Recently, I’ve started to learn basic Algorithms and Data Structures. I wanted to find any resource to understand them deeply because a lot of different articles from web couldn’t explain them well. After some time of surveying I’ve found a great course 6.006 “Introduction to Algorithms” by MIT OCW and after watching some lectures I decided to write some articles about main topics covered by the course.

I just want to remind you that it is really better to watch the entire lectures. My purpose is just to show key information from the lectures and implementation in C/C++ for some of the algorithms and data structures.

First topics are sorting and searching, so this article will cover main sorting algorithms based on **Comparison Model** (compare one element of the given data with another).

**Bubble sort :**

The most stupid sorting algorithm. Sorting one by one starting from the beginning comparing the current elment with the next one for each element of array.

void bubbleSort(int *arr, int size) { for (int i = 0; i < size; i++) for (int j = 0; j < size-1; j++) if (arr[j] > arr[j+1]) { int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } }

Then in `main()`

:

bubbleSort(arr, size);

*Complexity = O(n^2)**Extra space = O(1) – temporary variable for swap*

**Insertion sort :**

Sorting one by one comparing next element with previously sorted part of array.

Best sorting algorithm when n < 10

void insertionSort(int *arr, int size) { for (int i = 1; i < size; i++) for (int j = i; j > 0 && arr[j-1] > arr[j]; j--) swap(arr[j-1], arr[j]); }

Then in `main()`

:

insertionSort(arr, size);

*Complexity = O(n^2)**Extra space = O(1) – temporary variable for swap*

**Merge sort :**

Sorting by dividing initial array on two parts, sorting them by recursion and merging by taking a pair of elements from two arrays and placing according to their values.

void merge(int *array, int first, int last) { int mid, start, final, j; int *arr = new int[100]; mid = (first + last) / 2; start = first; final = mid + 1; for (j = first; j <= last; j++) if ((start <= mid) && ((final > last) || (array[start] < array[final]))) { arr[j] = array[start]; start++; } else { arr[j] = array[final]; final++; } for (j = first; j<= last; j++) array[j] = arr[j]; delete []arr; }

void mergeSort(int *arr, int first, int last) { if (first < last) { mergeSort(arr, first, (first+last) / 2); mergeSort(arr, (first+last) / 2 + 1, last); merge(arr, first, last); } }

Then calling it from `main()`

function :

mergeSort(arr, 0, size - 1);

*Complexity = O(nlog(n)) – n for merge and log(n) for recursive sorting* *Extra space = O(n) – two copies of divided array*

**Heap sort**

Algorithm that builds a max-heap (binary tree where node key is always >= than the keys of children) from any heap(array represented as a binary tree) and creates sorted array by taking the biggest element from the max-heap.

The algorithm can be implemented by 3 functions – `maxHeapify()`

, `buildMaxHeap()`

and `heapSort()`

:

void maxHeapify(int *arr, int size, int i) { int largest = i; int left = 2*i + 1; int right = 2*i + 2; if (left < size && arr[left] > arr[largest]) largest = left; if (right < size && arr[right] > arr[largest]) largest = right; if (largest != i) { swap(arr[i], arr[largest]); maxHeapify(arr, size, largest); } }

void buildMaxHeap(int *arr, int size) { for (int i = size / 2 - 1; i >= 0; i--) maxHeapify(arr, size, i); }

void heapSort(int *arr, int size) { buildMaxHeap(arr, size); for (int i = size - 1; i >= 0; i--) { swap(a[0], a[i]); maxHeapify(arr, i, 0); } }

Then call `heapSort()`

from `main()`

:

heapSort(arr, size);

*Complexity = O(nlog(n)) *

That is all what I wanted to cover in this article. Next will be about other type of sorting algorithms based on **Random Access**.