aSorting 1. Introduction 1.1. Sorting methods in languages 2. Bubble sort 3. Selection sort 4. Insertion sort 5. Merge sort 6. Quick sort 7. Which sort is best? 8. Radix sort, Counting sort 9. Sorting interview

1. Introduction• In interviews, sorting is really important → e.g. take an array of numbers and sort them or interviewer wants you to do something to an input and they tell you the input is sorted → why they would tell you that?.• Sorting is not a big deal when it comes to small input data. It gets more important as the input gets larger and larger.• Sorting is very important component of many big companies every day business, e.g. Google, Amazon, Facebook, etc.• They can't just use the built-in sort methods that come with the languages → They usually need custom sorting methods.• For most of the data applications, some kind of sorting operation is needed.• There are so many sorting algorithms → sorting algorithms Wiki– Note: You won't need to implement many of these advanced sorting methods on your own. They're mostly done by academics, etc. You only need to learn the basic sorting algorithms for the interview.* Bubble Sort* Insertion Sort* Selection Sort* Merge Sort* Quick Sort– Note: Even in the interviews, there's no need to implement sorting algorithms from scratch → you just have to be familiar with different sorting algorithms (along with their time & space complexity) and apply it to the interview questions. * You should know different sorting algorithms time and space complexity tradeoffs. It's important to know when to use which sorting algorithm.* Check out this website for a nice visual comparison of different sorting algorithms based on the input data.1.1. Sorting methods in languages• Sort method in different languages may behave differently and act weird at times.– For example, the <Array>.sort() method in JS, converts numerical values into strings and sort based on the characters' unicode.• Also, with sort methods, usually there's no guarantee for space and time complexity optimization for all the cases. 2. Bubble sort• Bubble sort comes from the idea of bubbling up the largest value using multiple pass through.• Let's say we want to sort this series of numbers → 6,5,3,1,8,7,2,4${\displaystyle 6,5,3,1,8,7,2,4}$– 6,5,3,1,8,7,2,4${\displaystyle 6,5,3,1,8,7,2,4}$ → 5⇆6,3,1,8,7,2,4${\displaystyle 5\leftrightarrows 6,3,1,8,7,2,4}$– 5,6,3,1,8,7,2,4${\displaystyle 5,6,3,1,8,7,2,4}$ → 5,3⇆6,1,8,7,2,4${\displaystyle 5,3\leftrightarrows 6,1,8,7,2,4}$– 5,3,6,1,8,7,2,4${\displaystyle 5,3,6,1,8,7,2,4}$ → 5,3,1⇆6,8,7,2,4${\displaystyle 5,3,1\leftrightarrows 6,8,7,2,4}$– 5,3,1,6,8,7,2,4${\displaystyle 5,3,1,6,8,7,2,4}$ → 5,3,1,6,8,7,2,4${\displaystyle 5,3,1,6,8,7,2,4}$ (no change here)– 5,3,1,6,8,7,2,4${\displaystyle 5,3,1,6,8,7,2,4}$ → 5,3,1,6,7⇆8,2,4${\displaystyle 5,3,1,6,7\leftrightarrows 8,2,4}$– 5,3,1,6,7,8,2,4${\displaystyle 5,3,1,6,7,8,2,4}$ → 5,3,1,6,7,2⇆8,4${\displaystyle 5,3,1,6,7,2\leftrightarrows 8,4}$– 5,3,1,6,7,2,8,4${\displaystyle 5,3,1,6,7,2,8,4}$ → 5,3,1,6,7,2,4⇆8${\displaystyle 5,3,1,6,7,2,4\leftrightarrows 8}$– go to the beginning and continue sorting (bubbling up) like that${\displaystyle gotothebeginningandcontinuesorting(bubblingup)likethat}$ • Bubble sort is not the most efficient sort but it's the simplest one.• Time complexity → O(n2)${\displaystyle O\left(n^2\right)}$• Space complexity → O(1)${\displaystyle O(1)}$

