Sorting in Data Structure: Categories & Types

Sorting is an arrangement of data in a particular order.

But if we talk about sorting in Data Structure then it’s more relevant to rearrange the data or element in ascending or descending order which can be lexicographical, numerical, or maybe user-defined. For example, Consider you have five siblings and you want to arrange them according to height.

Now if you wish to arrange them in increasing or decreasing order of height and then algorithm, you’ll perform to do this task is sorting. But more interestingly in How much time, you can do it? Suppose if you do it in five sec and when your brother is given a chance and he does it in three sec then his idea
would be best among both of you. That’s the complexity of your algorithm.

What is Sorting in Data Structure?

In other words, you can say that sorting is also used to represent data in a more readable format. Some real-life examples of sorting are:-

• Contact List in Your Mobile Phone also contains all contacts arranged alphabetically (lexicographically). So if you look for contact then you don’t have to look randomly and can be searched easily and many others like Apps on your phone.
  
• Keywords in Your book are also in a lexicographical manner and you can find it according to Chapter.

Why Study Sorting?

• When you perform sorting on an array/elements, many problems become easy (e.g. min/max, kth smallest/largest)
• Performing Sorting also gives no. of algorithmic solutions that contain many other ideas such as:
• Iterative
• Divide-and-conquer
• Comparison vs non-comparison based
• Recursive

The main advantage of sorting is time complexity and that’s the most important thing when you solve a problem because it’s not enough you’re able to solve a problem but you should be able to solve it in the minimum time possible. Sometimes problems can be solved easily and quickly based on sorting which can prevent you from every Coder’s Nightmare i.e. TLE (Time Limit Exceeded).

Types of Sorting algorithms:-

Although there is no. of sorting algorithms best algorithm is which can solve a problem in the minimum time and minimum space required to do so. Some types of the Sorting algorithm are:-

• Bubble Sort: It’s one of the simplest algorithms which repeatedly iterates through the list, compares the elements next to each other, and swaps according to the condition passed to them. Confusing isn’t it? It would be right to say this Sorting as an idea or approach to solving a problem what we people usually do (Brute force Solution).

Suppose, You are given an array, arr [8] = {2, 4, 1, 6, 5, 3, 7, 8} and you have to sort it in increasing order then Steps followed would be as:

• Here two loops would be required in sorting, the first loop for iterating and the second loop for comparing.
• As first you’ll check if the previous element is greater than the next element then swap it otherwise increase the counter.

	First pass
{ 2 4 1 6 5 3 7 8 }   { 2 4 1 6 5 3 7 8 } , Since these elements are already sorted (2 < 2) , no swapping required
{ 2 4 1 6 5 3 7 8 }   { 2 1 4 6 5 3 7 8 }, Here compares the elements and found (4 > 1), so swaps them.
{ 2 1 4 6 5 3 7 8 }   { 2 1 4 6 5 3 7 8 }, No swapping (4 < 6)
{ 2 1 4 6 5 3 7 8 }   { 2 1 4 5 6 3 7 8 }, Swapping (6 > 5)
{ 2 1 4 5 6 3 7 8 }   { 2 1 4 5 3 6 7 8 }, Swapping (6 > 3)
{ 2 1 4 5 3 6 7 8 }   { 2 1 4 5 3 6 7 8 }, No swapping (6 < 7)
{ 2 1 4 5 3 6 7 8 }   { 2 1 4 5 3 6 7 8 }, No swapping (7 < 8)

	Second pass
{ 2 1 4 5 3 6 7 8 }   { 1 2 4 5 3 6 7 8 }, Swapping (2 > 1)
{ 1 2 4 5 3 6 7 8 }   { 1 2 4 5 3 6 7 8 }, No swapping (2 < 4)
{ 1 2 4 5 3 6 7 8 }   { 1 2 4 5 3 6 7 8 }, No swapping (4 < 5)
{ 1 2 4 5 3 6 7 8 }   { 1 2 4 3 5 6 7 8 }, Swapping (5 > 3)
{ 1 2 4 3 5 6 7 8 }   {1 2 4 3 5 6 7 8 }, No swapping ( 5 < 6)
{ 1 2 4 3 5 6 7 8 }   { 1 2 4 3 5 6 7 8 }, No swapping (6 < 7)
{ 1 2 4 3 5 6 7 8 }   { 1 2 4 3 5 6 7 8 }, No swapping (7 < 8)

