Web Notes
2016.08.20
Using Liquid in Jekyll - Live with Demos
Liquid is a simple template language that Jekyll uses to process pages for your site. With Liquid you can output complex contents without additional plugins.
A short review on the common sorting algorithms, refresh, don’t forget anymore…
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 occasionally 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 (or vice versa).
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 through 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");
}
}
Save the codes to bubble.c and compile it with gcc:
gcc bubble.c
# run the program
./a.out
# example outputs
Input:
7 *******
19 *******************
23 ***********************
8 ********
10 **********
2 **
24 ************************
8 ********
23 ***********************
19 *******************
#1 iteration
7 *******
19 *******************
8 ********
10 **********
2 **
23 ***********************
8 ********
23 ***********************
19 *******************
24 ************************
#2 iteration
7 *******
8 ********
10 **********
2 **
19 *******************
8 ********
23 ***********************
19 *******************
23 ***********************
24 ************************
#3 iteration
7 *******
8 ********
2 **
10 **********
8 ********
19 *******************
19 *******************
23 ***********************
23 ***********************
24 ************************
#4 iteration
7 *******
2 **
8 ********
8 ********
10 **********
19 *******************
19 *******************
23 ***********************
23 ***********************
24 ************************
#5 iteration
2 **
7 *******
8 ********
8 ********
10 **********
19 *******************
19 *******************
23 ***********************
23 ***********************
24 ************************
#6 iteration
2 **
7 *******
8 ********
8 ********
10 **********
19 *******************
19 *******************
23 ***********************
23 ***********************
24 ************************
#7 iteration
2 **
7 *******
8 ********
8 ********
10 **********
19 *******************
19 *******************
23 ***********************
23 ***********************
24 ************************
#8 iteration
2 **
7 *******
8 ********
8 ********
10 **********
19 *******************
19 *******************
23 ***********************
23 ***********************
24 ************************
#9 iteration
2 **
7 *******
8 ********
8 ********
10 **********
19 *******************
19 *******************
23 ***********************
23 ***********************
24 ************************
Output:
2 **
7 *******
8 ********
8 ********
10 **********
19 *******************
19 *******************
23 ***********************
23 ***********************
24 ************************
Do the same compile then run process for the following examples. 🤝
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 of sorting algorithms. 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 next 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 through 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 through 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 through 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("merging: %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 – .
#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 through 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 through 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:
- Create 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 through 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;
}
Well, just learn and summarise these implementations, keep going… 🥳
THE END
Ads by Google
林宏
Frank Lin
Hey, there! This is Frank Lin (@flinhong), one of the 1.41 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
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 tunnelling between networks. It is developed by Microsoft and Cisco (primarily) for mobile users, and introduced as an updated version of IKEv1 in 2005. The IKEv2 MOBIKE (Mobility and Multihoming) protocol allows the client to main secure connection despite network switches, such as when leaving a WiFi area for a mobile data area. IKEv2 works on most platforms, and natively supported on some platforms (OS X 10.11+, iOS 9.1+, and Windows 10) with no additional applications necessary.
TOC
Ads by Google