What is Sorting?

Sorting is a technique in which data is arranged in a meaningful order to analyze it in a better way. For eg: In school assemblies, students are made to stand in increasing order of height so that all the students can have a proper view of the stage.

Sorting algorithms in programming

Sorting is a way in which we can rearrange elements in an array/list of elements based on some comparisons. There are a lot of algorithms using which we can sort a list of elements. Mainly,

Insertion Sort
Selection Sort
Bubble Sort
Bucket Sort
Radix Sort
Merge Sort
Quick Sort etc.

Let's take a look at some basic sorting algorithms:

Insertion Sort:

In this algorithm, we make sure that the element should be inserted into its right position. We pick an element and check on its left if the element is greater than it, then it is not in its right place, so we keep checking on its left until we find the right place for it. That if we find that the element is not in its position while checking on the left we also shift the elements to its right making space for the element to be placed. The array keeps getting sorted from the left, as we find an element and check on its left.
It is an in-place and stable sorting algorithm.
This algorithm takes O(N²) time and O(1) extra space.

void insertionSort(int A[], int n)
    {
        //Insertion Sort
        for(int i=1;i<n;i++){
            int x=A[i];  //Element that has to be inserted
            int j=i-1;
            while(A[j]>x && j>=0){
                A[j+1]=A[j];  //Shifting elements to the right
                j--;
            }
            A[j+1]=x; //Inserting 'x' at its right position
        }
    }

Selection Sort:

In this algorithm, select an element and place it in its right position. We do it by selecting the smallest element and swapping its position to the first place. Find the second smallest element and swap it with the second place element. By doing this we will get an array sorted from left to right. We can do this by taking the largest element and performing the swapping but the array will be sorted from the right.
It is an in-place and stable sorting algorithm.
This algorithm takes O(N²) time and O(1) extra space.

void selectionSort(int arr[], int n)
    {
       //code here
       for(int i=0;i<n;i++){
           int x=i;
           for(int j=i;j<n;j++){
               if(arr[x]>arr[j]) x=j;
           }
           swap(arr[x],arr[i]);
       }
    }

Bubble Sort:

In this algorithm, we find the smallest element of the whole array and move it to the front. After each iteration, the array keeps getting sorted from the left as the smallest element comes and sets itself in the first available index from the front. The way the smallest element comes to the front is similar to the way bubbles start to float in sparkling water/aerated drinks, so we can call it bubble sort.
It is also an in-place and stable algorithm.

This algorithm takes O(N²) time and O(1) extra space.

  void bubbleSort(int arr[], int n)
      {
          // Your code here  
          for(int i=0;i<n-1;i++){
              for(int j=n-1;j>=i+1;j--){
                  if(arr[j]<arr[j-1]) {
                      swap(arr[j],arr[j-1]);
                  }
              }
          }
      }

Bucket Sort and Radix Sort:

These two sorting algorithms work on bucketing the elements into certain containers and applying sorting algorithms on individual buckets to finally sort the array/list.
The bucket sort on one hand divides the array based on the MSD(Most Significant Digit). The buckets will be of range (0-9) and based on the MSD we divide the array elements into these buckets. Then we individually sort the buckets and then copy the elements as it is in the same order to finally form the sorted array.
The radix sort on the other hand sorts the elements based on each digit from LSD to MSD. First, the array elements will be sorted based on the LSD and then the next digit and so on till the MSD and doing so the whole array will be sorted.
Time Complexity:
- Bucket Sort: O(N + N log(N))
- Radix Sort: O(N log (max(A)))
Space Complexity: Both algorithms take O(N) extra space.

Merge Sort:

This is a sorting algorithm that breaks down the array till only a single element exists and then sorts them on the way back while the merging happens. We use recursion for ease of the algorithm and of course the magic of recursion.
We divide the given array into two parts and then the recursion call will divide those two arrays into it's two different parts till only one element exits. Now the merge function will receive two sorted arrays and its job is to merge them both into a single array.
Using merge sort, we can sort any given Data Structure which can be divided into two halves. For eg, Array/List, Linked List, Stack etc.
Time complexity: O(N log N), Space complexity: O(N).

void mergeSort(int arr[],int start,int end){
    if(start>=end) return;
    int mid=(start+end)/2;
    mergeSort(arr,start,mid);
    mergeSort(arr,mid+1,end); 
    merge(arr,start,mid,end); //Merges 2 sorted arrays in O(end-start+1) time
}

Quick Sort:

In this algorithm, we keep finding the right place for each element and then we swap it to its rightful place once we find it. While doing that we will swap the other elements which are not in their right areas/violating the sorting order.
Time complexity: It varies from situation to situation.
- O(N log N) when the selected pivot element is in the middle.
- O(N²) when the array is reversely sorted.
- O(log N) when we select the pivot element to be the nearest element of the mean of the array and it is the best time complexity of all the above.

Quick sort is better than merge sort as the space complexity is O(log N) in quick sort where as it is O(N) in merge sort. The quick sort uses cache memory which is faster than the RAM used by merge sort.

  void quickSort(int arr[],int start,int end){
      if(start>=end) return;
      int pivot=rearrange(arr,start,end); //Finds the pivot and sets it to its right place
      quickSort(arr,start,pivot-1); //Quick sort is applied on the left side of the pivot
      quickSort(arr,pivot+1,end); //Quick sort is applied on the right side of the pivot 
  }

Extra points:

Out of all sorting algorithms, HEAP SORT is the best sorting algorithm that sorts the given array in O(N log N) time and constant extra space.
INBUILT SORT FUNCTION: Generally, if we call the inbuilt sorting function then a hybrid sorting function is used based on the input we have. The inbuilt algorithm can be a hybrid of 2 or more sorting algorithms to give the best possible time and space complexity. You can change the better(based on their complexities) algorithms like merge/quick sort with an integration of a selection sort if the input is <100 so the number of operations will be less in comparison to merge/quick sort.

A small note to end this article...

This is my first attempt at blogging, so if there are any errors please excuse me for that. I will be blogging about a lot more topics regarding DSA and computer science in general. So do consider following me on Hashnode as well as my Twitter and LinkedIn.

I hope you all had a good read and if you gained any benefit reading this article or there is any doubt regarding the above topic or there is an error that I might have missed, leave a comment below or reach out on LinkedIn, I will be more than happy to help you out! :)

Venketesh's Blog