Tim Koval
Geek; Embedded Systems Developer; Firmware, Hardware and System Software Engineer;

Sorting Algorithms – Part 1

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.

Share

You may also like...

Leave a Reply