What is a sorting algorithm?

A sorting algorithm is a systematic approach used to arrange elements in a specific order within a collection, typically a list or an array. The primary objective of sorting is to organize data in a way that makes it easier to search, retrieve, and analyze. Sorting algorithms play a crucial role in computer science and various applications, ranging from database management to data visualization.

There are various sorting algorithms, each with its own set of advantages, disadvantages, and specific use cases. Here's a brief overview of the key concepts related to sorting algorithms:

Comparison-based vs. Non-comparison-based: Sorting algorithms can be broadly classified into two categories based on whether they rely on pairwise comparisons between elements. Comparison-based algorithms, such as bubble sort, merge sort, and quicksort, compare elements and determine their relative order. Non-comparison-based algorithms, like counting sort and radix sort, exploit the inherent properties of the data to sort elements without direct comparisons.
Stability: A sorting algorithm is considered stable if it maintains the relative order of equal elements in the sorted output as they were in the input. Stability is an essential characteristic in scenarios where secondary sorting is required.
Time Complexity: The efficiency of sorting algorithms is often evaluated in terms of time complexity, which represents the computational time required for the algorithm to complete as a function of the input size. Common notations include O(n^2) for quadratic time complexity (e.g., bubble sort) and O(n log n) for algorithms with better average and worst-case performance (e.g., merge sort, quicksort).
Space Complexity: Sorting algorithms also differ in their space complexity, which indicates the amount of additional memory required for sorting. In-place algorithms, such as bubble sort and insertion sort, sort the elements within the existing data structure without requiring additional memory. On the other hand, algorithms like merge sort may need extra space proportional to the input size.
Adaptivity: Some sorting algorithms exhibit adaptivity, meaning their performance improves when applied to partially ordered data. Adaptive algorithms, like insertion sort, are well-suited for situations where the input data is already partially sorted.

Insertion

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

To sort an array of size N in ascending order iterate over the array and compare the current element (key) to its predecessor, if the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Consider an example: arr[]: { 12, 11, 13, 5, 6 }

First Pass:

Initially, the first two elements of the array are compared in insertion sort.

Here, 12 is greater than 11 hence they are not in the ascending order and 12 is not at its correct position. Thus, swap 11 and 12.
So, for now 11 is stored in a sorted sub-array.

Second Pass:

Now, move to the next two elements and compare them

Here, 13 is greater than 12, thus both elements seems to be in ascending order, hence, no swapping will occur. 12 also stored in a sorted sub-array along with 11

Third Pass:

Now, two elements are present in the sorted sub-array which are 11 and 12
Moving forward to the next two elements which are 13 and 5

Both 5 and 13 are not present at their correct place so swap them

After swapping, elements 12 and 5 are not sorted, thus swap again

Here, again 11 and 5 are not sorted, hence swap again

Here, 5 is at its correct position

Fourth Pass:

Now, the elements which are present in the sorted sub-array are 5, 11 and 12
Moving to the next two elements 13 and 6

Clearly, they are not sorted, thus perform swap between both

Now, 6 is smaller than 12, hence, swap again

Here, also swapping makes 11 and 6 unsorted hence, swap again

Finally, the array is completely sorted.

Sorted array.

Selection

Selection sort is an in-place comparison sorting algorithm.

The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list.

Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

