Sorting Algorithms

Selection sort:

• Comparison based approach
• Time complexity: O(n²)
• Space complexity: O(1)
• Not a stable algorithm but can be made stable by shifting elements one position in a circular fashion
• In place sorting algorithm

void selection_sort(int *arr, int size) {
        for (int i = 0; i < size; ++i) {
            int minimum = i;
            for (int j = i + 1; j < size; ++j) {
                if (arr[j] < arr[minimum]) {
                    minimum = j;
                }
            }
                swap(&arr[i], &arr[minimum]);
            }
        }

Bubble sort:

• comparison based approach
• Time complexity:
• worst case, Average case : O(n²)
• Best case : O(n)
• Space complexity: O(1)
• Stable sorting algorithm
• can be optimized on a sorted array by setting a flag

void bubble_sort(int *arr, int size) {
	for (int i = 0; i < size-1; ++i) {
            static int count = 0;
            int swapped = false;
            for (int j = 0; j < size-i-1; ++j) {
                if (arr[j] > arr[j + 1]) {
                    swapped = true;
                    swap(&arr[j], &arr[j + 1]);
                }
            }
            if (!swapped) {
                cout << "Array is already in sorted state at iteration = " << count << endl;
                break;
            }
            ++count;
    }

Insertion sort:

• Comparison based sort algorithm
• Ideal to the technique we follow in arranging playing cards
• Time complexity:
• worst, average: O(n²)
• best: O(n)
• Space complexity: O(1)
• Stable sorting algorithm
• Mathematically proven that this algorithm works efficiently on smaller inputs
• Used a variation of this algorithm in c++, python libraries

void insertion_sort(int *arr, int size) {
        for (int index = 1; index < size; ++index) {
            int previous_index = index - 1;
            int key = arr[index];
            
            while (previous_index >= 0 && arr[previous_index] > key) {
                arr[previous_index + 1] = arr[previous_index--];
            }
            arr[previous_index + 1] = key;
        }
    }

Merge sort:

• Divide and conquer algorithm
• Does comparisons between the elements
• Time complexity:
• worst, avg cases: O(nlogn)
• Space Complexity: O(n)
• Not in place sorting algorithm
• stable sorting algorithm

void merge(int *arr, int start, int mid, int end) {
	int left_size = mid - start + 1;
	int right_size = end - mid;
	int *left_array = new int[left_size];
	int *right_array = new int[right_size];
	int temp_start = start;
	for (int index = 0; index < left_size; ++index) {
		left_array[index] = arr[temp_start++];
	}
	for (int index = 0; index < right_size; ++index) {
		right_array[index] = arr[++mid];
	}
	int i, j, k;
	
	i = j = 0;
	k = start;
	while (i < left_size && j < right_size)
	{
		if (left_array[i] <= right_array[j]) {
			arr[k++] = left_array[i++];
		}
		else {
			arr[k++] = right_array[j++];
		}
	}
	while (i < left_size) {
		 arr[k++] = left_array[i++];
	}
	while (j < right_size) {
		 arr[k++] = right_array[j++];
	}
}
void merge_sort(int *arr, int start, int end) {
	if (start < end) {
		int mid = (start+end)/2;
		merge_sort(arr, start, mid);
		merge_sort(arr, mid+1, end);
		merge(arr, start, mid, end);
	}
}

Quick sort:

• Divide and Conquer based approach
• Time Complexity:
• worst case: O(n²)
• average case: O(nlogn)
• Space Complexity: O(1)
• In place sorting algorithm
• Not a stable sorting algorithm but can be made stable by using naive partition approach (by creating an array of size ‘n’)

void swap(int *a, int *b) {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    int partition(int *arr, int start, int end) {
        int i, j, pivot;
        pivot = arr[end];
        i = start - 1;
        for (j = start; j < end; ++j) {
            if (arr[j] < pivot) {
                ++i;
                swap(&arr[i], &arr[j]);
            }
        }
        swap(&arr[i + 1], &arr[end]);
        return i;
    }
    void quick_sort(int *arr, int start, int end) {
        if (start < end) {
            int partitioned_index = partition(arr, start, end);
            quick_sort(arr, start, partitioned_index);
            quick_sort(arr, partitioned_index + 1, end);
        }
    }