And So on n-1 passes i.e. 7 passes it will check further. The one thing that makes this algorithm time consuming is even though the array is sorted in the second pass but it will continue going to check up to n-1 passes.

Not much clear Right? Alright, we’ll take a look at how this algorithm works which will give us a clear idea about this algorithm.

Void bubbleSort(int arr[ ], int n){
           For( int I = 0;  I < n-1; I++){          //outer loop for iterating to n-1 elements
                    For( int j = 0; j < n-I-1; j++){      //inner loop for checking each element
                         If (arr[ j ] > arr[ j+1 ]{            // For swapping if previous element is greater than next one
                               Swap( arr[ j ], arr[ j+1 ]);
                             }
                     }
             }
}

• Insertion Sort – it is an algorithm that works the way we sort our money. Funny isn’t it? Consider you have some 1rs., 2rs., 5rs. coins and some 10rs., 50rs., 100rs.,200rs.,500rs.,200rs. notes and they are already in sorted order(increasing) of their amount. If I give u another 100rs. Note and ask you to insert the note in the right position so that money in your hand should be sorted. How will you do it?

Well, you’ll have to go through each coin/note to check from starting for finding the right position of the new note. Once you find the right position, you’ll insert it.

Let’s consider an array, arr[ ]={5, 1, 6, 2, 4, 3} So what will we do in this we will start from index 1 to n-1 and compare that element with all elements from beginning and will put it in its right place.

Void insertionSort(int arr[ ], int n){
               Int i, temp, j;
               For(i=1; i<n; i++){   //We will start iterating through index 1
                     temp=arr[ i ];         //Will store the value in a temporary variable
                      J= i-1;
                      While(j>=0 and arr[ j ] > temp){    //check the which value is greater
                                 arr[ j+1] = arr[ j ];
                                 j - -;
                       }
                    arr[ j+1 ] = temp;   //Replace that value with the temporary variable
               }
}

• Selection Sort: Selection sort works by repeatedly finding the smallest element from the array and then putting it in the beginning and then again finding the smallest from the rest of the array other than the previous one and arranging it in beginning. So basically we can say that it has two subarrays in it one is Sorted and the other is unsorted.    

Let’s consider an array, arr[ ]= { 23, 78, 45, 8, 32, 56}

Void SelectionSort(int arr[ ], int n){
               int i, j, minIndex;
               for(i=0; i<n-1; i++){
                     minIndex=i;     //index of minimum element
                     for(j=i+1; j<n; j++){
                           if(arr[ j ] < arr[ minIndex ]){ 
                                minIndex=j; //update the min element 
                                swap(arr[ minIndex ], arr[ i ]); //Swapping 
                             }
                      }
               }
}

• Divide the larger problem into smaller problems i.e. it divides the array into two(equal) parts.
• Recursively sort the smaller problems (equal parts).
• Finally after solving it combines the result of a smaller problem to produce the results of the larger problem i.e.merge the two equal parts of the sorted array to form a parent sorted array.

Void mergeSort(int arr[ ], int si, int ei){
            If (si < ei){
                  Int mid=si+(ei - si) / 2;                      //For finding the mid of array so it can be divided into two equal parts

            mergeSort(arr, si, mid);                 //Applying merge Sort on first-half i.e. from starting-index to mid-index

            mergeSort(arr, mid+1, ei);           //Applying merge Sort on second half i.e. from mid-index to last-index

            merge(arr, si, mid, ei);             //Finally merging the two sorted arrays
          }
}

         /* For merging of sorted array*/

Void merge(int arr[ ], int si, int ei, int mid, int high){      
          int n= ei – si + 1;                                                                                                                    //Size of the array 
          int* temp=new int[n];             //Temporary array for storing the new sorted array
         
          int left_index=si, right_index=mid+1, temp_index=0;           
          
          while( left_index <= mid and right_index <= ei ) {
                     if ( arr[left_index] <= arr[right_index])                      //if the element at left index is smaller than right index, store it into temporary array 
                                temp[temp_index++] = arr[left_index++];
                     else
                           temp[temp_index++] = arr[right_index++];     //if the element of right index is smaller than left index, store it into temporary array
          }
          
          while( left_index <= mid ) {                                            //Suppose if the elements of left index are still left then directly store the rest of elements
                      temp[temp_index++] = arr[left_index++];
         }
          
         While( right_index <= ei ){                                           //Suppose if the elements of right index are still left then directly store the rest of elements
                     temp[temp_index++] = arr[right_index++];
          }
        
          For(int k=0; k < n; k++){               //Finally making the changes in the original array i.e. storing the merged result
                    arr[si+k] = temp[k];
          }

          delete [ ] temp;                            //For de-allocation of memory
}
                

• Quick Sort: It is based on partition. It is also known as partition exchange sorting. The basic concept of this algorithm is to pick one element from an array and rearranges the rest of elements around it and that element is known as pivot element and that element divides the main array into two sub-arrays. Once the pivot is fixed then it moves all the elements lesser than it to left and elements greater than it to right. This procedure is repeated recursively until there is one element left in the sub-array.

Let’s consider an array consisting of elements: 27, 38, 12, 39, 27, 16. Here 27 is chosen as pivot element and an array is divided into two sub-arrays consisting of all elements less than pivot to the left sub-array and greater than pivot to the right sub-array.

Void quicksort( int arr[ ],int si,int ei){

          If (si < ei) {
              Int pivot_index = partition(arr, si, ei);                 //Partition on basis of starting and end index for getting pivot
              quicksort(arr, si, pivot_index-1);
              quicksort(arr, pivot_index+1, ei);                   //Recursively Sort into two parts
          }
}

         /* For partitioning of array */       

Int partition(int arr[ ], int i, int j){                     //For iterating through unknow region given in above picture
          int pivot = arr[i];           
          int pivot_index = i;
          for (int k=i+1; k<=j; k++){
              if ( arr[ k ] < p){                                                                                 // Case2
                      pivot_index++;
                      swap(arr[ k ], arr[ pivot_index];          
              }
             else{                                // Case 1: Do nothing
              }
          }
         Swap( arr[ i ], arr[ pivot_index ]);                     //For swapping pivot with arr[pivot_index]
         return pivot_index;
}

Although there is no. of sorting algorithms mostly used are discussed above and others are also important which is used in advanced Data Structure such as-

• Heap Sort
• Counting Sort
• Bucket Sort
• Radix Sort
• Shell Sort
• Comb Sort
• Cycle Sort
• Bitonic Sort
• Tree Sort
• Stooge Sort

Facts: One thing that comes to our mind is why to study it when we have already inbuilt sorting function in Python, C++ and Java. But you should know that

• Python and Java sorting function is based on TimSort(hybrid algorithm of mergeSort and insertion Sort).
• C++ sort function(STL) is based on IntroSort(hybrid algorithm of quick Sort and heap Sort) and many more.

Overall these above-explained sorting algorithms are basics to understand any further advanced Sorting algorithms.

In-place Sorting and Not-in-place Sorting:-

‘In place’ means whenever you are sorting and you don’t require any extra space except the input space excluding the constant space which is used for variables or iterators. It also doesn’t include the space used for stack in the recursive algorithms. Now, In merge sort, when we perform merging then the merge function requires extra linear space which is not constant. So, it is not in-place. Hence, it is called ‘out of place’ algorithm or sorting.

On the other hand, Quicksort is kind of sorting which uses only some constant number of variables for partitioning purpose. So, it is an in-place algorithm or sorting.

Stable and Not stable Sorting:-

• A sorting algorithm when two objects with equal keys appear in the same order in the sorted output as they appear in the unsorted input.
• Whereas a sorting algorithm is called as an unstable sorting if there are two or more objects with equal keys which don’t appear in the same order before and after sorting.

Above we can see an example of stable sorting here number 26 is appearing two times at respective position 6 and 8 and their occurrence is kept in unsorted and sorted array i.e. element 26 (blue) at position 6 appears first in unsorted and then appears in sorted array.

One thing should be kept in mind in the case of an unstable sort, the order of appearance/occurrence before and after sorting is not necessarily preserved.

There are some sorting algorithms which are stable by nature such as Insertion sort, Merge Sort, Bubble Sort, etc. while on the other hand sorting algorithms like Heap Sort, Quick Sort are vice-versa.

Adaptive and Non–Adaptive Sorting Algorithm:-

When occurrence of the elements to be sorted of an input array matters the time complexity of a sorting algorithm, then that algorithm is called “Adaptive” sorting algorithm.

For example, Insertion sort is an adaptive sorting algorithm like in the case if input is already sorted then we know that time complexity will be O(n). That’s why If the input array is almost sorted then choose insertion sort, though this is not the only thing to be kept in mind for Insertion sort over other sorting algorithms.

Merge Sort is a “Non-Adaptive” Sorting algorithm because the order of the elements in the array doesn’t matter So the time complexity of algorithm will always be O(nlogn).

Adaptive sorting algorithms:

• Bubble Sort
• Insertion Sort
• Quick Sort

Non-adaptive sorting algorithms:

• Selection Sort
• Merge Sort
• Heap Sort

Which sorting is best in data structures?

Every sorting algorithms have their own advantages and disadvantages. Select the sorting algorithm that is best fitted for your data. If you’re constrained in space the choose heap sort. If you need something stable choosing merge sort will help you. For almost sorted data, considering insertion sort is O(n) time!

Inbuilt sorting algorithms use hybrid sorts which are combination of different basic sorting algorithms. Introsort (std::sort in C++) which runs quick sort and switches to heap sort when the recursion gets too deep. This way, you get the fast performance of quick sort in practice while guaranteeing a worst case O(nlogn) run time.

Which sort is the fastest?

Quicksort is considered to be one of the fastest sorting algorithms. It is also considered to be the best sorting algorithm. Some of its features are that it is basically a comparison sort and can be done in-place in an array, however, inefficient implementation, it’s not a stable sort.

Though the worst-case complexity is O(n^2), on an average it gives us O(nlogn) time complexity. You can also think of considering Merge sort, which is very similar to Quicksort but has more complexity than quicksort.

When to use which sorting technique?
Q: Is the occurrence of the same element important?
Yes: Insertion, Bubble, Merge, Quick
No: Heap, Quick

Q: Is the data size small?
Yes: Insertion, Bubble
No: Heap, Merge, Quick

Q: Is memory for extra space an issue?
Yes: Insertion, Bubble, Heap
No: Merge, Quick*

Q: Is the input data nearly sorted?
Yes: Insertion, Bubble
No: Heap, Merge, Quick

Q: Is speed important?
Yes: Heap, Merge, Quick
No: Insertion, Bubble

We have three options in order to sort one million data — Heapsort, Merge Sort and Quicksort. Selecting the suitable sorting algorithm will still depend if occurrence of the same element is important and memory for extra space is not an issue.

Frequently Asked Questions

Summary

For more problems, you can also login to our practice platform and enhance your data structure and algorithm skills on CodeZen.

By Yogesh Kumar