Complete Information on sorting algorithms in c

In this article, you will find Sorting Algorithms in C with examples and outputs.

Sorting Algorithms In C

Sorting Algorithms In C

Sorting means arranging the elements in some meaningful ordered sequence so that it is easy to understand, analyze, view, and process.

Sorting is one of the most important topic from the exam as well as a competitive programming point of view.

Selection Sort

Selection Sort algorithm sorts an array by putting the smallest element in the beginning.

Let’s Understand Selection Sort by an example:-

Let’s take an array a[] = 10 7 5 6 4

  • 1st Iteration: Find a minimum element in a[0 . . . 4] and put it at a[0] 4 7 5 6 10
  • 2nd Iteration: Find a minimum element in a[1 . . . 4] and put it at a[1] 4 5 7 6 10
  • 3rd Iteration: Find a minimum element in a[2 . . . 4] and put it at a[2] 4 5 6 7 10
  • 4th Iteration: Find a minimum element in a[3 . . . 4] and put it at a[3] 4 5 6 7 10

Worst, Average, Best Case Time Complexity = O(n2)

Auxiliary Space = O(1)

/*sorting-selection*/
#include<stdio.h>
void main(){
      int n,a[10],i,j,temp;
      printf("Enter the size of array: ");
      scanf("%d",&n);
      printf("Enter the value of array: ");
      for(i=0;i<n;i++)
      scanf("%d",&a[i]);
      for(i=0;i<n;i++){
            for(j=i+1;j<n;j++){
                  if(a[i]>a[j]){
                        temp=a[i];
                        a[i]=a[j];
                        a[j]=temp;
                        }
            }
      }
      printf("Array after Selection Sorting:\n");
      for(i=0;i<n;i++)
      printf("%d\t",a[i]);
      }


      

OUTPUT

Enter the size of array: 5
Enter the value of array: 3 6 8 4 2
Array after Selection Sorting:
2	3	4	6	8

Bubble Sort

Bubble Sort algorithm is the most simple sorting algorithms in C. It sorts an array by swapping the adjacent elements if they are in the wrong order.

Let’s Understand Bubble Sort by an example:-

Let’s take an array a[] = 10 7 5 6 4

  • 1st Iteration: 7 10 5 6 4 -> 7 5 10 6 4 -> 7 5 6 10 4 -> 7 5 6 4 10
  • 2nd Iteration: 5 7 6 4 10 -> 5 6 7 4 10 -> 5 6 4 7 10
  • 3rd Iteration: 5 6 4 7 10 -> 5 4 6 7 10

Worst and Average Case Time Complexity = O(n2)

Best Case Time Complexity = O(n)

Auxiliary Space = O(1)

