[MasterThe Coding Interview]Algorithms:Sorting

本篇為MasterThe Coding Interview教學影片筆記文

排序存在網路世界的任何地方,Google的搜尋引擎、Amazon的商品排序,價錢、評論都可以做排序,每個公司都會有自己排序的方法,來適應各種不同的資料,讓排序可以耗費較少的複雜度達到要求。

在javaScript的sort方法裡,會把所有的element轉換成string在進行比對,這樣的方法會出現以下的錯誤

1
2
3
4
5
6
7
const basket = [2 , 3 , 65 , 34 , 1 , 7]
basket.sort() //1 , 2 , 3 , 34 , 65 , 7

//correct way
basket.sort(function(a,b){
return a - b
})

Bubble Sort

從第一個和第二個元素開始比較,如果左邊比右邊大,就把兩個元素交換,再來是第二跟第三個元素比較,以此類推直到所有元素都比較完,就可以確定最右邊的元素一定是最大,接著再重複以上步驟直到所有元素都排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function bubbleSort(array) { //O(n^2)
for(let i = 0 ; i < array.length ; i++){
for(let j = 0 ; j < array.length - i ; j++){
if(array[j] > array[j + 1]){
[array[j + 1] , array[j]] = [array[j] , array[j + 1]]
}
}
}
}

bubbleSort(numbers);
console.log(numbers);

Selection Sort

從頭開始找最小或最大的元素,並且跟第一個交換,再來從第二個開始找,找到後再跟第二個交換,以此類推到全部的元素都排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function selectionSort(array) { //O(n^2)
for(let i = 0 ; i < array.length ; i++){
let minIndex = i;
for(let j = i + 1 ; j < array.length ; j++){
if(array[minIndex] > array[j]){
minIndex = j;
}
}
[array[i] , array[minIndex]] = [array[minIndex] , array[i]]
}
}

selectionSort(numbers);
console.log(numbers);

Insertion Sort

先固定第一個元素,判斷第二個比較大還是小,並且固定住元素,接著第三個元素比較已經固定的元素陣列,找到合適的地方插入,以此類推直到所有元素完成排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function insertionSort(array) { //O(n^2)
for(let i = 1 ; i < array.length ; i++){
let insertIndex = i;
for(let j = i - 1 ; j >= 0 ; j--){
if(array[i] < array[j]){
insertIndex = j
}
}
array.splice(insertIndex , 0 , array.splice(i , 1)[0])
}
}

insertionSort(numbers);
console.log(numbers);

Merge Sort

跟前三種sort的方法不一樣,前三種都用到了巢狀迴圈,時間複雜度一定會在O(n^2),但merge sort利用了Dividde and Conquer的方法,先把整個陣列分割到不可分割為止,再經過排序把陣列倆倆合併起來,只要O(nlogn)即可完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function mergeSort (array) {
if (array.length === 1) {
return array
}
let left = array.slice(0 , parseInt(array.length / 2))
let right = array.slice(parseInt(array.length / 2) , array.length)

return merge(
mergeSort(left),
mergeSort(right)
)
}

function merge(left, right){
let ans = []
let l = 0, r = 0
while(l < left.length && r < right.length){
if(left[l] < right[r]){
ans.push(left[l]);
l++;
}else{
ans.push(right[r]);
r++;
}
}
return ans.concat(left.slice(l)).concat(right.slice(r))
}

const answer = mergeSort(numbers);
console.log(answer);

Quick Sort

跟merge sort一樣用到divide and conquer的想法,比較不一樣的是這邊是會先選定一個pivot,比他大的放右邊,比她小的放左邊,透過這個pivot把陣列分割成兩個部分,每個部份再用相同的方式比較和排序直到所有元素都完成為止。如果有選到好的pivot可以幾乎都平分陣列,那時間複雜度就可以維持在O(nlogn),如果每次選定的pivot都剛好是陣列裡的最大值或最小值,沒有有效的分割的話,時間複雜度就會是O(n^2),不過相較於merge sort,quick sort的空間複雜度是O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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){
[array[i] , array[partitionIndex]] = [array[partitionIndex] , array[i]];
partitionIndex++;
}
}
[array[right] , array[partitionIndex]] = [array[partitionIndex] , array[right]];
return partitionIndex;
}

//Select first and last index as 2nd and 3rd parameters
quickSort(numbers, 0, numbers.length - 1);
console.log(numbers);

Untitled

Untitled

Which Sort Is Best?

不同的資料有不同的方法,假設今天資料量少少的且大多都排序好,Insertion Sort就可以有將近O(n)的速度,空間複雜度也可以有O(1)。Bubble Sort和Select Sort都不太適合用在實作上面,時間複雜度永遠都是O(n^2)。如果資料量很大且有足夠的memory可以使用的話,merge Sort絕對是最好的選擇,不管資料如何時間複雜度絕對是O(nlogn)。Quick Sort也不錯,甚至空間複雜度只有O(logn),比merge Sort還要更好,但只要pivot沒有選好的話,他的時間複雜度會降低到O(n^2),這是特別要注意到的地方。

補充:Heap Sort

以上的方法我們會把他歸類成comparison sort,在排序的過程中有兩兩比較,相反的,有另外一群排序的方法叫做non-comparison sort,透過其他方法排序,比較常見的叫做Radix Sort和Counting Sort,雖然時間複雜度可以壓在O(nlogn)以下,但對於資料的條件有限制,必須要小範圍的數字才能使用。

補充:Radix Sort

補充:Radix Sort Animation

補充:Counting Sort

補充:Counting Sort Animation

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. Sport scores on ESPN → Quick Sort(資料雜亂)
  4. Massive database (can’t fit all into memory) needs to sort through past year’s user data →Merge Sort(資料量太大,需要確保時間複雜度是O(nlogn))
  5. Almost sorted Udemy review data needs to update and add 2 new reviews →Insertion Sort(雖然資料量大但多數已經完成排序)
  6. Temperature Records for the past 50 years in Canada → Quick Sort , Radix or Counting Sort(如果資料量都是數字且有範圍限制住就可以用 Radix or Counting Sort)
  7. Large user name database needs to be sorted. Data is very random. → Merge Sort(資料雜亂要確保時間複雜度不會過於糟糕)
  8. You want to teach sorting for the first time → Bubble Sort or Select Sort

javaScript中有自己的sort function,但它並不是在語言中實作,而是在瀏覽器的javaScript引擎中實作,例如chrome中的V8是用merge sort 或insertion sort實作這個sort,取決於資料的大小。mozilla是用quick sort實作sort功能等。