Sorting
Bubble Sort
- Time Complexity: O(n^2)
- Space Complexity: O(1)
static void BubbleSort(IList<int> nums){ var swapped = false;
do { swapped = false; for (var i = 0; i < nums.Count() - 1; i++) { if (nums[i] > nums[i + 1]) { Swap(nums, i, i + 1); swapped = true; } } } while (swapped);}
static void Swap(IList<int> nums, int i1, int i2){ var temp = nums[i1]; nums[i1] = nums[i2]; nums[i2] = temp;}
Insertion Sort
Similar to Bubble Sort, but:
- does only 1 pass through the array
- places items in the right spots directly instead of moving them 1 field at a time
It’s slow, but it comes useful when:
-
the dataset is almost sorted
-
we’re sorting a stream of incoming data
-
Time Complexity: O(n^2)
-
Space Complexity: O(1)
void InsertionSort(int[] numbers){ for (var i = 0; i < numbers.Length - 1; i++) { if (numbers[i] > numbers[i + 1]) { var index = FindInsertionIndex(numbers, i + 1); Insert(numbers, i + 1, index); } }
int FindInsertionIndex(int[] numbers, int sourceIndex) { for (var i = 0; i < sourceIndex; i++) { if (numbers[i] > numbers[sourceIndex]) return i; } return 0; }
void Insert(int[] numbers, int originalIndex, int targetIndex) { if (originalIndex == targetIndex) return;
var temp = numbers[originalIndex]; for (var i = originalIndex; i > targetIndex; i--) { numbers[i] = numbers[i - 1]; } numbers[targetIndex] = temp; }}
Merge Sort
It uses the divide-and-conquer approach. We split the array to single-element arrays and then join them together, sorting in the process.
- Time Complexity: O(n log(n))
- Space Complexity: O(n)
void MergeSort(int[] numbers){ if (numbers.Length <= 1) return;
var partitionIndex = numbers.Length / 2;
var arr1 = numbers.Take(partitionIndex).ToArray(); var arr2 = numbers.Skip(partitionIndex).ToArray();
MergeSort(arr1); MergeSort(arr2);
var i = 0; var j = 0; var index = 0;
while (index < numbers.Length) { if (i == arr1.Length || arr2[j] < arr1[i]) { numbers[index++] = arr2[j++]; } else if (j == arr2.Length || arr1[i] < arr2[j]) { numbers[index++] = arr1[i++]; } }}
Quicksort
It’s a recursive algorithm where we select pivot point and move elements around the pivot in a way that elements less than pivot are on the right, and elements that are greater are on the right. Then, we do the same in the two partitions that the pivot created.
It’s a divide-and-conquer technique.
There are different strategies when it comes to selecting the pivot point. It could be:
- first element
- last element
- random element
- something else
- Time Complexity: O(n log n) (worst case: O(n^2) - when the picked pivot is the smallest or the greatest element)
- Space Complexity: O(log n)
static void QuickSort(IList<int> nums){ QuickSortInternal(nums, 0, nums.Count() - 1);}
static async void QuickSortInternal(IList<int> nums, int startIndex, int endIndex){ if (startIndex >= endIndex) return;
var pivotIndex = endIndex;
var tempIndex = -1; // it will point to elements greater than pivot for (var i = startIndex; i < pivotIndex; i++) { if (nums[i] < nums[pivotIndex] && tempIndex != -1) { Swap(nums, i, tempIndex); tempIndex++; } else if (nums[i] > nums[pivotIndex] && tempIndex == -1) { tempIndex = i; } }
if (tempIndex != -1) { Swap(nums, pivotIndex, tempIndex); pivotIndex = tempIndex; }
QuickSortInternal(nums, startIndex, pivotIndex - 1); QuickSortInternal(nums, pivotIndex + 1, endIndex);}
static void Swap(IList<int> nums, int i1, int i2){ var temp = nums[i1]; nums[i1] = nums[i2]; nums[i2] = temp;}