Sorting

A sorting algorithm is used to arrange elements of an array/list in a

specific order.

Different Sorting Algorithms

 Bubble Sort
 Selection Sort
 Insertion Sort
 Merge Sort
 Quicksort
 Heap Sort
(i) Bubble Sort
Bubble sort is a sorting algorithm that compares two adjacent elements and swaps
them until they are in the intended order.
Just like the movement of air bubbles in the water that rise up to the surface, each
element of the array move to the end in each iteration. Therefore, it is called a
bubble sort.
// Bubble sort in C

#include <stdio.h>

// perform the bubble sort

void bubbleSort(int array[], int size) {

// loop to access each array element

for (int step = 0; step < size - 1; ++step) {

// loop to compare array elements

for (int i = 0; i < size - step - 1; ++i) {

// compare two adjacent elements

// change > to < to sort in descending order
if (array[i] > array[i + 1]) {

// swapping occurs if elements

// are not in the intended order
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}

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

int main() {
int data[] = {-2, 45, 0, 11, -9};
 // find the array's length
int size = sizeof(data) / sizeof(data[0]);

bubbleSort(data, size);

printf("Sorted Array in Ascending Order:\n");

printArray(data, size);
}

Bubble Sort Complexity

Time Complexity

Best O(n)

Worst O(n2)

Average O(n2)

Space Complexity O(1)

(ii) Selection Sort

Selection sort is a sorting algorithm that selects the smallest element
from an unsorted list in each iteration and places that element at the
beginning of the unsorted list.
Selection Sort Algorithm
selectionSort(array, size)
for i from 0 to size - 1 do
set i as the index of the current minimum
for j from i + 1 to size - 1 do
 if array[j] < array[current minimum]
set j as the new current minimum index
if current minimum is not i
swap array[i] with array[current minimum]
end selectionSort

Program to implement Selection Sort Algorithm

#include <stdio.h>

// function to swap the the position of two elements

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

void selectionSort(int array[], int size) {

for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {

// To sort in descending order, change > to < in this line.

// Select the minimum element in each loop.
if (array[i] < array[min_idx])
min_idx = i;
}

// put min at the correct position

swap(&array[min_idx], &array[step]);
}
}
// function to print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}

// driver code
int main() {
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Sorted array in Acsending Order:\n");
printArray(data, size);
}

(iii)Insertion Sort Algorithm

Insertion sort is a sorting algorithm that places an unsorted element at its
suitable place in each iteration.
Insertion Sort Algorithm

insertionSort(array)
mark first element as sorted
for each unsorted element X
'extract' the element X
for j <- lastSortedIndex down to 0
if current element j > X
 move sorted element to the right by 1
break loop and insert X here
end insertionSort
Program for Insertion Sort
#include <stdio.h>

// Function to print an array

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

void insertionSort(int array[], int size) {

for (int step = 1; step < size; step++) {
int key = array[step];
int j = step - 1;

// Compare key with each element on the left of it until an element

smaller than
// it is found.
// For descending order, change key<array[j] to key>array[j].
while (j >=0 && key < array[j]) {
array[j + 1] = array[j];
--j;
}
array[j + 1] = key;
}
}
// Driver code
int main() {
int data[] = {9, 5, 1, 4, 3};
int size = sizeof(data) / sizeof(data[0]);
insertionSort(data, size);
printf("Sorted array in ascending order:\n");
printArray(data, size);
}

(iv) Merge Sort Algorithm

Merge Sort is one of the most popular sorting algorithms that is based on
the principle of Divide and Conquer Algorithm.
Here, a problem is divided into multiple sub-problems. Each sub-
problem is solved individually. Finally, sub-problems are combined to
form the final solution.
// Merge sort in C

#include <stdio.h>

// Merge two subarrays L and M into arr

void merge(int arr[], int p, int q, int r) {

// Create L ← A[p..q] and M ← A[q+1..r]

int n1 = q - p + 1;
int n2 = r - q;

int L[n1], M[n2];

for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];

// Maintain current index of sub-arrays and main array

int i, j, k;
i = 0;
j = 0;
k = p;

// Until we reach either end of either L or M, pick larger among

// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
 // When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

while (j < n2) {

arr[k] = M[j];
j++;
k++;
}
}

// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {

// m is the point where the array is divided into two subarrays

int m = l + (r - l) / 2;

mergeSort(arr, l, m);
 mergeSort(arr, m + 1, r);

// Merge the sorted subarrays

merge(arr, l, m, r);
}
}

// Print the array

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

// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, size - 1);

printf("Sorted array: \n");

printArray(arr, size);
}
(v)Quicksort
Quicksort is a sorting algorithm based on the divide and conquer
approach where
1. An array is divided into subarrays by selecting a pivot
element (element selected from the array).

While dividing the array, the pivot element should be positioned in

such a way that elements less than pivot are kept on the left side
and elements greater than pivot are on the right side of the pivot.
2. The left and right subarrays are also divided using the same
approach. This process continues until each subarray contains a
single element.
3. At this point, elements are already sorted. Finally, elements are
combined to form a sorted array.

// Quick sort in C

#include <stdio.h>

// function to swap elements

void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}

// function to find the partition position

int partition(int array[], int low, int high) {

// select the rightmost element as pivot

int pivot = array[high];

// pointer for greater element

int i = (low - 1);

// traverse each element of the array

// compare them with the pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {

// if element smaller than pivot is found

// swap it with the greater element pointed by i
i++;

// swap element at i with element at j

swap(&array[i], &array[j]);
}
}

// swap the pivot element with the greater element at i

swap(&array[i + 1], &array[high]);
 // return the partition point
return (i + 1);
}

void quickSort(int array[], int low, int high) {

if (low < high) {

// find the pivot element such that

// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
int pi = partition(array, low, high);

// recursive call on the left of pivot

quickSort(array, low, pi - 1);

// recursive call on the right of pivot

quickSort(array, pi + 1, high);
}
}

// function to print array elements

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

// main function
int main() {
int data[] = {8, 7, 2, 1, 0, 9, 6};

int n = sizeof(data) / sizeof(data[0]);

printf("Unsorted Array\n");
printArray(data, n);

// perform quicksort on data

quickSort(data, 0, n - 1);

printf("Sorted array in ascending order: \n");

printArray(data, n);
}

(vi) Heap Sort Algorithm

Heap Sort is a popular and efficient sorting algorithm in computer
programming. Learning how to write the heap sort algorithm requires
knowledge of two types of data structures - arrays and trees.
The initial set of numbers that we want to sort is stored in an array
e.g. [10, 3, 76, 34, 23, 32] and after sorting, we get a sorted
array [3,10,23,32,34,76].
Heap sort works by visualizing the elements of the array as a special
kind of complete binary tree called a heap.
// Heap Sort in C
#include <stdio.h>
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
 heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
// Print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
}

Heap Sort Complexity

Time Complexity

Best O(nlog n)
Worst O(nlog n)

Average O(nlog n)

Space Complexity O(1)