Sorting Algorithms
“Any fool can write code that a computer can understand. Good programmers write code that humans can understand.”
– Martin Fowler
In today’s date more than 5 million applications use sorting methods to perform any task . Sorting methods that are widely used in today’s date are Quick Sort and Merge Sort. These two sorting methods have a good time complexity as compared to other sorting methods. So, here’s a short summary about these two algorithms.
Quick Sort
Best time complexity :- O(nlogn)
Worst time complexity :- O(n²) [Not good at all ]
Best space complexity :- O(logn)
Worst space complexity :- O(n)
Now, the worst time complexity of quick sort is not really good at all as we can see from here as it has a complexity of O(n²) which we can find even in sorting methods like selection sort , insertion sort and binary sort. We will discuss this broadly after the explanation of the two sorting algorithms.
Explanation of the quick sort
For an instance let us take an auxiliary array of 10 numbers.
Now in quick sort we maintain three pointers let them be left , right and Pivot.
left pointer is initialized at index 0.
right pointer is initialized at index 9 (which is the n-1 index).
Pivot is initialized at index 0.
Now the condition is like this: (This is just the pseudo code)
While(right>left)
{
While(data[left]<=data [Pivot])
++left;
While(data[right]>=data [Pivot])
- - right;
If(left<right)
Swap(data[left], data[right])
}
Swap(data[right],data[pivot])
1st Step: -As per the condition above our pivot ,left and right have moved
Step 2:-At 5 and 13 our left and right pointer respectively has stopped and now we moved to the 3rd line of the pseudo code and swapped them.
Step 3:- Now we again started the loop as the end condition is still not fulfilled as right>left. And our pointers now stopped at 20 and 0 respectively.
Step 4:- So we again swapped them up as per the 3rd condition of our while loop
Step 5:- Now our left and right pointers are at 20 and 0 and as we can see the right <left now so we have came out of the while loop
Step 6:- So as we are now out of the while loop we have the last statement to be executed which is to swap the value at pivot and right.
Step 7:- So now we have two partitions one is the partition_left which is from 0 to pivot-1 index and the partition_right is from pivot+1 to 9.
Now we will recursively do the same process over the partition_left and partition_right and achieve partition.
Sample code:-
#include<iostream>
using namespace std;
int part(int arr[],int l,int h);
void quicksort(int arr[],int l,int h)
{
if(l<h)
{
int p=part(arr,l,h);
quicksort(arr,l,p-1);
quicksort(arr,p+1,h);
}
}
int part(int arr[],int l,int h)
{
int pivot = arr[h];
int i = (l-1);
for (int j=l;j<=h-1;j++)
{
if (arr[j] <= pivot)
{
i++;
int temp2=arr[i];
arr[i]=arr[j];
arr[j]=temp2;
}
}
int temp=arr[i+1];
arr[i+1]=arr[h];
arr[h]=temp;
return (i + 1);
}
int main()
{
int arr[10]={6,10,15,2,20,0,5,30,15,4};
cout<<”Array before sorted: “;
for(int i=0;i<10;i++)
cout<<arr[i]<<” “;
cout<<”\nArray after sorted: “;
quicksort(arr,0,9);
for(int i=0;i<10;i++)
cout<<arr[i]<<” “;
}
Output:-
Merge Sort
Best time complexity :- O(nlogn)
Worst time complexity :- O(nlogn)
Best space complexity :- O(logn)
Worst space complexity :- O(n)
Now here we clearly see some improvement of merge sort over quick sort. The worst time complexity of merge sort is O(nlogn) which is far better than O(n²).
Explanation of the merge sort
Now let us take the array again which we used in the previous sorting method.
Now in merge sort we don’t need any type of pointers as merge sort typically works on dividing the size of the array by 2 on each step. So here we use a variable mid for the partitioning of the array.
Step 1: — Declare mid with the value (lower+upper)/2. And initialize
Lower at 0
Upper at 9 (n-1)
Step2 :- Now the condition will be as follows for the partition of the array
Void partition(int arr[],int l,int u) /*This is just the pseudo code*/
{
While(l<u)
{
int mid=(l+u)/2; /*l is lower and u is upper */
partition(arr,l,mid);
partition(arr,mid+1,u);
}
}
Step 3:- And in this way the partition goes on. The 1st partition goes on making partitions till l-u==1 or l>u. And same applies to the 2nd partition also.
Step 4: — All the elements gets distributed into single segments at the end of this process as shown by the graph clearly. Now we use merge function after that to merge all the partitions into a single point at the end. By taking 2 auxiliary arrays and storing them the elements into that.
Sample code:-
#include<iostream>
using namespace std;
void merge(int arr[],int f,int mid,int l)
{
int left=mid-f+1;
int right=l-mid;
int arr1[left],arr2[right];
for(int i=0;i<left;i++)
{
arr1[i]=arr[f+i];
}
for(int j=0;j<right;j++)
{
arr2[j]=arr[mid+1+j];
}
int u=0,v=0,k=f;
while(u<left && v<right)
{
if(arr1[u]<=arr2[v])
{
arr[k]=arr1[u];
u++;
}
else
{
arr[k]=arr2[v];
v++;
}
k++;
}
while(u<left)
{
arr[k] = arr1[u];
u++;
k++;
}
while(v<right)
{
arr[k]= arr2[v];
v++;
k++;
}
}
void split(int arr[],int f,int l)
{
if(f>=l)
return;
int mid=(f+(l-1))/2;
split(arr,f,mid);
split(arr,mid+1,l);
merge(arr,f,mid,l);
}
int main()
{
int arr[10]={6,10,15,2,20,0,5,30,15,4};
cout<<”Array before sorting : “;
for(int j=0;j<10;j++)
{
cout<<arr[j]<<” “;
}
split(arr,0,9);
cout<<”\nArray after sorting : “;
for(int j=0;j<10;j++)
{
cout<<arr[j]<<” “;
}
}
Output:-
My Opinion
Now we have discussed both the sorting methods very precisely . Now here I am going to share my opinion , which may vary from other’s opinions. After going through both of the sorting methods , I prefer merge sort for most of the time as it is good for all types of array be it an sorted one or be it in any unsorted array. It prefers good in all cases and gives a constant complexity of O(nlogn). So here is the conclusion, if anyone want to sort any general array where there is no special conditions like difference between elements is same or something then, it’s better to use merge sort as in maximum it would use a time complexity of O(nlogn) and space complexity of O(n).
Thank you,
Gud luck coders
