Common sorting algorithms, understand and implemention in C

Common sorting algorithms, understand and implemention in C

sorts of sorting algorithms

A short review on the common sorting algorithms, refresh, don’t forget…

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 as an efficient algorithm.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 settle down at the end of the array.

Take an unsorted array for example.

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

#define NUM 10  // array length for sorting
#define MAX 30  // max number in the array

int list[NUM];
void display();
void bubbleSort();

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

    bubbleSort();

    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;

    // loop through all numbers
    for (i = 0; i < NUM-1; i++) {
        bool 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("#%d iteration \n", i+1);
        display();
        printf("\n");
    }
}

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

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

Let’s take a look at the action:

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

#define NUM 10  // array length for sorting
#define MAX 30  // max number in the array

int list[NUM];
void display();
void insertionSort();

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

    insertionSort();

    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 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");
    }
}

Selection sort

Selection sort is also an in-place comparison based algorithm. The list (array) 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.

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

#define NUM 10  // array length for sorting
#define MAX 30  // max number in the array

int list[NUM];
void display();
void selectionSort();

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

    selectionSort();

    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 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");
    }
}

Merge sort

Merge sort is based on divide and conquer. In divide & conquer algorithm design paradigm, we divide the problems in sub-problems recursively then solve the sub-problems, and at last combine the solutions to find the final result.

In merge sort, first divides the array into halves. If the number of elements is odd, in the divide process, we will floor it. Until no more elements can be divided (the sub-array contains a single element), 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.

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

#define NUM 10  // array length for sorting
#define MAX 30  // max number in the array

int list[NUM];
void display();
void merging();
void sort();

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

    sort(0, NUM-1);

    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 merging(int left, int mid, int right) {
    int size = right - left + 1;
    int temp[NUM];
    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;
    // finding mid element
    if (left < right) {
        mid = left + (right - left) / 2;
        printf("sort: %d %d sort: %d %d \n", left, mid, mid+1, right);
        // recursively sorting both the halves
        sort(left, mid);
        sort(mid+1, right);

        printf("mergeing: %d %d %d \n", left, mid, right);
        merging(left, mid, right);
    }
}

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 – h=h3+1h = h*3 +1.

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

#define NUM 10  // array length for sorting
#define MAX 30  // max number in the array

int list[NUM];
void display();
void shellSort();

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

    shellSort();

    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 shellSort() {
    int i = 0, inner, outer, valueToInsert, interval = 1;
    while (interval < NUM/3) {
        interval = interval*3 + 1;
    }
    while (interval > 0) {
        // print sorting process
        display();
        printf("\n");

        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++;
    }
}

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.

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

#define NUM 10  // array length for sorting
#define MAX 30  // max number in the array

int list[NUM];
void display();
void quickSort();
void swap();
void sorting();
int partition();

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

    quickSort();

    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 quickSort() {
    sorting(0, NUM-1);
}

void swap(int num1, int num2) {
    int temp = list[num1];
    list[num1] = list[num2];
    list[num2] = temp;
}

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);
    }
}

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();
    printf("\n");

    return leftPointer;
}

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.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define NUM 10  // array length for sorting
#define MAX 30  // max number in the array

int list[NUM];
void display();
void heapify();
void adjust();
void sorting();
void heapSort();

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

    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 heapSort() {
    sorting(list, NUM);
}

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);
    }
}

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;
}
Ads by Google

林宏

Frank Lin

Hey, there! This is Frank Lin (@flinhong), one of the 1.4 billion 🇨🇳. This 'inDev. Journal' site holds the exploration of my quirky thoughts and random adventures through life. Hope you enjoy reading and perusing my posts.

YOU MAY ALSO LIKE

Using Liquid in Jekyll - Live with Demos

Web Notes

2016.08.20

Using Liquid in Jekyll - Live with Demos

Liquid is a simple templating language that Jekyll uses to process pages on your site. With Liquid you can output an modify variables, have logic statements inside your pages and loop over content.

Practising closures in JavaScript

JavaScript Notes

2018.12.17

Practising closures in JavaScript

JavaScript is a very function-oriented language. As we know, functions are first class objects and can be easily assigned to variables, passed as arguments, returned from another function invocation, or stored into data structures. A function can access variable outside of it. But what happens when an outer variable changes? Does a function get the most recent value or the one that existed when the function was created? Also, what happens when a function invoked in another place - does it get access to the outer variables of the new place?

Setup an IKEv2 server with StrongSwan

Tutorials

2020.01.09

Setup an IKEv2 server with StrongSwan

IKEv2, or Internet Key Exchange v2, is a protocol that allows for direct IPSec tunneling between two points. In IKEv2 implementations, IPSec provides encryption for the network traffic. IKEv2 is natively supported on some platforms (OS X 10.11+, iOS 9.1+, and Windows 10) with no additional applications necessary, and it handles client hiccups quite smoothly.

TOC