Best Sorting Algorithms used in Data Structures | Learn Data Structures and Algorithms

Welcome back Programmers, Previously we learned some very useful and basic operations in a 1D array. In this post, we are going to explore the 3 most valuable Sorting techniques/algorithms that are not only simple to understand but also give us knowledge about other important aspects of coding, like time complexity and space complexity.

These Algorithms include:

• Bubble Sort
• Insertion Sort 
• Selection Sort

----------------------------------------------

1. Bubble Sort: It is the most simple sorting algorithm that repeatedly iterates through every element in the array and swapping the adjacent elements, by comparing them. And swaps the elements if they are not in proper arrangement/order. Thus giving us a sorted array of elements.

HOW IT WORKS: Firstly we compare the first two elements of the array and if the element at the 1st index is greater than the element at the 2nd index, then their positions are swapped. And then the so formed array in 2nd pass, that array's 2nd, and 3rd elements are compared and again swapped if the 2nd element is greater than the 3rd element. And so on.

#include<stdio.h>

int main()

{

    int i,temp,p,c,n,count=-1,c1=-1,c2=-1;

    int a[100];

    printf("enter the size of array\n");

    scanf("%d",&n);

    for(i=0;i<n;i++)

    scanf("%d",&a[i]);

    for(p=0;p<n-1;p++)

    { c2++;

        for(c=0;c<n-1-p;c++)

        { c1++;

            if(a[c]>a[c+1])

            { count++;

                temp=a[c];

                a[c]=a[c+1];

                a[c+1]=temp;

            }

        }

    }

    printf("\n the sorted array is:");

    for(i=0;i<n;i++)

    printf("%d ",a[i]);

    printf("\n the number of passes = %d",c2);

    printf("\n the number of comparisons = %d",c1);

    

    printf("\n the number of total swaps = %d",count);

    return 0;

}

* Here we can also come to know about the total number of passes and comparisons.

Properties of Bubble sort are:

Worst and Average Case Time Complexity: O(n^2). The worst case occurs when the array is sorted in opposite direction.

Best Case Time Complexity:  O(n). The best-case occurs when the array is already sorted.

Auxiliary Space:  O(1)

----------------------------------------------

2. Insertion Sort: In this sorting technique we have to consider the given array as 2 lists, 1 sorted on the right side of the array and other unsorted, here we put 1 element on the right side, i.e sorted side, and then go on comparing each element on the left side to the element placed on the right side and then giving the element a position based on the comparison.

HOW IT WORKS :

#include<stdio.h>

int main()

{  int i, j, size, temp, number[25];

   printf("Enter size: ");

   scanf("%d",&size);

   printf("Enter Elements \n");

   for(i=0;i<size;i++)

      scanf("%d",&number[i]);

   

   for(i=1;i<size;i++){

      temp=number[i];

      j=i-1;

      while((temp<number[j])&&(j>=0)){

         number[j+1]=number[j];

         j=j-1;

      }

      number[j+1]=temp;

   }

   printf("Sorted Array: ");

   for(i=0;i<size;i++)

      printf(" %d",number[i]);

   return 0;

}

Properties of Insertion sort are:

Worst and Average Case Time Complexity: O(n^2). The worst case occurs when the array is sorted in opposite direction.

Best Case Time Complexity: O(n). The best-case occurs when the array is already sorted.

Auxiliary Space: O(1)

----------------------------------------------

3. Selection Sort: This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list. The smallest element is selected from the unsorted array and inserted at the end of the sorted array. This process continues moving unsorted array boundary by one element to the right

HOW IT WORKS : 

loop for i=0 to i<size

   select the smallest among A[i], . . . , A[n]

   swap it with A[i];

end

#include <stdio.h>

int main()

{

    int array[10], i,j,a,b,temp size;

    printf("Enter Size");

    scanf("%d", &size);

    printf("Enter Elements");

    for (i = 0; i < size; i++)

        scanf("%d", &array[i]);

    for (i = 0 ;  i < size;i++)

    {

        for (j = i ; j < size; j++)

        {

            if (arr[i] > arr[j])

                {

                  temp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = temp;

                 }

        }

    }

    

    printf("\nSorted array is ");

    for (i = 0; i < size;i++)

        printf(" %d ", array[i]);

    return 0;

}

Properties of Selection sort are:

Worst and Average Case Time Complexity: O(n^2). The worst case occurs when the array is sorted in opposite direction.

Best Case Time Complexity: O(n^2). As in all cases, it will search minimum linearly for all n-1 iterations.

Auxiliary Space: O(1)