Sorting Techniques 1.0
Have you ever wondered how items on an online shopping website rearranges its items for sale to match your preferences (for example: Prices- Highest to Lowest)? What are the underlying algorithms? Let’s find out…
There are innumerable ways of “Sorting” so let’s check out some of the most popular sorting techniques!!
SORTING ALGORITHMS
Before we dive into the various types of sorting algorithms let’s first see what “Sorting” actually is and some basic terms related to it.
Sorting is any process of arranging items systematically. It has two common, yet distinct meanings: Ordering (arranging items in a sequence ordered by some criterion) and Categorizing (grouping items with similar properties).
However, in coding, a Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.
Time Complexity — the amount of time taken by an algorithm to run, as a function of the length of the input. It measures the time taken to execute each statement of code in an algorithm.
Space Complexity — The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of the characteristics of the input. It is the memory required by an algorithm until it executes completely.
Algorithmic Paradigm — a generic model or framework which underlies the design of a class of algorithms. For example:- Divide and conquer, Brute force, Dynamic programming etc.
Stability — A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
INSERTION SORT
Chances are you have probably already heard of this sorting technique. Insertion sort is one of the most basic and most popular sorting techniques to exist.
Insertion sort uses the idea of dividing the array into two parts — the first part of the array being the ‘Sorted part’ and the remaining part being the ‘Unsorted Part’. The ‘Unsorted Part’ of the array is iterated through and each element is compared with the predecessor.|
If this element is greater than or equal to the predecessor no change is made and the iteration is continued.
If this element is smaller than the predecessor then the element is ‘inserted’ into the correct position of the ‘Sorted Part’ and then the iteration is continued.
The following is the python code for Insertion Sort :-
Time Complexity: O(n²)
Space Complexity: O(1)
Algorithmic Paradigm: Incremental Approach (i.e to enable the user to visualise intermediate results until a desired final result is achieved)
Stable: Yes
COUNTING SORT
Counting sort is a type of sorting algorithm used when the the range of the given data set is known. The idea behind implements counting the number of elements having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.
To understand this let us see a quick example:-
The given data input is:- 1,4,1,2,7,5,2
We use a ‘count array’ to note the occurrences of each element in the data input at the element-index of the count array. Here, there are two 1s in the data input, hence the value 2 is stored at index 1 in the count array.
We then modify the count array by adding the previous counts in the count array.
The final ‘output array’ is created. We now again parse the data input. For each element (k) in the data input, we see the value (v) at that index (k) in the count array. We place this element (k) at the index (v) of the output array and then decrease the value (v) in the count array by 1.
Here in this example:-
1 -> has a count of 2 -> placed at index 2 in the output array (and count is decremented and changes to 1)
4 -> has a count of 5-> placed at index 5 in the output array (and the count is decremented and changed to 4)
1 -> has a count of 1 (value changed from 2 to 1 at step 1)-> placed at index 1 in the output.
2 -> has a count of 4-> placed at index 4 in the output array (and the count is decremented and changes to 3)
7 -> has a count of 7-> placed at index 7 in the output array (and the count is decremented and changes to 6)
5 ->has a count of 6-> placed at index 6 in the output array (and count is decremented and changes to 5)
2 -> has a count of 3 (value changed from 4 to 3 at step 3)-> placed at index 3 in the output array (and the count is decremented and changes to 2)
Above is the given image of the final status of output and count arrays.
The following is the python code for Counting Sort:-
Time Complexity: O(n+k) where n is the number of elements in the input array and k is the range of input.
Auxiliary Space: O(n+k)
Stable: Yes
RADIX SORT
Now that we have seen Counting sort what happens if we have huge ranges of numbers? Using counting sort would take too much time to sort large data sets. And that brings us to our next sorting method -> Radix Sort. Radix sort implements the idea of sorting by the digits of the numbers, starting from the least significant digit to the most significant digit.
Let’s try to understand this with an example:-
Given data input:-
23, 7, 439, 129, 366, 47, 256, 69We start from the least significant digit:-
23, 7, 439, 129, 366, 47, 86, 69 -> 23, 366, 86, 7, 47, 439, 129, 69We move to the next significant digit:-
23, 366, 86, 7, 47, 439, 129, 69 -> 7, 23, 439, 129, 47, 366, 69, 86We move to the next significant digit:-
7, 23, 439, 129, 47, 366, 69, 86 -> 7, 23, 47, 69, 86, 129, 366, 439Final sorted output:-
7, 23, 47, 69, 86, 129, 366, 439
The following is the python code for Radix Sort:-
Time Complexity:O((n+b) * logb(k)) where n is the number of elements in the input array, b is the base of the number system and k is the maximum input.
Auxiliary Space: O(n+2^d)
Stable: Yes
A FEW POPULAR SORTING TECHNIQUES
Bubble Sort is a very popular sorting technique and is one of the most basic sorting algorithms everyone usually starts off with. The algorithm works by repeatedly swapping the adjacent elements if they are in the wrong order.
Let us see the following example:-
Given Data Input :- ( 5 1 4 2 8 )
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )The Selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The already sorted subarray
2) The remaining unsorted subarray
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
The following example explains the above steps:
arr[] = 64 25 12 22 11
// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64
// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64
// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64
// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64CONCLUSION
Sorting Algorithms/Techniques are very helpful to sort the given data at your convenience. It is very helpful for competitive programming. You can parse data structures and order them much faster and very easily.
Learning how to sort data structures is very useful but not always easy to perform. This article covers only a few sorting algorithms. Stay tuned in for more on Sorting Algorithms/Techniques.
REFERENCES
Code:- GeeksForGeeks, Programiz
Pictures:- GeeksForGeeks and Google Images
