Sorting Algorithms
Hello, my fellow coders!! today we are gonna discuss about different sorting techniques or sorting algorithms used in coding. I hope this blog would prove to be helpful to budding coders and also students like me who have some doubts in this topic.
What is sorting?
Computer science highly depends upon sorting algorithms. They organize disordered data through criteria such as alphabetical order, highest-to-lowest value, or shortest-to-longest distance.
Why Sorting?
>Sometimes an application must sort data on its own. Banks, for example, must sort checks by check number in order to prepare customer statements.
>Many engineering issues arise when sorting algorithms are implemented. The fastest sorting program for a given situation may be determined by a variety of factors, including prior knowledge of the keys and satellite data, the host computer’s memory hierarchy, and the software environment.
>We can choose from a wide range of sorting algorithms, each of which employs a diverse set of techniques. Indeed, many important techniques used in algorithm design can be found in the body of sorting algorithms that have been developed over time. Sorting, in this sense, is therefor also a historical problem.
In this blog, we will talk about -
1. Bubble Sort
2. Insertion Sort
3. Quick Sort
BUBBLE SORT
The Bubble Sort algorithm compares elements two at a time, with the element with the higher value passing on, and the element with the lowest value “emerging” in the first place in the first iteration.
Basically, if a list of elements is provided to arrange it in ascending order, then this technique will start comparing first two elements with each other, and if first element is greater than the second element, they both are swapped and similarly next two elements are compared and so on.
Implementation
The algorithm in our example starts by comparing the first element (11) with the second (10). Since 11 is greater than 10, it replaces 10 as the second element in the list. Then it repeats the procedure with the second element (11) and the third element (2), and so on with all of the list elements. As a consequence, in the first pass, the highest element in the list (11) will be put at the end of the list (on the right). The algorithm will go through all of the elements several times before they are all sorted, “bubbling up” each element to its proper position, finally providing us the sorted array- [2,5,7,10,11].
Complexity Analysis
- Time Complexity
>Best case scenario- The best case scenario occurs when the array is already sorted. In this case, no swapping will happen in the first iteration. So, when this happens, we break from the loop after the very first iteration. Hence, time complexity in the best case scenario is O(n) because it has to traverse through all the elements once.
>Worst case scenario- In Bubble Sort, n-1 comparisons are done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So, the total number of comparisons will be
Sum = (n-1) + (n-2) + (n-3) + …..+ 3 + 2 + 1
Sum = n(n-1)/2
Hence the time complexity of bubble sort is O(n²). - Space Complexity
Since only a single additional memory space is needed, namely for the temporary variable used for swapping, the algorithm’s space complexity is O(1).
Bubble Sort is frequently regarded as an inefficient sorting tool because it must exchange items before the final locations of the elements are known. However, if no exchanges occur during a pass, we know that the list must be sorted. Bubble Sort can be configured to stop early if it detects that a list has become sorted, allowing it to recognize sorted lists.
INSERTION SORT
Have you have ever sorted a deck of playing cards? If the answer is ‘Yes’, then you have implemented insertion sort unknowingly.
So, basically, Insertion sort is a basic sorting algorithm that works in the same way that you sort cards in your hands. The array is virtually divided into two main sections, one sorted and the other unsorted. Values from the unsorted part are selected and inserted into in the sorted part at the appropriate place.
Implementation
The algorithm first marks the first element(5) as sorted in our example, starting from the left. Then it selects the second element (9) from unsorted list and compares with previous element, and since it is sorted until that element, program moves forward.
The algorithm then marks the first element (9) as sorted. The program then selects the second element (6) from the unsorted list and compares it to the previous element from the sorted list. Since 6 is less than 9, the higher element is moved to the right and the smaller one is inserted in the first place. The sorted list is now represented by elements 5, 6 and 9. The algorithm completes this exercise in a sequential manner, removing elements from the unsorted list on the right and comparing them to elements in the sorted list on the left to determine where they should be inserted.
Complexity Analysis
- Time Complexity
>Best case scenario- Even though insertion sort is efficient, still, if we provide an already sorted array to the insertion sort algorithm, it will still execute the outer for loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n.
Hence, time complexity in the best case scenario is O(n).
>Worst case scenario- In an unsorted array, it takes for an element to compare with all the other elements which mean every n element compared with all other n elements. Thus, making it for n x n, i.e., n2 comparisons. Therefore, the time complexity of insertion sort is O(n²). - Space Complexity
Everything is done in-place (meaning no auxiliary data structures, the algorithm performs only swaps within the input array), so the space-complexity of Insertion Sort is O(1).
Insertion Sort is adaptive, which means it reduces its total number of steps if a partially sorted array is provided as input, making it more efficient. Insertion Sort is not suitable for large data volumes where it looses against other sorting algorithms.
QUICK SORT
The quicksort algorithm is a divide-and-conquer algorithm, which breaks down a problem into two or more sub problems of the same or similar kind until they are easy enough to solve directly.
Implementation
Essentially, we are dividing our sorting problem into three steps: divide, conquer, combine.
Let’s take a typical subarray A[p…r]
DIVIDE: Breaking the array A[p…r] into two subarrays A[p…q-1] and A[q+1…r] such that each element of A[p…q-1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[q+1…r]. We are taking the index q as part of this partitioning procedure.
CONQUER: Now we sort the two subarrays A[p…q-1] and A[q+1…r] by recursive calls to quicksort.
COMBINE: Because the subarrays are already sorted, no work is needed to combine them: the entire array A[p…r] is now sorted.
Complexity Analysis
- Time Complexity
>Best case scenario- In the most even possible split, Partition function will produce two sub problems, each of size more than n/2, since one if of size [n/2] and one of size [n/2]-1. Hence the time complexity in the best case scenario is O(nLogn).
>Worst case scenario- It occurs when the partitioning routine produces one sub problem with n-1 elements and one with 0 elements. If the partitioning is maximally unbalanced at every recursive level of the algorithm, the worst time complexity is found out to be O(n²). - Space Complexity
The space complexity is calculated based on the space used in the recursion stack. The worst case space used will be O(n). The average case space used will be of the order O(logn). The worst case space complexity becomes O(n), when the algorithm encounters its worst case where for getting a sorted list, we need to make n recursive calls.
Quick Sort can take longer to complete if the sub-divisions generated after partitioning are unbalanced. To avoid this, choose a random pivot factor to spread out the risk of unbalanced partitions.
Which one to choose ?
As a general rule, Insertion Sort is best for small lists, Bubble Sort is best for lists that are already almost sorted, and Quick Sort is usually fastest for everyday use…