Selection sort is a simple algorithm, but inefficient.
First, find the smallest element using a linear scan and move it to the front (swap). Then, find the second smallest and move it, again doing a linear scan. Continue doing this until all the elements are in place.
Selection Sort
void Swap(int[] array, int index1, int index2){
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
void SelectionSort(int[] array){
var n = array.Length - 1;
for(int i = 0; i <= n; i++){
var minIdx = i;
for(int j = i + 1; j <= n; j++){
if(array[j] < array[minIdx]){
minIdx = j;
}
}
Swap(array, minIdx, i);
}
}
Time Complexity: O(n^2)
Space Complexity: O(1)
Bubble Sort
In this algorithm, we start at the beginning of the array and swap the first two elements if the first is greater than the second. Then, we go to the next pair, and so on, continuously making sweeps of the array until it is sorted.
void BubbleSort(int[] array){
var n = array.Length;
for(int i = 0; i < n - 1; i++){
for(int j = 0; j < n - i - 1; j++){
if(array[j] > array[j + 1]){
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
Time Complexity: O(n^2)
Space Complexity: O(1)
Insertion Sort
void InsertionSort(int[] array){
var n = array.Length - 1;
for(int i = 1; i <= n; i++){
var unsortedItem = array[i];
var comparingItemIndex = i - 1;
while(comparingItemIndex >= 0 && unsortedItem < array[comparingItemIndex]){
array[comparingItemIndex + 1] = array[comparingItemIndex];
comparingItemIndex--;
}
array[comparingItemIndex + 1] = unsortedItem;
}
}
Time Complexity: O(n^2)
Space Complexity: ?
Quick Sort
Quicksort is another sorting algorithm based on the Divide and Conquer programming technique. In this algorithm, an element is first chosen as the pivot, and the entire array is then partitioned around this pivot.
As you've probably guessed, a good pivot is crucial for an efficient sort. The pivot can either be a random element, the media element, the first element, or even the last element.
Implementations of quicksort often differ in the way they choose a pivot. In the average case, quicksort will sort a large array with a good pivot in just O(nlogn) time.
The general pseudocode of quicksort repeatedly partitions the array on the pivot and positions it in the correct position of the subarray. It also places the elements smaller than the pivot to its left and elements greater than the pivot to its right.
void Swap(int[] array, int index1, int index2){
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
int Partition(int[] array, int lowIdx, int highIdx){
var pivot = array[highIdx];
var possibleIdx = lowIdx - 1;
for(int i = lowIdx; i < highIdx; i++){
if(array[i] <= pivot){
possibleIdx++;
Swap(array, i, possibleIdx);
}
}
possibleIdx++;
Swap(array, possibleIdx, highIdx);
return possibleIdx;
}
void QuickSort(int[] array, int startIdx, int endIdx){
if(startIdx < endIdx){
var pivotIdx = Partition(array, startIdx, endIdx);
if(startIdx < pivotIdx - 1) // sort left half
QuickSort(array, startIdx, pivotIdx - 1);
if(pivotIdx < endIdx) // sort right half
QuickSort(array, pivotIdx, endIdx);
}
}
Time Complexity:
O(n^2) Worst case
O(n log n) Average case
Space Complexity:
O(log n)
Merge Sort
Divide and Conquer Programming Technique
Merge sort divides the array in half, sorts each of those halves, and then merge them back together.
Each of those halves has the same sorting algorithm applied to it.
Merge Sort
void MergeSort(int[] array){
int[] helper = new int[array.Length];
MergeSort(array, helper, 0, array.Length - 1);
}
void MergeSort(int[] array, int[] helper, int lowIdx, int highIdx){
if(lowIdx < highIdx){
int middleIdx = (lowIdx + highIdx) / 2;
MergeSort(array, helper, lowIdx, middleIdx); //sort left half
MergeSort(array, helper, middleIdx + 1, highIdx); //sort right half
Merge(array, helper, lowIdx, middleIdx, highIdx);
}
}
void Merge(int[] array, int[] helper, int lowIdx, int middleIdx, int highIdx){
/* Copy both halves into a helper array */
for(int i = lowIdx; i <= highIdx; i++){
helper[i] = array[i];
}
int helperLeft = lowIdx;
int helperRight = middleIdx + 1;
int currentIdx = lowIdx;
while(helperLeft <= middleIdx && helperRight <= highIdx){
// if left element is smaller than the right element
if(helper[helperLeft] <= helper[helperRight]){
array[currentIdx] = helper[helperLeft];
helperLeft++;
}
// else if right element is smaller than the left element
else{
array[currentIdx] = helper[helperRight];
helperRight++;
}
currentIdx++;
}
int remaining = middleIdx - helperLeft;
for(int i = 0; i <= remaining; i++){
array[currentIdx + i] = helper[helperLeft + i];
}
}
Time Complexity: O(n log n)
Space Complexity: O(n)
The space complexity being O(n) is due to the auxiliary space used to merge the parts of the array.