/*sorting-bubble*/
#include<stdio.h>
        void main(){
        int i,j,n,a[10],temp;
        printf("Enter the size of array: ");
        scanf("%d",&n);
        printf("Enter the value of array: ");
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        for(i=0;i<n;i++){
            for(j=0;j<n-i-1;j++){
                if(a[j]>a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        printf("Array after Bubble Sorting:\n");
        for(i=0;i<n;i++)
        printf("%d\t",a[i]);
        }

OUTPUT

Enter the size of array: 5
Enter the value of array: 3 6 8 4 2
Array after Bubble Sorting:
2	3	4	6	8

Insertion Sort

Insertion Sort algorithm sorts an array by taking an element and iterating through the array to find its correct position in the sorted array.

Let’s Understand Insertion Sort by an example:-

There is an array a[] = 11 10 13 2 3

  • 1st Iteration: 10 11 13 2 3
  • 2nd Iteration: 10 11 13 2 3
  • 3rd Iteration: 2 10 11 13 3
  • 4th Iteration: 2 3 10 11 13

Worst and Average Case Time Complexity = O(n2)

Best Case Time Complexity = O(n)

Auxiliary Space = O(1)

/*sorting-insertion*/ 
#include<stdio.h>
void main() {
  int i, j, n, a[10], temp;
  printf("Enter the size of array: ");
  scanf("%d", & n);
  printf("Enter the value of array: ");
  for (i = 0; i < n; i++)
    scanf("%d", & a[i]);
  for (i = 1; i < n; i++) {
    temp = a[i];
    j = i - 1;
    while (temp < a[j] && j >= 0) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = temp;
  }
  printf("Array after Insertion Sorting:\n");
  for (i = 0; i < n; i++)
    printf("%d\t", a[i]);
}

OUTPUT

Enter the size of array:5
Enter the value of array: 3 6 8 4 2
Array after Insertion Sorting:
2	3	4	6	8

Merge Sort

Merge Sort is a divide and conquer algorithm. It divides the input array into two halves. Recursively calls itself for the two halves than use merge() method to merge both the sorted halves. This algorithm has the least time complexity in the worst case as compared to other sorting algorithms in C.

Merge Sort Algorithm
  1. First of all, read the array length and array from the user.
  2. If the array is of length 0 or 1, then it is already sorted.
  3. Divide the list recursively into two halves until it can no more be divided.
  4. Use the merge sort algorithm recursively to sort each sub-array.
  5. Merge the smaller lists into a new list in sorted order.

Worst, Average, Best Case Time Complexity = O( nLogn )

Auxiliary Space = O(n)

#include <stdio.h>

int a[10];
int b[10];

void merge(int low, int mid, int high) {
  int l1, l2, i;

  for (l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
    if (a[l1] <= a[l2])
      b[i] = a[l1++];
    else
      b[i] = a[l2++];
  }

  while (l1 <= mid)
    b[i++] = a[l1++];

  while (l2 <= high)
    b[i++] = a[l2++];

  for (i = low; i <= high; i++)
    a[i] = b[i];
}

void sort(int low, int high) {
  int mid;
  if (low < high) {
    mid = (low + high) / 2;
    sort(low, mid);
    sort(mid + 1, high);
    merge(low, mid, high);
  } else {
    return;
  }
}

int main() {
  int i, n;
  printf("Enter the size of array: ");
  scanf("%d", & n);
  printf("Enter the value of array: ");
  for (i = 0; i < n; i++)
    scanf("%d", & a[i]);

  printf("Before sorting\n");

  for (i = 0; i < n; i++)
    printf("%d ", a[i]);
  printf("\n");
  sort(0, n - 1);

  printf("After sorting\n");

  for (i = 0; i < n; i++)
    printf("%d ", a[i]);
}

OUTPUT

Enter the size of array: 5
Enter the value of array: 3 6 8 4 2
Before sorting
3 6 8 4 2 
After sorting
2 3 4 6 8

Quick Sort

Quicksort is a divide and conquer algorithm. It partitions the complete array around the pivot element. Pivot element can be picked in multiple ways : –

  • First Element as the pivot
  • Last Element as the pivot
  • Median Element as the pivot
  • The Random element as pivot
Quick Sort Algorithm
  1. In this Algorithm, we select the element at the first index as a pivot element.
  2. Define two variables i and j. Set i and j to the first and last elements of the list respectively. These variables will be used to represent the index of the element in the list.
  3. Keep on Increasing i until list[i] > pivot then stop.
  4. keep on decreasing j until list[j] < pivot then stop.
  5. If i < j then swap list[i] and list[j].
  6. Repeat 3rd,4th, and 5th steps in a loop until i > j.
  7. Exchange the pivot element with the list[j] element.
  8. Finally, a sorted list will be obtained.

Worst Case Time Complexity = O(n2)

Average, Best Case Time Complexity = O( nLogn )

Auxiliary Space = O(n)

#include<stdio.h>

void quicksort(int a[25], int first, int last) {
  int i, j, pivot, temp;

  if (first < last) {
    pivot = first;
    i = first;
    j = last;

    while (i < j) {
      while (a[i] <= a[pivot] && i < last)
        i++;
      while (a[j] > a[pivot])
        j--;
      if (i < j) {
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
      }
    }

    temp = a[pivot];
    a[pivot] = a[j];
    a[j] = temp;
    quicksort(a, first, j - 1);
    quicksort(a, j + 1, last);

  }
}

int main() {
  int i, n, a[25];

  printf("Enter the size of Array: ");
  scanf("%d", & n);

  printf("Enter Array Elements: ", n);
  for (i = 0; i < n; i++)
    scanf("%d", & a[i]);

  quicksort(a, 0, n - 1);

  printf("After Quick Sort: ");
  for (i = 0; i < n; i++)
    printf("%d\t", a[i]);

  return 0;
}

OUTPUT

Enter the size of Array: 5
Enter Array Elements: 3 6 8 4 2
After Quick Sort: 2	3	4	6	8

You may also like:-

Basic C Programs

Good Programming Languages to learn

Leave a Comment

Your email address will not be published. Required fields are marked *