Some commonly used Array Sorting Algorithms

Important terminologies related to Sorting:

Here we will see several algorithms used for array sorting. But before that let us see some important terminologies related to sorting:...

Some commonly used Array Sorting Algorithms:

Bubble Sort: Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large arrays as its average and worst-case time complexity is quite high. Selection Sort: Selection sort is another sorting technique in which we find the minimum element in every iteration and place it in the array beginning from the first index. Thus, a selection sort also gets divided into a sorted and unsorted subarray. Insertion Sort: Insertion sort similarly to the way we sort playing cards in our hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part. Merge Sort: It is a sorting algorithm that is based on the Divide and Conquer paradigm. In this algorithm, the array is repeatedly divided into two equal halves and then they are combined in a sorted manner. Quick Sort: This is a sorting algorithm based on the divide and conquer approach where an array is divided into subarrays by selecting a pivot element (element selected from the array). Heap Sort: Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements. Counting Sort: Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of elements having distinct key values (kind of hashing). Then do some arithmetic to calculate the position of each element in the output sequence....

Comparison of Time Complexity of Sorting Algorithms:

Name Best Case   Average Case   Worst Case  Memory Stable    Method Used Quick Sort N * logN N * logN N2 logN No Partitioning Merge Sort N * logN N * logN N * logN N Yes Merging Heap Sort N * logN N * logN N * logN 1 No Selection Insertion Sort N N2 N2 1 Yes Insertion Selection Sort N2 N2 N2 1 No Selection Bubble Sort N N2 N2 1 Yes Exchanging Counting Sort N+K N+K N+K N+K Yes Hashing...

Easy Problems on Array Sorting:

Program to check if an array is sorted or not (Iterative and Recursive) Print sorted distinct elements of array in C++ Print All Distinct Elements of a given integer array Alternative Sorting Sort an array in wave form Sort on the basis of number of factors using STL Sort an array which contain 1 to n values Sort 1 to N by swapping adjacent elements Sort elements by frequency | Set 1 Sort an array containing two types of elements Sort an array according to absolute difference with given value Sorting all array elements except one Minimum product pair an array of positive Integers Minimum adjacent swaps required to Sort Binary array Pairs with Difference less than K...

Medium Problems on Array Sorting:

Sort a nearly sorted (or K sorted) array Count Inversions in an array | Set 1 (Using Merge Sort) Union and Intersection of two sorted arrays Sort an array of 0s, 1s and 2s Check if reversing a sub array make the array sorted Merge 3 Sorted Arrays Sorting array except elements in a subarray Count all distinct pairs with difference equal to k Construct an array from its pair-sum array Ropes left after every removal of smallest Check if any interval completely overlaps the other Maximizing Unique Pairs from two arrays...

Hard Problems on Array Sorting:

Minimum number of swaps required to sort an array Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted Median in a stream of integers (running integers) Merge two sorted arrays with O(1) extra space Minimum De-arrangements present in array of AP (Arithmetic Progression) Divide an array into k segments to maximize maximum of segment minimums Maximum number of partitions that can be sorted individually to make sorted Rank of all elements in an array Merging two unsorted arrays in sorted order Sort an array after applying the given equation Minimum swaps to make two arrays consisting unique elements identical...