As we traverse through the array in an initial loop, we push forward through the array with a second pointer in a nested loop at the same time, comparing each value to the starting value (beginning with our first loop's initial index.) If we find a lower value, we set that new value as our new lowest value to be compared against, and continue pushing.

By doing this, we ensure that each time we traverse through the array we will always find the next lowest value. When we reach the end of our second loop, we swap the lowest value with our very first initial index's value, and proceed to the next step.

This could also be done in reverse order, by searching for the largest values, if we were interested in sorting from highest to lowest.

How efficient is it?

Selection Sort, while relatively simple to comprehend and implement, unfortunately lags behind other sorting algorithms like Quick Sort, Heap Sort, and Merge Sort for larger data sets.

However, since Selection Sort functions in-place and requires no auxiliary memory, it does have a space advantage over some other more complicated algorithms.

Generally speaking, Insertion Sort is likely to be a more performant alternative, although Selection Sort is still important to know and understand as a programmer and computer scientist.

Selection Sort has a best case, worst case, and average case runtime complexity of O(n^2), meaning it will always be quadratic in nature.

Bubble

Bubble sort algorithm is a simple sorting technique that compares two adjacent elements in an array and swaps them if they are in the wrong order. It keeps repeating this process until the array is sorted.

For example, the diagram below illustrates the different swaps/bubble that happens when the element on the left is greater than the element on the right.

Also, at the end of the array iteration, it checks to see if any swaps occurred; if so, the process is repeated; otherwise, the array is sorted.

Unsorted Array

[ 12, 3, 7, 4, 10 ]

→

Swap since 12 > 3

→

[ 3, 12, 7, 4, 10 ]

Here 12 is greater than 3. Swap 12 and 3

[ 3, 12, 7, 4, 10 ]

→

Swap since 12 > 7

→

[ 3, 7, 12, 4, 10 ]

Here 12 is greater than 7. Swap 12 and 7

[ 3, 7, 12, 4, 10 ]

→

Swap since 12 > 4

→

[ 3, 7, 4, 12, 10 ]

Here 12 is greater than 4. Swap 12 and 4

[ 3, 7, 4, 12, 10 ]

→

Swap since 12 > 10

→

[ 3, 7, 4, 10, 12 ]

Here 12 is greater than 10. Swap 12 and 10

Repeat the process since elements has been swapped.

[ 3, 7, 4, 10, 12 ]

→

No swap since 3 < 7

Here 3 is not greater than 7. No swap

[ 3, 7, 4, 10, 12 ]

→

Swap since 7 > 4

→

[ 3, 4, 7, 10, 12 ]

Here 7 is greater than 4. Swap 7 and 4

[ 3, 4, 7, 10, 12 ]

→

No swap since 7 < 10

Here 7 is not greater than 10. No swap

[ 3, 4, 7, 10, 12 ]

→

No swap since 10 < 12

Here 10 is not greater than 12. No swap

Repeat the process since elements has been swapped.

[ 3, 4, 7, 10, 12 ]

→

No swap since 3 < 4

Here 3 is not greater than 4. No swap

[ 3, 4, 7, 10, 12 ]

→

No swap since 4 < 7

Here 4 is not greater than 7. No swap

[ 3, 4, 7, 10, 12 ]

→

No swap since 7 < 10

Here 7 is not greater than 10. No swap

[ 3, 4, 7, 10, 12 ]

→

No swap since 10 < 12

Here 10 is not greater than 12. No swap

End of array since no elements has swapped.

[ 3, 4, 7, 10, 12 ]

Sorted array.

Shell

The key idea behind Shell Sort is to repeatedly divide the input array into smaller subarrays and sort the elements within those subarrays using an insertion sort.

The algorithm works by defining a sequence of increment values (often referred to as the "gap" sequence), which determine the size of the subarrays. The elements that are a certain gap distance apart are compared and swapped if necessary. The gap is then reduced, and the process is repeated until the gap becomes 1. At this point, the algorithm performs a final insertion sort on the entire array.

Shell Sort has a time complexity that depends on the chosen gap sequence, and in practice, it exhibits better performance than simpler quadratic sorting algorithms. However, it is generally outperformed by more advanced sorting algorithms like quicksort and mergesort for larger datasets. Shell Sort is often used in scenarios where memory is limited, and more advanced algorithms may not be feasible.

Unsorted Array

Step 1

Here, the array size is 8. Thus, the interval value will be h = 8/2 or 4.

Step 2

Now, we will store all the elements at a distance of 4. For our case, the sublists are = { 8, 1 }, { 6, 4 }, { 7, 5 }, { 2, 3 }.

Step 3

Now, those sublists will be sorted using insertion sort, where a temporary variable is used to compare both numbers and sort accordingly.

Now, the array looks like this.

Step 4

Now, we will decrease the initial value of the interval. The new interval will be h=h/2 or 4/2 or 2.

Step 5

As 2>0, we will go to step 2 to store all the elements at a distance of 2. For this time, the sublists are = { 1, 5, 8, 7 }, { 4, 2, 6, 3 }

Then these sublists will be sorted using insertion sort. After comparing and swapping the first sublist, the array would be the following.

After sorting the second sublist, the original array will be:

Then again, the interval will be decreased. Now the interval will be h=h/2 or 2/1 or 1. Hence we will use the insertion sort algorithm to sort the modified array.

Following is the step-by-step procedural depiction of insertion sort.

The interval is again divided by 2. By this time, the interval becomes 0.

As the interval is 0, the array is sorted

Sorted array.

Merge

Merge Sort is a popular and efficient divide-and-conquer sorting algorithm.

The primary idea behind Merge Sort is to divide the unsorted array into two halves, recursively sort each half, and then merge the sorted halves to produce a fully sorted array.

Merge Sort ensures stability, meaning that the order of equal elements in the original array is preserved in the sorted array. It has a guaranteed time complexity of O(n log n), making it efficient for large datasets. However, it comes with a space complexity of O(n) due to the need for additional space to store the merged subarrays.

Merge Sort is widely used in various applications and serves as a foundation for more advanced sorting algorithms. Its predictable and efficient performance makes it a reliable choice for sorting large datasets.

Unsorted Array

Step 1

As there are eight elements in the given array, so it is divided into two arrays of size 4.

Step 2

Now, again divide these two arrays into halves. As they are of size 4, so divide them into new arrays of size 2.

Step 3

Now, again divide these arrays to get the atomic value that cannot be further divided.

Now you can't divide anymore it's time to merge.

Step 4

In combining, first compare the element of each array and then combine them into another array in sorted order.

So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in the list of two values, put 8 first followed by 25. Then compare 32 and 17, sort them and put 17 first followed by 32. After that, compare 40 and 42, and place them sequentially.

Step 5

In the next iteration of combining, now compare the arrays with two data values and merge them into an array of found values in sorted order.

Step 6

Now, there is a final merging of the arrays.

Sorted array.

Quick

QuickSort is a widely used sorting algorithm known for its efficiency and simplicity. It follows a divide-and-conquer approach to sort an array of elements. The algorithm works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays based on whether they are less than or greater than the pivot. This process is then applied recursively to the sub-arrays. The key steps in QuickSort are:

Pivot Selection: Choose a pivot element from the array. Common strategies include selecting the first, last, or middle element.
Partitioning: Rearrange the array elements so that elements less than the pivot are on its left, and elements greater than the pivot are on its right. The pivot is now in its final sorted position.
Recursive Sort: Apply QuickSort recursively to the sub-arrays on the left and right of the pivot until the entire array is sorted.

Unsorted Array

Step 1

Select the Pivot element. In this case it's going to be 2.

Step 2

Rearrange the array. Put all elements smaller than the Pivot element to the left and elements larger to the right.

Here's how we rearrange the array

A pointer is fixed at the pivot element. The pivot element is compared with the elements beginning from the first index.

↑

If the element is greater than the pivot element, a second pointer is set for that element.

↑

(Second pointer)

(First pointer)

Now, pivot is compared with other elements. If an element smaller than the pivot element is reached, the smaller element is swapped with the greater element found earlier.

↑

No switch since 6 is bigger than the Pivot number.

↑

Now, we want to switch elements 8 and 1 since 1 is smaller than the Pivot element.

↑

Again, the process is repeated to set the next greater element as the second pointer. And, swap it with another smaller element.

↑

(Second pointer)

(First pointer)

Now, we want to switch elements 7 and 0 since 0 is smaller than the Pivot element.

The process goes on until the second last element is reached.

↑

Finally, the pivot element is swapped with the second pointer.

Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is repeated.

→

Finally you will be ended up with a sorted array.

Sorted array.

Sorting Algorithms

Sorting Algorithms Animations

The provided animations demonstrate the efficient sorting of data sets originating from various starting points, showcasing the effectiveness of different algorithms.

What is a sorting algorithm?

Unsorted Array

Sorted Array

Insertion

Selection

How efficient is it?

Bubble

Shell

Merge

Quick