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 settles down at the end of the array.

Take an unsorted array for example.

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:

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.

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.

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$.

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.

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.

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
intlist[NUM];voiddisplay();voidbubbleSort();voidinsertionSort();voidselectionSort();voidmergeSort();voidshellSort();voidquickSort();voidheapSort();intmain(){for(inti=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();}voiddisplay(){// navigate througt all numbersfor(inti=0;i<NUM;i++){printf("%2d ",list[i]);for(intj=0;j<list[i];j++){printf("*");}printf("\n");}}voidbubbleSort(){inti,j,temp;boolswapped=false;// loop through all numbersfor(i=0;i<NUM-1;i++){swapped=false;// loop through numbers falling aheadfor(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 sortedif(!swapped){break;}}// print the sorting processprintf("Iteration #%d: \n",i+1);display();printf("\n");}}voidinsertionSort(){inti,valueToInsert,holePosition;// loop through all numbersfor(i=0;i<NUM;i++){// select the value to be insertedvalueToInsert=list[i];// select the hole position where the number is to be insertedholePosition=i;// check if previous number is larger than the number to be insertedwhile(holePosition>0&&list[holePosition-1]>valueToInsert){list[holePosition]=list[holePosition-1];holePosition--;}if(holePosition!=i){list[holePosition]=valueToInsert;}// print the sorting processprintf("Iteration #%d: \n",i+1);display();printf("\n");}}voidselectionSort(){inti,j,indexMin,temp;// loop through all numbersfor(i=0;i<NUM-1;i++){// set current number as minimumindexMin=i;// check the number is the minimumfor(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 processprintf("Iteration #%d: \n",i+1);display();printf("\n");}}voidmergeSort(){voidmerging(intleft,intmid,intright){intsize=right-left+1;inttemp[size];inti,l1,l2;for(l1=left,l2=mid+1,i=left;l1<=mid&&l2<=right;i++){if(list[l1]<=list[l2])temp[i]=list[l1++];elsetemp[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 processdisplay();printf("\n");}voidsort(intleft,intright){intmid;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);}voidshellSort(){inti=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++;}}voidquickSort(){voidswap(intnum1,intnum2){inttemp=list[num1];list[num1]=list[num2];list[num2]=temp;}intpartition(intleft,intright,intpivot){intleftPointer=left-1;intrightPointer=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();returnleftPointer;}voidsorting(intleft,intright){if(right-left<=0){return;}else{intpivot=list[right];intpartitionPoint=partition(left,right,pivot);sorting(left,partitionPoint-1);sorting(partitionPoint+1,right);}}sorting(0,NUM-1);}voidheapSort(){voidheapify(inta[],intn){inti,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;}}voidadjust(inta[],intn){inti,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;}voidsorting(inta[],intn){inti,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);}

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.

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 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?