Repository navigation
Sorting Algorithms
Examples
- Sorting numbers from smallest to largest
- Sorting names alphabetically
- Sorting movies based on release year
Why do we need to learn this?
. Sorting is an incredibly common taks, so it's good to know how it works . there are many different ways to sort things, and different techniques have their own advantages and disadvantages
...but it doesn't always work the way you expect
example:
["Steele", "Colt", "Data Structure", "Algorithms"].sort() =>
["Algorithms", "Colt", "Data Structures", "Steele"]
that make sense, that sorted alphabetically.
another example:
[6, 4, 15, 10].sort() => [10, 15, 4, 6] => that does not make sense.
. The built-in sort method accepts an optional comparator funtion . You can use this comparator function to tell JavaScript how you want it to sort . The comparator looks at pairs of elements (a and b), determines their order on the return value . If it returns a negative number, a should come before b . If it returns positive number, it should come after b . If it returns 0, a and b are the same as far as the sort is concerned
example:
function numberCompare(num1, num2) {
return num1 - num2;
}
[6, 4, 15, 10].sort(numberCompare); // [4, 6, 10, 15]bubble sort is not all that efficient, it's not that commonly used, it's only have one use case.
A sorting algorithm where the largest values bubble up to the top!
how it works: we have this array => [29, 10, 14, 30, 37, 14, 18]
as we loop through each item, we compare it to the next item, and if this one is larger than the next value, and if it is => we swap the values => so swaping is the important thing to the bubble sort
Before we sort, we must swap!
Many sorting algorithms involve some type of swapping functionality (e.g. swapping to numbers to put them in order)
function swap(arr, idx1, idx2) {
return [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
}BubbleSort Pseudocode
. Start looping from with a variable called i the end of the array towards the beginning
. Start an inner loop with a variable called j from the beginning until i - 1
. Return the sorted array
. If arr[j] is greater than arr[j + 1], swap those two values!
function swap(arr, idx1, idx2) {
return [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}
function bubbleSortAscend(arr) {
for (let i = arr.length; i > 0; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j+1] < arr[j]) {
swap(arr, j, j+1);
}
}
}
return arr;
}
function bubbleSortDescend(arr) {
for (let i = arr.length; i > 0; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j+1] > arr[j]) {
swap(arr, j, j+1);
}
}
}
return arr;
}
console.log(bubbleSortAscend([9, 3, 6, 24, 17]));
console.log(bubbleSortDescend([9, 3, 6, 24, 17]));check do we need more swaps???
function bubbleSort(arr) {
let noSwaps;
for (let i = arr.length; i > 0; i--) {
noSwaps = true;
for (let j = 0; j < i - 1; j++) {
if (arr[j+1] > arr[j]) {
swap(arr, j, j+1);
noSwaps = false;
}
}
if (noSwaps) break;
}
return arr;
}in general it is O(n^2), however if the data is nearly sorted or already sorted, then with optimized version noSwaps it's more like linear time. O(n) => that is the best case. So if we know that our data is nearly sorted, so we can use BubbleSort
Similar to bubble sort, but instead of first placing large values into sorted position, it places small values into sorted position.
for example we have this array: [5, 3, 4, 1, 2] => what we're gonna do is that we're start from at the beginning and find the minimum value and put it at first of the array. in bubble sort we're finding largest value, but in selection sort we're finding the smallest value.
We are going through and selecting the smallest element (the minimum) and then put it at the beginning in this as well we use swapping method.
. Store the first element as the smallest value you've seen so far.
. Compare this item to the next item in the array until you find the smaller value.
. Repeat this with the next element until the array is sorted
What do we actually saving, we're not actually saving the value itself, what we're gonna save is the index of the value that we found, so that we can swap
O(n^2)
selection sort is potentially better than bubble sort
bubble sort, we're basically swapping over and over to get the largest item to the end, but in selection sort we compare values but we only make one swap at the end of each loop.
so, selection sort is better than bubble sort
swapping is not good for memory, we're worried actually doing the swap, which is not very common to be honest, but if you were then selection sort is better, otherwise it's not very good. but it is easy and it helps us to prepare for some of the other algorithms
it's pretty similar to bubble and selection sort, however there are couple key distinctions, that insertion sort is actually good at.
Builds up the sort by gradually creating a larger left half which is always sorted.
. Start by picking the second element in the array . Now compare the second element with the one before it and swap if necessary . Continue to the next element ...
function insertionSort(arr) {
for (var i = 1; i < arr.length; i++) {
var currentVal = arr[i];
for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j+1] = arr[j]
}
arr[j+1] = currentVal;
}
return arr
}in time complexity it's pretty similar to the other ones, but if our data is almost all sorted => it's good to use this sorting algorithm.
and if your data, there's something called online algorithm => it receives new data => does not have to have the entire array at once => in this case insertion sort is good at as well. in this case insertion sort is great.
Bubble Sort => Time Complexity (Best) O(n) / Time Complexity (Average) O(n^2) / Time Complexity (Worst) O(n^2) / Space Complexity (Best) O(1)
Insertion Sort => Time Complexity (Best) O(n) / Time Complexity (Average) O(n^2) / Time Complexity (Worst) O(n^2) / Space Complexity (Best) O(1)
Selection Sort => Time Complexity (Best) O(n^2) / Time Complexity (Average) O(n^2) / Time Complexity (Worst) O(n^2) Space Complexity (Best) O(1)
. Sorting is Fundamental! . Bubble sort, selection sort, and insertion sort are all roughly equivalent . All have average time complexities that are quadratic . We can do better ...but we need more complex algorithms!