Common sorting algorithms, understand and implemention in C

Common sorting algorithms, understand and implemention in C

Bubble sort

Although bubble sort is rarely used in practise, it is one of the simplest sorting algorithms to understand and implement. When the input is usually in sorted order but occasionlly have some out-of-order elements, bubble sort can also be employed.1

This sorting algorithm is based on comparison algorithm. By comparing each pair of adjacent elements and swapped them if they are not in order. After every iteration, the highest values settles down at the end of the array.

Take an unsorted array for example.

Bubble sort

Insertion sort

Insertion sort is an in-place comparison based sorting algorithm. In most cases, a lower part of an array is maintained to be sorted, and an element is going to be inserted into this sorted sublist with appropriate place.

This is a simple implementation sorting algorithm. In real life, we use this algorithm (or similar) to sort cards in bridge hand.2

Insertion sort

In the program, using a while loop to maintain the sorted sub-list, and find the right place to insert the element:

while (holePosition > 0 && list[holePosition-1] > valueToInsert) {
    list[holePosition] = list[holePosition-1];
    holePosition--;
}
if (holePosition != i) {
    list[holePosition] = valueToInsert;
}

Selection sort

Selection sort is also an in-place comparison based algorithm. The list is divided into two parts (sorted and unsorted). Then the smallest element selected from the unsorted part and swapped with the leftmost element in the unsorted part, which also make this element to the rightmost place in the sorted part. Repeat this process to put the smallest element in the unsorted part to the last place of the sorted part.

Selection sort

Merge sort

Merge sort is based on divide and conquer.

First divides the array into halves. If the number of elements is odd, in the divide process, we will floor it.

Untill no more elements can be diveded, we combine them in exactly the same manner as they were broken down. When combine two halves, we first compare the element for each list and store the elements in sorted order.

Merge sort

Shell sort

Shell sort is based on insertion sort, but spread the sort list in small pieces and then insertion sort them. To make the list into small pieces, an interval is used, and this interval is calculated based on Knuth’s formula – .

Shell Sort

Quick sort

Quick sort is an efficient sorting algorithm and is based on partitioning of array into smaller arrays.

A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

Quick sort

Heap sort

Heap sort is divided into two basic parts:

  • Creating a heap of unsorted list
  • Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array.

Heap sort

Implement in C

All the above sorting algorithms were involved in the following snippet:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define NUM 9  // array length for sorting
#define MAX 27  // max number in the array

int list[NUM];
void display();
void bubbleSort();
void insertionSort();
void selectionSort();
void mergeSort();
void shellSort();
void quickSort();
void heapSort();

int main()
{
    for (int i = 0; i < NUM; i++) {
        list[i] = rand() % MAX;
    }
    printf("Input: \n");
    display();
    printf("\n");

    // bubbleSort();
    // insertionSort();
    // selectionSort();
    mergeSort();
    // shellSort();
    // quickSort();
    // heapSort();
    printf("Output: \n");
    display();
}

void display()
{
    // navigate througt all numbers
    for (int i = 0; i < NUM; i++) {
        printf("%2d ", list[i]);
        for (int j = 0; j < list[i]; j++) {
            printf("*");
        }
        printf("\n");
    }
}

void bubbleSort()
{
    int i, j, temp;
    bool swapped = false;

    // loop through all numbers
    for (i = 0; i < NUM-1; i++) {
        swapped = false;

        // loop through numbers falling ahead
        for (j = 0; j < NUM-1-i; j++) {
            // check if next number is less than current number
            // swap the numbers (bubble up)
            if (list[j] > list[j+1]) {
                temp = list[j];
                list[j] = list[j+1];
                list[j+1] = temp;
                swapped = true;
            } else {
                swapped = true;
            }
            // if no numbers was swapped that means array is sorted
            if (!swapped) {
                break;
            }
        }
        // print the sorting process
        printf("Iteration #%d: \n", i+1);
        display();
        printf("\n");
    }
}

void insertionSort()
{
    int i, valueToInsert, holePosition;

    // loop through all numbers
    for (i = 0; i < NUM; i++) {
        // select the value to be inserted
        valueToInsert = list[i];
        // select the hole position where the number is to be inserted
        holePosition = i;

        // check if previous number is larger than the number to be inserted
        while (holePosition > 0 && list[holePosition-1] > valueToInsert) {
            list[holePosition] = list[holePosition-1];
            holePosition--;
        }
        if (holePosition != i) {
            list[holePosition] = valueToInsert;
        }
        // print the sorting process
        printf("Iteration #%d: \n", i+1);
        display();
        printf("\n");
    }
}

