Sorting Algorithms and their running cost explained in detail with CPP.

Sorting Algorithms and their running cost explained in detail with CPP.

  • Post category:Coding
  • Reading time:10 mins read

What is a sorting algorithm and what it does?

As the name suggest an algorithm which is sorting something is called a sorting algorithm. And, that something could be anything, it just might be the natural numbers or a string of words or even any object variable like photos corresponding to their numbers or letters. Like when we add a contact to our mobile device or search something on Google it get sorted in an order which is coded in it.

Without sorting algorithms we can’t see the structured behaviour of the data that today we are dealing with or what we see on earth today from Computer System Processes, Concurrent Transactions that are happening all around the globe at the same time, Traffic Control, Super Complex Calculations done by the powerful CPUs to just buying something online, sorting applies everywhere. So it’s become important to choose the right Sorting Method at right time and on the right dataset so that we can outsource the results efficiently without wasting unnecessary resources.

Different Types of Sorting Algorithms.

With lots of years of research done by the super intelligent mathematicians and computer scientists all around the globe we today have lots of different sorting algorithms that all are efficient when applied on the right data.

So most important and commonly used sorting algorithms are:-

  1. Selection Sort
  2. Bubble Sort
  3. Insertion Sort
  4. Merge Sort
  5. Quick Sort
  6. Heap Sort
  7. Counting Sort
  8. Radix Sort
  9. Bucket Sort

These thirteen of the sorting algorithms are most common and we are going to study them in complete detail and the we will rank them on different data from worst to first. Let’s get started:

1. Selection Sort

This algorithm is quite simple and easy to understand. What we do here is a three steps simple process:

  • First we took the array and divide it into sorted and unsorted array within. Initially whole array is unsorted.
  • Second than what we do is create the passes and on first pass we select the smallest element of the array and put it to the sorted array within, then on the second pass after the first one we start just after the last element present in the sorted array.
  • And after n-1 number of passes (if the array consists of n number of elements in it) we finally placed all the smallest element one after the other in the sorted array.

Here is how the code Looks Like:

#include <iostream> 
using namespace std; 
  
void swap(int *index1, int *index2)  
{  
    int temp = *index1;  
    *index1 = *index2;  
    *index2 = temp;  
}  
  
void selection_sort(int arr[], int n)  
{  
    int i, j, min;  
  
    // One by one move boundary of unsorted subarray  
    for (i = 0; i < n-1; i++)  
    {  
        // Find the minimum element in unsorted array  
        min = i;  
        for (j = i+1; j < n; j++)  
        if (arr[j] < arr[min])  
            min = j;  
  
        // Swap the found minimum element with the first element  
        swap(&arr[min], &arr[i]);  
    }  
}  
  
/* Function to print an array */
void print(int arr[], int size)  
{  
    int i;  
    for (i=0; i < size; i++)  
        cout << arr[i] << " ";  
    cout << endl;  
}  
  
// Driver program to test above functions  
int main()  
{  
    int arr[] = {64, 25, 12, 22, 11};  
    int n = sizeof(arr)/sizeof(arr[0]);  
    selection_sort(arr, n);  
    cout << "Sorted array: \n";  
    print(arr, n);  
    return 0;  
}  

Let’s talk about the time and space complexity of the selection sort algotrithm:

Best Case: O(n2) [O(n2) – Comparison, O(1) – Swap ]

Average Case: O(n2) [O(n2) – Comparison, O(n) – Swap ]

Best Case: O(n2) [O(n2) – Comparison, O(n) – Swap ]

Worst Case Space: O(1) [Auxiliary Space]

Sorting In Place: Yes

Stable: No(However could be attained with stable selection sort)

2. Bubble Sort.

This algorithms works by swapping the adjacent elements several times in a pass. After each pass the largest element is pushed down to the array. On comparing the adjacent elements j and j+1, if j+1 is smaller than j then we will going to swap these to there respective indices and continue the same process when j becomes j+1 and j+1 becomes j+2.

Implementation of Bubble sort is as:

#include<iostream>

using namespace std;
int swap(int *index1, int* index2)
{
    int temp = * index1;
    *index1 = *index2;
    *index2 = temp;
    return 0;
}
int find_bubble_sort(int arr[], int n)
{
     for(int i=0; i<n-1; i++ )
     {
         for (int j=0; j<n-i-1; j++)
         {
             if (arr[j+1]<arr[j])
             {
                 swap(&arr[j],&arr[j+1]);

             }
         }
     }
     return 0;
}
int print(int arr[], int n)
     {
      for(int i=0; i<n; i++)
      {
          cout<<arr[i]<<" ";
      }   
      return 0;
     }
int main()
{
    int n, arr[1000],k;
    cout<<"Enter No of Elements";

    cin>>n;

    for(k=0; k<n; k++)
      cin>>arr[k];
    
    find_bubble_sort(arr,n);
    print(arr,n);
}

If array is of n elements then after n-1 passes the bubble sort algorithms is stopped here and it will be definitely sorted at the point but there are also chance that it doesn’t requires n-1 chances with every data. But, this algorithm only finishes when it completes total n-1 passes that is a disadvantage with bubble sort we will see in the next section how we can resolve this by updating a few lines of code.

Best Case: O(n2) [O(n2) – Comparison, O(1) – Swap ]

Average Case: O(n2) [O(n2) – Comparison, O(n2) – Swap ]

Worst Case: O(n2) [O(n2) – Comparison, O(n2) – Swap ]

Worst Case Space: O(1) [Auxiliary Space]

Sorting In Place: Yes

Stable: Yes

Optimized Bubble Sort:

Now think , if in the array we are passing already sorted elements then instead of going for n-1 passes our algorithm should stop at the very first pass. And, to implement this we are optimising above bubble sort algorithm as:

