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
Top comments (0)