loading...

Basic Sorting

giladri profile image Gilad Ri ・4 min read

C-mpler (13 Part Series)

1) C-mpler Introduction 2) Basic Variables & Operators 3 ... 11 3) Intro to I/O 4) Conditions 5) Practice #1 6) Loops 7) Compilation & Precompilation 8) Static Arrays 9) Practice #2 10) Memory Addresses & Pointers 11) Memory Allocation & Dynamic Arrays 12) Basic Sorting 13) Recursion

Let's say we have the following code:

#include <stdio.h>
#include <limits.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10
#define SUCCESS 0
#define TRUE 1
#define FALSE 0

void swap(int* x, int* y) {
    *x += *y;
    *y = *x - *y;
    *x -= *y;
}

void printArray(int* arr, int size) {
    int i = 0;
    printf("%d", arr[0]);
    for (i = 1; i < size; i++) {
        printf(", %d", arr[i]);
    }
    printf("\n");
}

void buildRandomArray(int* arr, int size) {
    // Builds a random integers array which its elements are between 0 and 100
    for (int i = 0; i < size; i++) {
        arr[i] = rand() % 100;
    }
}

int main() {
    // Random seed
    srand(time(NULL));
    // Builds a random array
    int size = SIZE;
    int* arr = (int*)malloc(size * sizeof(int));
    buildRandomArray(arr, size);

    // TODO: Sort the array <-- INSERT THE FUNCTION CALL HERE

    // Prints the array
    printArray(arr, SIZE);
    // Success
    return SUCCESS;
}

which builds a random array of integers and then prints it. (Make sure you understand the code). However, we want to sort the array before it is printed. How can we do so?

We will see in this post 3 different basic algorithms that can perform the task:

Selection Sort

In each iteration i (starts from 0), the Selection Sort algorithm finds the minimum element and swaps it with the element which is in the i position of the array right now. The code:

void selectionSort(int* arr, int size) {
    int minValue, minIndex = 0;
    for (int i = 0; i < size; i++) {
        // Sets the minimum value to be the maximum int size at the beginning of each iteration
        minValue = INT_MAX;
        for (int j = i; j < size; j++) {
            if (arr[j] <= minValue) {
                // Saves the minimum value and its index
                minValue = arr[j];
                minIndex = j;
            }
        }
        // Swaps only if the indexes are different
        if (i != minIndex) {
            swap(&arr[i], &arr[minIndex]);
        }
    }
}

For example:

45, 87, 23, 11, 43, 23, 76, 28, 18, 7
7, 87, 23, 11, 43, 23, 76, 28, 18, 45
7, 11, 23, 87, 43, 23, 76, 28, 18, 45
7, 11, 18, 87, 43, 23, 76, 28, 23, 45
7, 11, 18, 23, 43, 23, 76, 28, 87, 45
7, 11, 18, 23, 23, 43, 76, 28, 87, 45
7, 11, 18, 23, 23, 28, 76, 43, 87, 45
7, 11, 18, 23, 23, 28, 43, 76, 87, 45
7, 11, 18, 23, 23, 28, 43, 45, 87, 76
7, 11, 18, 23, 23, 28, 43, 45, 76, 87
7, 11, 18, 23, 23, 28, 43, 45, 76, 87

As you can see, we first placed 7 at the beginning of the array, and then we placed 11 and then 23 and so on.

Insertion Sort

In each iteration i (starts from 0), the Insertion Sort choose the i'th element as a pivot and found its place. In this way, after two loops the array is sorted: the outer loop is for the selection of the pivot and the inner loop is for placing the chosen pivot at its location.

void insertionSort(int* arr, int size) {
    int pivot;
    for (int i = 1; i < size; i++) {
        // Prints the array in each iteration
        printArray(arr, size);
        // Chooses a pivot for this iteration
        pivot = arr[i];
        // Swaps until the pivot is bigger than the j'th element
        for (int j = i - 1; j >= 0; j--) {
            if (pivot > arr[j]) {
                break;
            }
            swap(&arr[j], &arr[j + 1]);
        }
    }
}

For example:

29, 49, 48, 21, 40, 17, 58, 61, 14, 60
29, 49, 48, 21, 40, 17, 58, 61, 14, 60
29, 48, 49, 21, 40, 17, 58, 61, 14, 60
21, 29, 48, 49, 40, 17, 58, 61, 14, 60
21, 29, 40, 48, 49, 17, 58, 61, 14, 60
17, 21, 29, 40, 48, 49, 58, 61, 14, 60
17, 21, 29, 40, 48, 49, 58, 61, 14, 60
17, 21, 29, 40, 48, 49, 58, 61, 14, 60
14, 17, 21, 29, 40, 48, 49, 58, 61, 60
14, 17, 21, 29, 40, 48, 49, 58, 60, 61

As you can see, the first and the second iteration in this example are trivial, 29 and 49 stayed in their places. But, the third and the fourth iteration are intersting because 48 found its place between 29 and 48 and than 21 found its place at the begining of the array and so on.

Bubble Sort

In each iteration, we just swap between two adjacent elements if they are in the wrong order. This way, because we have a loop inside a loop even if the minimum element is at the end of the array, the swapping will bring it to the beginning of the array.

void bubleSort(int* arr, int size) {
    int swapped;
    for (int i = 0; i < size; i++) {
        // Prints the array in each iteration
        printArray(arr, size);
        // Turn off the flag at the beginning of each iteration
        swapped = FALSE;
        for (int j = 0; j < size - 1; j++) {
            // Checks if the next element is bigger than the current one
            if (arr[j] > arr[j + 1]) {
                // Swaps between the two consecutive elements
                swap(&arr[j], &arr[j + 1]);
                // Turn on the flag
                swapped = TRUE;
            }
        }
        // Checks if there were any swaps in this iteration
        if (!swapped) {
            // No! the array is sorted - quits
            return;
        }
    }
}

For example:

52, 42, 91, 39, 10, 98, 68, 11, 50, 46
42, 52, 39, 10, 91, 68, 11, 50, 46, 98
42, 39, 10, 52, 68, 11, 50, 46, 91, 98
39, 10, 42, 52, 11, 50, 46, 68, 91, 98
10, 39, 42, 11, 50, 46, 52, 68, 91, 98
10, 39, 11, 42, 46, 50, 52, 68, 91, 98
10, 11, 39, 42, 46, 50, 52, 68, 91, 98
10, 11, 39, 42, 46, 50, 52, 68, 91, 98

As you can see, we swapped 52 with 42, and then 39 with 52 and then 10 with 52 and so on. Try to follow after this algorithm with a pen and a paper and make sure you fully understand it. Pay attention that because of the swapped flag we added to the basic algorithm, once the array is sorted - the algorithm stops. For example, if the array is sorted, the Buble Sort algorithm (with this flag) stops after one iteration - which is the best time for checking if the array is sorted. All the other algorithms above will fully run all of their iterations for nothing. That makes the Buble Sort algorithm the best algorithm if the array may be sorted with high probability.

Always remember, it's much C-mpler than you thought!

Regards,
Gilad

C-mpler (13 Part Series)

1) C-mpler Introduction 2) Basic Variables & Operators 3 ... 11 3) Intro to I/O 4) Conditions 5) Practice #1 6) Loops 7) Compilation & Precompilation 8) Static Arrays 9) Practice #2 10) Memory Addresses & Pointers 11) Memory Allocation & Dynamic Arrays 12) Basic Sorting 13) Recursion

Posted on by:

Discussion

markdown guide