Sorting

Bubble sort

• Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case complexity is quite high.

Procedure ↓

Pseudo code ↓

                
void bubbleSort(int A[], int n)
{
    for(i = 0; i < n - 1; i++)
    {
        for(j = 0; j < n - 1 - i; j++)
        {
            if(A[j]> A[j+1])
                swap(A[j], A[j+1]);
        }
    }
}
                
            

• Bubble sort is not adaptive, means that if the array is already sorted then there should be not more than 1 passes.
• We have to make it adaptive using a flag variable ↓

                
void bubbleSort(int A[], int n)
{
    int flag;
    for(i = 0; i < n - 1; i++)
    {
        flag = 0;
        for(j = 0; j < n - 1 - i; j++)
        {
            if(A[j]> A[j+1])
            {
                swap(A[j], A[j+1]);
                flag = 1;
            }
        }
        if(flag == 0) break;
    }
}
                
            

Program code ↓

                   
#include <stdio.h>
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void bubbleSort(int A[], int n)
{
    int i, j, flag;
    for (i = 0; i < n - 1; i++)
    {
        flag = 0;
        for (j = 0; j < n - 1 - i; j++)
        {
            if (A[j] > A[j + 1])
            {
                swap(&A[j], &A[j + 1]);
                flag = 1;
            }
        }
        if (flag == 0)
            break;
    }
}
int main()
{
    int A[] = {3, 7, 9, 10, 6, 5, 12, 4, 11, 2}, n = 10, i;
    bubbleSort(A, n);
    printf("The sorted array : ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}
                   
               

Selection sort

• This algorithm also sorts the element in passes, in each pass one element will be sorted. Just like bubble sort in selection sort for n element n - 1 passes are required.

Procedure ↓

Algorithm / Psuedo code ↓

                
void selectionSort(int A[], int n)
{
    int i, j, k;
    for(i = 0; i < n - 1; i++)
    {
        for(j = k = i; j < n; j++)
        {
            if(A[j] < A[k])
                k = j;
        }
        swap(A[i], A[k]);
    }
}
                
            

Program code ↓

                   
#include<stdio.h>
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selectionSort(int A[], int n)
{
    int i, j, k;
    for (i = 0; i < n - 1; i++)
    {
        for (j = k = i; j < n; j++)
        {
            if (A[j] < A[k])
                k = j;
        }
        swap(&A[i], &A[k]);
    }
}
int main()
{
    int A[] = {11, 12, 7, 2, 6, 9, 4, 5, 10, 3}, n = 10, i;
    selectionSort(A, n);
    printf("\nDisplay the sorted array : ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    return 0;
}
                   
               

Insertion Sort

• Before insertion sort we should know insertion of an element in a sorted array.
  

Procedure ↓

• For n number of element there are n-1 passes.
• Insertion is designed for linked list.

Algorithm / Psuedo code ↓

                
void insertionSort(int A[], int n)
{
    for(i = 1; i < n; i++)
    {
        j = i - 1;
        x = A[i];
        while(j > -1 && A[j]>x)
        {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = x;
    }
}
                
            

• The time complexity is O(n²).

Program code ↓

                   
#include <stdio.h>
void insertionSort(int A[], int n)
{
    int i, j, x;
    for (i = 1; i < n; i++)
    {
        j = i - 1;
        x = A[i];
        while (j > -1 && A[j] > x)
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = x;
    }
}
int main()
{
    int A[] = {11, 12, 7, 2, 6, 9, 4, 5, 10, 3}, n = 10, i;
    insertionSort(A, n);
    printf("\nDisplay the sorted array : ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    return 0;
}
                   
               

Quick Sort

Idea behind quick sort ↓

• Quick doesn't mean that this is the fastest sorting method.

Procedure ↓

The above procedure is known as partitioning procedure in which pivot element is moved to sorted place.
So quick sort uses partitioning procedure for sorting the elements and also it is recursive. So in code we will write the partitioned procedure and then quick sort procedure.

Partitioning algorithm ↓

                
int partition(int A[], int l, int h)
{
    int pivot = A[l];
    int i = l, j = h;
    do
    {
        do{i++;} while(A[i] <= pivot);
        do{j--;} while(A[j] > pivot);
        if(i < j)
            swap(A[i], A[j]);
    } while(i < j);
    swap(A[l], A[j]);
    return j;
}
                
            

Best case → If partitioning is done in middle. O(nlogn)
Worst case → If partitioning is on any end. O(n²) (already sorted)

Program code ↓

                   
#include <stdio.h>
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int partition(int A[], int l, int h)
{
    int pivot = A[l];
    int i = l, j = h;
    do
    {
        do
        {
            i++;
        } while (A[i] <= pivot);
        do
        {
            j--;
        } while (A[j] > pivot);
        if (i < j)
            swap(&A[i], &A[j]);
    } while (i < j);
    swap(&A[l], &A[j]);
    return j;
}
void quickSort(int A[], int l, int h)
{
    int j;
    if (l < h)
    {
        j = partition(A, l, h);
        quickSort(A, l, j);
        quickSort(A, j + 1, h);
    }
}
int main()
{
    int A[] = {11, 13, 7, 12, 16, 9, 24, 5, 10, 3}, n = 10, i;
    quickSort(A, 0, n);
    printf("\nDisplay the sorted array : ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    return 0;
}
                   
               

Merge Sort

Merging two array in a single array

• Merging is a process of combining two sorted list into a single sorted list

• In the last iteration there will be some elements that will be remaining to be added to C array and definitly this is going to happen if m and n are not equal.

Algorithm ↓

                    
void merge(int A[], int B[], int m, int n)
{
    int i, j, k;
    i = k = 0;
    while(i < m && j < n)
    {
        if(A[i] < B[j])
            C[k++] = A[i++];
        else 
            C[k++] = B[j++];
    }
    // now this is for if there are some remaining elements
    for(; i < m; i++)
        C[k++] = A[i];
    for(; j < n; j++)
        C[k++] = B[j];
    // either of 'for' loop will execute
}
                    
                

Merging two list which is in single array

• Now we have to update the previously written algorithm for single array.

                    
void merge(int A[], int l, int mid, int h)
{
    int i, j, k;
    i = l;
    j = mid + 1;
    k = l;
    // we need array to merge into 
    int B[h + 1];
    while(i < mid && j <= h)
    {
        if(A[i] < A[j])
            B[k++] = A[i++];
        else 
            B[k++] = A[j++];
    }

    for(; i <= mid; i++)
        B[k++] = A[i];
    for(; j <= h; j++)
        B[k++] = A[j];
    
    // now all the elements should be copied back to array A
    for(i = l; i <= h; i++) A[i] = B[i];
}
                    
                

• Now this modified code works for single array now.
• In merge sort we will utilize this technique.