void selectionSort()
{
    int i, j, indexMin, temp;

    // loop through all numbers
    for (i = 0; i < NUM-1; i++) {
        // set current number as minimum
        indexMin = i;
        // check the number is the minimum
        for (j = i+1; j < NUM; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }

        if (indexMin != i) {
            temp = list[indexMin];
            list[indexMin] = list[i];
            list[i] = temp;
        }
        // print the sorting process
        printf("Iteration #%d: \n", i+1);
        display();
        printf("\n");
    }
}

void mergeSort()
{
    void merging(int left, int mid, int right) {
        int size = right - left + 1;
        int temp[size];
        int i, l1, l2;
        for (l1 = left, l2 = mid + 1, i = left; l1 <= mid && l2 <= right; i++) {
            if (list[l1] <= list[l2])
                temp[i] = list[l1++];
            else
                temp[i] = list[l2++];
        }
        while (l1 <= mid)
            temp[i++] = list[l1++];
        while (l2 <= right)
            temp[i++] = list[l2++];
        for (i = left; i <= right; i++)
            list[i] = temp[i];
        // print the sorting process
        display();
        printf("\n");
    }
    void sort(int left, int right) {
        int mid;
        if (left < right) {
            mid = (left + right) / 2;
            printf("sort: %d %d sort: %d %d \n", left, mid, mid+1, right);
            sort(left, mid);
            sort(mid+1, right);
            printf("mergeing: %d %d %d \n", left, mid, right);
            merging(left, mid, right);
        }
    }
    sort(0, NUM-1);
}

void shellSort()
{
    int i = 0, inner, outer, valueToInsert, interval = 1;
    while (interval < NUM/3) {
        interval = interval*3 + 1;
    }
    while (interval > 0) {
        // print sorting process
        // display();

        for (outer = interval; outer < NUM; outer++) {
            valueToInsert = list[outer];
            inner = outer;
            while (inner > interval - 1 && list[inner - interval] >= valueToInsert) {
                list[inner] = list[inner - interval];
                inner -= interval;
            }
            list[inner] = valueToInsert;
        }
        interval = (interval - 1) / 3;
        i++;
    }
}

void quickSort()
{
    void swap(int num1, int num2) {
        int temp = list[num1];
        list[num1] = list[num2];
        list[num2] = temp;
    }
    int partition(int left, int right, int pivot) {
        int leftPointer = left -1;
        int rightPointer = right;

        while (true) {
            while(list[++leftPointer] < pivot) {}
            while(rightPointer > 0 && list[--rightPointer] > pivot) {}
            if (leftPointer >= rightPointer) {
                break;
            } else {
                swap(leftPointer, rightPointer);
            }
        }

        swap(leftPointer, right);
        // print sorting process
        // display();
        return leftPointer;
    }
    void sorting(int left, int right) {
        if (right-left <= 0) {
            return;
        } else {
            int pivot = list[right];
            int partitionPoint = partition(left, right, pivot);
            sorting(left, partitionPoint - 1);
            sorting(partitionPoint + 1, right);
        }
    }
    sorting(0, NUM-1);
}

void heapSort()
{
    void heapify(int a[], int n) {
        int i, j, k, item;
        for (k = 1; k < n; k++) {
            item = a[k];
            i = k;
            j = (i-1)/2;
            while (i > 0 && item > a[j]) {
                a[i] = a[j];
                i = j;
                j = (i-1)/2;
            }
            a[i] = item;
        }
    }
    void adjust(int a[], int n) {
        int i, j, item;
        j = 0;
        item = a[j];
        i = 2*j + 1;
        while (i <= n-1) {
            if (i+1 <= n-1) {
                if (a[i] < a[i+1]) {
                    i++;
                }
            }
            if (item < a[i]) {
                a[j] = a[i];
                j = i;
                i = 2*j +1;
            } else {
                break;
            }            
        }
        a[j] = item;
    }
    void sorting(int a[], int n) {
        int i, t;
        heapify(a, n);
        for (i = n - 1; i > 0; i--) {
            t = a[0];
            a[0] = a [i];
            a[i] = t;
            adjust(a, i);
        }
    }
    sorting(list, NUM);
}

Ref:

avatar

Frank Lin

Code learning...

Say something Login