#include<iostream>

using namespace std;
int swap(int *index1, int* index2)
{
    int temp = * index1;
    *index1 = *index2;
    *index2 = temp;
    return 0;
}
int find_bubble_sort(int arr[], int n)
{    bool swapped;
     for(int i=0; i<n-1; i++ )
     {   swapped = false;
         for (int j=0; j<n-i-1; j++)
         {
             if (arr[j+1]<arr[j])
             {
                 swap(&arr[j],&arr[j+1]);
                 swapped = true;

             }
         }
       if(!swapped)
          break;
     }
     return 0;
}
int print(int arr[], int n)
     {
      for(int i=0; i<n; i++)
      {
          cout<<arr[i]<<" ";
      }   
      return 0;
     }
int main()
{
    int n, arr[1000],k;
    cout<<"Enter No of Elements";

    cin>>n;

    for(k=0; k<n; k++)
      cin>>arr[k];
    
    find_bubble_sort(arr,n);
    print(arr,n);
}

So, here on the above lines of code we are just restricting the algorithm to jump to another pass if the value of swapped remains false on the initial pass that means if the array is already sorted then why to go for n-1 passes if you can finalize it in single pass.

This optimized version of algorithm makes the Best Case time complexity of Bubble Sort to O(n).

3. Insertion Sort:-

This sorting algorithm is like a play of cards where player have to place it passing the previous cards. Here, in this algorithm we compare the element to its predecessor in the array and if the predecessor are greater then placing the element appropiately at the right position in the Index.

This algorithm involves 3 simple step to work with and they are as follow:

  • First, choose the key index let say arr[i] where i starts from 1 to n.
  • Then comparing the key to the predecessors lets arr[j] where j starts in reverse from i-1 until 0.
  • Now, placing the smallest element to the top of the array. On doing this n-1 times with the outer loop we got the elements sorted.

Here is the code for Insertion Sort:

#include<iostream>
using namespace std;
int print(int arr[], int n)
     {
      for(int i=0; i<n; i++)
      {
          cout<<arr[i]<<" ";
      }   
      return 0;
     }
int insertion_sort(int arr[], int n)
{
   int i,j,key;
   for(i=1; i<n; i++)
  {
       key = arr[i];
       j=i-1;
       while(j>=0 && arr[j]>key)
          {
               arr[j+1]=arr[j];
               j=j-1;
          }
       arr[j+1]=key;
  }

print(arr,n);
return 0;
}
int main()
{
   int k,n,arr[10000];
   cout<<"Enter No. of elements in the array:";
   cin>>n;
   for(k=0; k<n; k++)
    {
        cin>>arr[k];
    }
   insertion_sort(arr,n);
}

Time Complexity: O(n2)

Auxiliary Space: O(1)

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

Algorithmic Paradigm: Incremental Approach

Sorting In Place: Yes

Stable: Yes

Online: Yes

Uses: Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

4. Merge Sort:-

Merge Sort algorithm is based on divide and conquer strategy. In merge sort a whole array is divided into half and half unless they can’t be divided anymore. Two indices are selected “l-very fist index of array” , “n last index of an array” and with those we divide the array from index “m=l+(n-1)/2” and pass the subsequent subarrays to the same function through recursion.

Algorithm for Merge Sort works as:

merge_sort(arr[], l,  n)
If n > l
     1. Find the middle point to divide the array into two halves:  
             middle m = l+ (n-l)/2
     2. Call merge_sort for first half:   
             Call merge_sort(arr, l, m)
     3. Call merge_sort for second half:
             Call merge_sort(arr, m+1, n)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, n)
Else 
     Return;

Code for the merge sort is:

#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int n)
{
   int n1 = m - l + 1;
	int n2 = n - m;


	int L[n1], R[n2];


	for (int i = 0; i < n1; i++)
		L[i] = arr[l + i];
	for (int j = 0; j < n2; j++)
		R[j] = arr[m + 1 + j];

	
	int i = 0;

	
	int j = 0;


	int k = l;


	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}

	
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}

	
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}
void merge_sort(int arr[], int l, int n)
{   
	 if(l>=n){
		return;
	}
	int m =l+ (n-l)/2;
	merge_sort(arr,l,m);
	merge_sort(arr,m+1,n);
	merge(arr,l,m,n);
}
void printArray(int A[], int size)
{
	for (int i = 0; i < size; i++)
		cout << A[i] << " ";
}

int main()
{
	int k,arr[10000],n;
	cout<<"Enter No. of elements in the array:";

    cin>>n;
   for(k=0; k<n; k++)
    {
        cin>>arr[k];
    }
	merge_sort(arr, 0, n- 1);

	cout << "\nSorted array is \n";
	printArray(arr, n);
	return 0;
}

Auxiliary Space: O(n)
Algorithmic Paradigm: Divide and Conquer
Sorting In Place: No in a typical implementation
Stable: Yes
Time Complexity: Time complexity of Merge Sort is  O(nlogn) in all 3 cases (worst, average and best).

Want to learn JavaScript see our beginner tutorial on JavaScript.

Thank you so much if you are still here. We will see you in the next post with all remaining sorting techniques, till then take care and keep coding.

Share with others:)

This Post Has 2 Comments

  1. Dannie

    These are actually great ideas in on the topic of
    blogging. You have touched some good factors here. Any way keep up wrinting.

  2. Latesha

    My developer is trying to persuade me to move to .net from PHP.
    I have always disliked the idea because of the expenses.

    But he’s tryiong none the less. I’ve been using Movable-type on a variety of websites for about a year
    and am anxious about switching to another platform. I have heard good things about blogengine.net.
    Is there a way I can transfer all my wordpress posts into it?
    Any kind of help would be really appreciated!

Leave a Reply