Basic Sorting
Tags: c, sorting, beginners
Published: 2019-06-28 10:35:32

Let's say we have the following code:
```cpp
#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:
```cpp
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.
```cpp
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. 
```cpp
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