site logo

by Frank Lin in Programming
2017-04-24 18 minutes to read 1 views 0 comments

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

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
#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);
}
algorithm sorting