These algorithms are what we call intermediate sorting algorithms. The main reason for using these algorithms is the lack of scalability in algorithms such as bubble sort. Understanding the limitations of the latter algorithms is critical. For instance, sorting an array of 100000 elements using bubble sort will take a lot of time to complete. Because of this, we need a quick way to sort massive arrays faster.
What are faster sorts?
It is a family of sorting algorithms capable of improving the time complexity of sorting an algorithm from O(n) to O(n log(n)). These algorithms do a trade-off between simplicity and efficiency. So, algorithms that are generally hard and take longer to comprehend mostly have very efficient time complexity. These algorithms comprise Merge Sort, Quick Sort, and an additional Radix Sort.
Merge Sort
It is an algorithm that works by combining merging and sorting. It exploits the fact that arrays of 0 or 1 elements are always sorted. Merge sort decomposes an array into smaller arrays of 0 or 1 elements, then builds up a new sorted array.
Merging Arrays
- To implement merge sort, it’s helpful first to implement a function responsible for merging two sorted arrays
Given two sorted arrays, this helper function should create a new array that is also sorted and consists of all of the elements in two input arrays. - This function should run in O(n + m) time and O(n + m) space and should not modify the parameters passed to it.
Merging Arrays Pseudocode
- Create an empty array, take a look at the smaller values in each input array.
- While there are still values we haven’t looked at …
- if the value in the first array is smaller than the value in the second array, push the value in the first array into our results and move on to the next value in the first array.
- If the value in the first array is larger than the value in the second array, push the value in the second array
- Once we exhaust one array, push in all remaining values from the other array.
function merge(arr1, arr2){
let results =[];
let i =0;
let j = 0;
while(i < arr1.length && j < arr2.length){ if(arr2[j] > arr1[i]){
results.push(arr1[i]);
i++;
}else{
results.push(arr2[j])
j++;
}
}
while( i < arr1.length ){
results.push(arr1[i])
i++;
}
while(j < arr2.length){
results.push(arr2[j])
j++;
}
return results
}
arrayOne =[1,10,50]
arrayTwo = [2,14,99,100]
merge(arrayOne,arrayTwo)
MergeSort Pseudocode
- Break up the array into halves until you have arrays that are empty or have one element
- Once you have smaller sorted arrays, merge those arrays with other sorted arrays until you are back at the entire length of the array
- Once the array has been merged back together, return the merged and sorted array.
function mergeSort(arr){
if(arr.length <=1) return arr;
let mid = Math.floor(arr.length/2);
let left = mergeSort(arr.slice(0,mid));
let right =mergeSort(arr.slice(mid));
return merge(left, right)
}
Complete MergeSort Algorithm
// Merge function from earlier
function merge(arr1, arr2){
let results = [];
let i = 0;
let j = 0;
while(i < arr1.length && j < arr2.length){
if(arr2[j] > arr1[i]){
results.push(arr1[i]);
i++;
} else {
results.push(arr2[j])
j++;
}
}
while(i < arr1.length) {
results.push(arr1[i])
i++;
}
while(j < arr2.length) {
results.push(arr2[j])
j++;
}
return results;
}
// Recrusive Merge Sort
function mergeSort(arr){
if(arr.length <= 1) return arr;
let mid = Math.floor(arr.length/2);
let left = mergeSort(arr.slice(0,mid));
let right = mergeSort(arr.slice(mid));
return merge(left, sright);
}
mergeSort([10,24,76,73])
Complexity of mergeSort(Big O)
- Time complexity (Best) – O(nlog(n))
- Time Complexity(Average) – O(nlog(n))
- Time Complexity (worst) – O(n log(n))
- Space Complexity – (O(n))
QuickSort
Like merge sort, it exploits that arrays of 0 or 1 elements are always sorted. It works by selecting one pivot element and finding the index where the pivot should end up in the sorted array. Once the pivot is positioned appropriately, quicksort can be applied on either side of the pivot.
Pivot Helper
- To implement merge sort, it’s helpful first to implement a function responsible for arranging elements in an array on either side of a pivot
- Given an array, this helper function should designate an element as the pivot
- It should then rearrange elements in the array so that all values less than the pivot are moved to the left of the pivot, and all values more significant than the pivot are moved to the right of the pivot.
- The order of elements on either side of the pivot doesn’t matter!
- The helper should do this in place; that is, it should not create a new array.
- when complete, the helper should return the index of the pivot
Picking a pivot
- The runtime of a quick sort depends partly on how one selects the pivot.
- Ideally, the pivot should be chosen so that it’s roughly the median value in the data set you’re sorting.
- For simplicity, we’ll always choose the pivot to be the first element(we’ll talk about the consequences of this later)
Pivot Pseudocode
- It will help to accept three arguments: an array, a start index, and an end index. These can default to 0 and the array length minus 1, respectively.
- Grab the pivot from the start of the array
- Store the current pivot index in a variable(this will keep track of where the pivot should end up)
- Loop through the array from the start until the end
- If the pivot is greater than the current element, increment the pivot index variable and then swap the current element with the element at the pivot index
- swap the starting element(i.e. the pivot ) with the pivot index
- Return the pivot index
function pivot(arr, start =0, end=arr.length+1){
function swap(array, i, j){
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
var pivot = arr[start];
var swapIdx = start;
for(var i =start +1; i<arr.length; i++){
swapIdx++;
swap(arr, swapIdx, i)
}
}
swap(arr, start, swapIdx)
return swapIdx;
}
Quicksort Pseudocode
- call the pivot helper on the array
- when the helper returns you the updated pivot index, recursively call the pivot helper on the subarray to the left of that index and the subarray to the right of that index.
- Your base case occurs when you consider a subarray with less than two elements.
function quickSort(arr, left =0, right =arr.length-1){
if(left < right){
let pivotIndex =pivot(arr, left, right)
// left
quickSort(arr, left, pivotIndex-1);
//right
quickSort(arr, pivotIndex+1, right);
}
return arr;
}
quickSort([4,6,9,1,2,5,3])
Complete QuickSort Algorithm
function pivot(arr, start = 0, end = arr.length - 1) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
// We are assuming the pivot is always the first element
let pivot = arr[start];
let swapIdx = start;
for (let i = start + 1; i <= end; i++) {
if (pivot > arr[i]) {
swapIdx++;
swap(arr, swapIdx, i);
}
}
// Swap the pivot from the start the swapPoint
swap(arr, start, swapIdx);
return swapIdx;
}
function quickSort(arr, left = 0, right = arr.length -1){
if(left < right){
let pivotIndex = pivot(arr, left, right) //3
//left
quickSort(arr,left,pivotIndex-1);
//right
quickSort(arr,pivotIndex+1,right);
}
return arr;
}
quickSort([100,-3,2,4,6,9,1,2,5,3,23])
Big O of Quicksort
- Time complexity(Best) – O(n log n)
- Time complexity (average)- O(n log n)
- Time complexity(worst) – O(n^2)
- Space complexity – O(log n)
Radix Sort
Radix sort is a special sorting algorithm that works on lists of numbers. It never makes comparisons between elements! Instead, it exploits the fact that information about the size of a number is encoded in the number of digits. More digits mean a more significant number.
Radix Sort Helpers
To implement radix sort, it’s helpful to build a few helper functions first:
getDigit(num, place) – returns the digit in num at the given place value
function getDigit(num, i){
return Math.floor(Math.abs(num) / Math.pow(10, i)) %% 10;
}
digitCount(num) – returns the number of digits in num
function digitCount(num){
if(num ===0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
Most digits(nums) – Given an array of numbers, returns the number of digits in the most significant numbers in the list.
function mostDigits(nums){
let maxDigits = 0;
for(let i= 0; i<nums;i++){
maxDigits =Math.max(maxDigits, digitCount(nums[i]));
}
return maxDigits;
}
Radix Sort Pseudocode
- Define a function that accepts a list of numbers
- Figure out how many digits the largest number has
- Loop from k = 0 up to this most significant number of digits
- For each iteration of the loop:
- create buckets for each digit (0 to 9)
- place each number in the corresponding bucket based on its kth digit.
- Replace our existing array with values in our buckets, starting with 0 and going up to 9
- return the list at the end!
function radixSort(nums){
let maxDigitCount =mostDigits(nums);
for(let k =0; k<maxDigitCount; k++){
let digitBuckets = Array.from({length:10}, () => []);
for(let i =0; i<nums.length; i++){
let digit = getDigit(nums[i],k);
digitBuckets[getDigit(digit)].push(nums[i]);
}
nums =[].concat(...digitBuckets);
}
return nums;
}
radixSort([23, 345,5467,12,2345,9852])
Complete Radix sort Algorithm
function getDigit(num, i) {
return Math.floor(Math.abs(num) / Math.pow(10, i)) %% 10;
}
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function mostDigits(nums) {
let maxDigits = 0;
for (let i = 0; i < nums.length; i++) {
maxDigits = Math.max(maxDigits, digitCount(nums[i]));
}
return maxDigits;
}
function radixSort(nums){
let maxDigitCount = mostDigits(nums);
for(let k = 0; k < maxDigitCount; k++){
let digitBuckets = Array.from({length: 10}, () => []);
for(let i = 0; i < nums.length; i++){
let digit = getDigit(nums[i],k);
digitBuckets[digit].push(nums[i]);
}
nums = [].concat(...digitBuckets);
}
return nums;
}
radixSort([23,345,5467,12,2345,9852])
Radix sort Big O
- Time complexity (Best) – O(nk)
- Time complexity(Average) – O(nk)
- Time complexity(Worst) – O(nk)
- Space complexity: O(n + k)
where:
- n -length of the array
- k – number of digits(average)
Conclusion
Merge sort, and quick sort are standard efficient sorting algorithms. Quicksort can be slow in the worst case, but it is comparable to merge sort on average. In addition, Merge sort takes up more memory because it creates a new array in-place merge sorts exist, but they are complex.
It is also worth looking into Radix sort, a fast sorting algorithm for numbers. The latter exploits place value to sort numbers in linear time for a fixed number of digits.
