 # Common sorting algorithms, understand and implemention in C

sorts of sorting algorithms

2017.04.24

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 = 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;
a = 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 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. 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? 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.