Figure 1:Bubble Sort

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; function bubbleSort(array) { const length = array.length; for (let i = 0; i < length; i++) { for (let j = 0; j < length; j++) { if(array[j] > array[j+1]) { //Swap the numbers let temp = array[j] array[j] = array[j+1]; array[j+1] = temp; } } }} bubbleSort(numbers);console.log(numbers);

3. Selection sort• The algorithm works by scanning a list of items for the smallest element and then swapping that element for the one in the first position.• See the visual example below (red → smallest in step t${\displaystyle t}$, blue → comparison element in step t${\displaystyle t}$) for one pass through (results in swapping 0${\displaystyle 0}$ and 8${\displaystyle 8}$)•

a

8
5
2
6
9
3
1
4
0
7

a

8
5
2
6
9
3
1
4
0
7

a

8
5
2
6
9
3
1
4
0
7

a

8
5
2
6
9
3
1
4
0
7

a

8
5
2
6
9
3
1
4
0
7

a

8
5
2
6
9
3
1
4
0
7

a

8
5
2
6
9
3
1
4
0
7

a

8
5
2
6
9
3
1
4
0
7

a

8
5
2
6
9
3
1
4
0
7

a

0
5
2
6
9
3
1
4
8
7

• • We repeat the same as shown in the picture above until the entire list is sorted.• Time complexity → O(n2)${\displaystyle O\left(n^2\right)}$• Space complexity → O(1)${\displaystyle O(1)}$

Figure 2:Selection Sort

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; function selectionSort(array) { const length = array.length; for(let i = 0; i < length; i++){ // set current index as minimum let min = i; let temp = array[i]; for(let j = i+1; j < length; j++){ if (array[j] < array[min]){ //update minimum if current is lower that what we had previously min = j; } } array[i] = array[min]; array[min] = temp; } return array;}

4. Insertion sort• Insertion sort is useful for times when you're pretty sure the list is almost sorted.– In a best case scenario (when the list is almost sorted) you can get O(n)${\displaystyle O(n)}$.– Note: The average time complexity is still O(n2)${\displaystyle O\left(n^2\right)}$.• Insertion sort performs really good when it comes to small datasets.

Figure 3:Insertion Sort

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; function insertionSort(array) { const length = array.length; for (let i = 0; i < length; i++) { if (array[i] < array[0]) { //move number to the first position array.unshift(array.splice(i,1)[0]); } else { // only sort number smaller than number on the left of it. This is the part of insertion sort that makes it fast if the array is almost sorted. if (array[i] < array[i-1]) { //find where number should go for (var j = 1; j < i; j++) { if (array[i] >= array[j-1] && array[i] < array[j]) { //move number to the right spot array.splice(j,0,array.splice(i,1)[0]); } } } } }} insertionSort(numbers);console.log(numbers);

5. Merge sort• Unlike the bubble, selection, and insertion sorting algorithms, merge and quick sort use divide and conquer and recursion techniques.– Note: Divide & conquer is about dividing the problem down, to work on each subset and then combining the solutions.– Note: Whenever we see divide & conquer used in an algorithm, it usually give O(nlogn)${\displaystyle O(n\log n)}$.• How merge sort works?– Let's say we have this list → 6,5,3,1,8,7,2,4${\displaystyle 6,5,3,1,8,7,2,4}$– We divide the list in half → 6,5,3,1${\displaystyle 6,5,3,1}$ and 8,7,2,4${\displaystyle 8,7,2,4}$– We divide each subset in half again → 6,5${\displaystyle 6,5}$ and 3,1${\displaystyle 3,1}$ and 8,7${\displaystyle 8,7}$ and 2,4${\displaystyle 2,4}$– We keep dividing in half until we get one item → 6${\displaystyle 6}$ and 5${\displaystyle 5}$ and 3${\displaystyle 3}$ and ...– Now, we take the first two and sort them → then move to next two and sort it and so on ... (it's like doing the reverse tree) → 5,6${\displaystyle 5,6}$ and 1,3${\displaystyle 1,3}$ and 7,8${\displaystyle 7,8}$ and 2,4${\displaystyle 2,4}$– Now, we keep combining up → 1,3,5,6${\displaystyle 1,3,5,6}$ and 2,4,7,8${\displaystyle 2,4,7,8}$• Merge sort is one of the most efficient sorting algorithms.• Time complexity → O(nlogn)${\displaystyle O(n\log n)}$– n${\displaystyle n}$ → we still have to compare everything– logn${\displaystyle \log n}$ → is kind of like the height of the tree. Unlike bubble sort, we don't have to compare everything to everything. Here, we only compare local lists to each other.• Space complexity → O(n)${\displaystyle O(n)}$ → because we have to hold on to those divided up lists.• Merge sort is stable, i.e. if we have equivalent elements, it will keep the original order in the array.

Figure 4:Merge Sort, Splitting the list

Figure 5:Merge Sort, Merging lists together

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; function mergeSort (array) { if (array.length === 1) { return array } // Split Array in into right and left const length = array.length; const middle = Math.floor(length / 2) const left = array.slice(0, middle) const right = array.slice(middle) // console.log('left:', left); // console.log('right:', right); return merge( mergeSort(left), mergeSort(right) )} function merge(left, right){ const result = []; let leftIndex = 0; let rightIndex = 0; while(leftIndex < left.length && rightIndex < right.length){ if(left[leftIndex] < right[rightIndex]){ result.push(left[leftIndex]); leftIndex++; } else{ result.push(right[rightIndex]); rightIndex++ } } // console.log(left, right) return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));} const answer = mergeSort(numbers);console.log(answer);

6. Quick sort• Similar to merge sort, quick sort is also a divide & conquer algorithm.• Quick sort uses something called a pivoting technique to break the main list into smaller lists.– We pick a random pivot (or we can just simply pick the first element as pivot).* The role of the pivot value is to assist with splitting the list. * The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.– Bring all the numbers less than the pivot to its left and all the numbers greater than pivot to its right.– We split the list on the pivot number, and on the smaller lists, pick a pivot and repeat the above steps.• Time complexity → O(nlogn)${\displaystyle O(n\log n)}$• Space complexity → O(nlogn)${\displaystyle O(n\log n)}$ • Figure 6 shows that 54 will serve as our first pivot value. Since we have looked at this example a few times already, we know that 54 will eventually end up in the position currently holding 31. The partition process will happen next. It will find the split point and at the same time move other items to the appropriate side of the list, either less than or greater than the pivot value.

Figure 6:Quick Sort, The first pivot value

• Partitioning begins by locating two position markers—let’s call them leftmark and rightmark—at the beginning and end of the remaining items in the list (positions 1 and 8 in Figure 7). The goal of the partition process is to move items that are on the wrong side with respect to the pivot value while also converging on the split point. Figure 7 shows this process as we locate the position of 54.

Figure 7:Quick Sort, Finding split point for 54

• We begin by incrementing leftmark until we locate a value that is greater than the pivot value. We then decrement rightmark until we find a value that is less than the pivot value. At this point we have discovered two items that are out of place with respect to the eventual split point. For our example, this occurs at 93 and 20. Now we can exchange these two items and then repeat the process again.• At the point where rightmark becomes less than leftmark, we stop. The position of rightmark is now the split point. The pivot value can be exchanged with the contents of the split point and the pivot value is now in place (Figure 8). In addition, all the items to the left of the split point are less than the pivot value, and all the items to the right of the split point are greater than the pivot value. The list can now be divided at the split point and the quick sort can be invoked recursively on the two halves.

Figure 8:Quick Sort, Completing the partition process to find the split point for 54

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; function quickSort(array, left, right){ const len = array.length; let pivot; let partitionIndex; if(left < right) { pivot = right; partitionIndex = partition(array, pivot, left, right); //sort left and right quickSort(array, left, partitionIndex - 1); quickSort(array, partitionIndex + 1, right); } return array;} function partition(array, pivot, left, right){ let pivotValue = array[pivot]; let partitionIndex = left; for(let i = left; i < right; i++) { if(array[i] < pivotValue){ swap(array, i, partitionIndex); partitionIndex++; } } swap(array, right, partitionIndex); return partitionIndex;} function swap(array, firstIndex, secondIndex){ var temp = array[firstIndex]; array[firstIndex] = array[secondIndex]; array[secondIndex] = temp;} //Select first and last index as 2nd and 3rd parametersquickSort(numbers, 0, numbers.length - 1);console.log(numbers);

7. Which sort is best?• When to use insertion sort?– Insertion sort should be used with only a few items if your input is small or items are mostly sorted → in such cases it's really really fast and use a little space O(1)${\displaystyle O(1)}$.• When to use bubble sort?– You're never going to use bubble sort. – It's only used for educational purposes.• When to use selection sort?– Like bubble sort, you're not going to use it.• When to use merge sort?– Merge sort is really good because of divide & conquer.– The worst case scenario time complexity is still O(nlogn)${\displaystyle O(n\log n)}$– Merge sort is going to be expensive for space complexity (specially for large data).– If you had huge files that can't be sorted in memory, merge sort can be suitable for external sorting (outside of memory).• When to use quick sort?– Quick sort is better than merge sort.– Average time complexity is the same as merge sort but it has smaller space complexity than merge sort.– The one downside of quick sort is its worst case time complexity → O(n2)${\displaystyle O\left(n^2\right)}$.* If you don't pick the pivot properly, you could have really slow sorting.• When to use heap sort?– Heap sort resource– It's very similar to quick and merge sort.– But it has a space complexity → O(1)${\displaystyle O(1)}$.– Heap sort can sort in place and doesn't have the worst case scenario (i.e. O(n2)${\displaystyle O\left(n^2\right)}$) of quick sort or the memory usage of merge sort.– But, heap sort on average is slower than quick sort in most cases. Read more– Unless you're really worried about the worst case or memory then use heap sort → but most of the time you'd use either quick sort or merge sort. 8. Radix sort, Counting sort• Can we beat O(nlogn)${\displaystyle O(n\log n)}$?– Mathematically, it's impossible because we have to make comparisons for sorting.– However, you can improve this time complexity if you don't make comparisons.* There's a small section of inputs that allows us to beat this time complexity.* These are called non-comparison sorts.• Non-comparison sorts:– Counting sort– Radix sort • With comparison sort, we decided the order of the numbers based on asking the question: is this element bigger than the other one?• With non-comparison sorting, we're going to use the way that numbers and data is stored on our computers in 0${\displaystyle 0}$s and 1${\displaystyle 1}$s.– Note: These types of sorting algorithms only work with numbers, specifically integers in a restricted range.• Radix sort• Radix sort animation• Counting sort• Counting sort animation 9. Sorting interview

//#1 - Sort 10 schools around your house by distance:insertion sort //#2 - eBay sorts listings by the current Bid amount:radix or counting sort //#3 - Sort scores on ESPNQuick sort //#4 - Massive database (can't fit all into memory) needs to sort through past year's user dataMerge Sort //#5 - Almost sorted Udemy review data needs to update and add 2 new reviewsInsertion Sort //#6 - Temperature Records for the past 50 years in Canadaradix or counting SortQuick sort if decimal places //#7 - Large user name database needs to be sorted. Data is very random.Quick sort //#8 - You want to teach sortingBubble sort

• Check out what sorting algorithm Python uses under the hood?