Various sorting algorithms and their complexities

Sorting is the operation to arrange an array and collection either in numerical order (Ascending or Descending ) or Alphabetical order. Here we will discuss Various sorting techniques and their time complexities. We will know which is the best sorting technique that you should use in competitive programming. There are various ways to sort an array here is the pseudo-code is given you can implement it in your respective language.

Best Sorting Algoritm

There are Lots of factors on which basis you can determine the best sorting algorithm.

1. Execution Time - The Algorithm should run in a definite time in its worst and average cases.

2. Space - The Algorithm should not be too bulky. It should take limited space.

3. No Repetition -  The algorithm should not repeat the already covered cases, which will make the code more efficient.

Types of Sorting

The Best sorting Techniques are as follows:

1. BUBBLE SORT 

This is the simplest of all sorting techniques present this is just the Brute Force Algorithm of sorting. As the name suggests, sorting happens like a bubble formation on a line. Each element is compared with its adjacent element and the swapped.

Time Complexity

Best Case -  Ω(n)

Average Case - θ(n^2)

Worst Case - O(n^2)

Implementation:-

 

 int n = array.length;

 for (int i = 0; i < n-1; i++)

 for (int j = 0; j < n-i-1; j++)

 if (arr[j] > arr[j+1])

 {

  int temp = arr[j];

  arr[j] = arr[j+1];

  arr[j+1] = temp;

  }

   

INSERTION SORT

This sorting technique is not as efficient as other techniques(heap and selection sort). In this, each element is compared with all other elements. This can be a good algorithm for a small data size.

Time Complexity

Best Case -  Ω(n)

Average Case - θ(n^2)

Worst Case - O(n^2)

Implementation -:

for(int i=0;i<array.length;i++)

{

int temp=array[i];

int j=i-1;

while(j>=0 && array[j]>temp)

{

array[j+1]=array[j];

j--;

}

array[j+1]=temp;

}

 

SELECTION SORT

In this sorting process, we repeatedly find the shortest element in the array by comparing each element one by and arranging them to get the sorted collection.

Time Complexity

Best Case -  Ω(n^2)

Average Case - θ(n^2)

Worst Case - O(n^2)

Implementation -:

for(int i=0;i<array.length;i++)

{

int min=i;

for(int j=i+1;j<n;j++)

{

if(array[j]<array[min])

{

min=j;

}

}

if(min!=i)

{

int temp=array[min];

array[min]=array[i];

array[i]=temp;

}

}

QUICK SORT

As the name suggests, It is one of the most efficient sorting techniques. It works on the divide and conquers Algorithm. We pick two pivots and take the median of them and sort the elements by partitioning the array at the median.

Time Complexity

Best Case - Ω(nlog(n))

Average Case - θ(nlog(n))

Worst Case - O(n^2)

Implementation -:

partion (array ,low,high)

{

pivot=array[low];

start=low;

end=high;

while(array[start]<pivot)

{

start++;

}

while(array[end]>pivot)

{

end--;

}

if(start<end)

{

int temp=array[start];

array[start]=array[end];

array[end]=temp;

}

}

so these are the best sorting algorithms discussed above you can optimize it more to make it more efficient and less complex.