[MasterThe Coding Interview]Algorithms:Sorting
本篇為MasterThe Coding Interview教學影片筆記文
排序存在網路世界的任何地方,Google的搜尋引擎、Amazon的商品排序,價錢、評論都可以做排序,每個公司都會有自己排序的方法,來適應各種不同的資料,讓排序可以耗費較少的複雜度達到要求。
在javaScript的sort方法裡,會把所有的element轉換成string在進行比對,這樣的方法會出現以下的錯誤
1 | const basket = [2 , 3 , 65 , 34 , 1 , 7] |
Bubble Sort
從第一個和第二個元素開始比較,如果左邊比右邊大,就把兩個元素交換,再來是第二跟第三個元素比較,以此類推直到所有元素都比較完,就可以確定最右邊的元素一定是最大,接著再重複以上步驟直到所有元素都排序完成。
1 | const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; |
Selection Sort
從頭開始找最小或最大的元素,並且跟第一個交換,再來從第二個開始找,找到後再跟第二個交換,以此類推到全部的元素都排序完成。
1 | const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; |
Insertion Sort
先固定第一個元素,判斷第二個比較大還是小,並且固定住元素,接著第三個元素比較已經固定的元素陣列,找到合適的地方插入,以此類推直到所有元素完成排序。
1 | const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; |
Merge Sort
跟前三種sort的方法不一樣,前三種都用到了巢狀迴圈,時間複雜度一定會在O(n^2),但merge sort利用了Dividde and Conquer的方法,先把整個陣列分割到不可分割為止,再經過排序把陣列倆倆合併起來,只要O(nlogn)即可完成。
1 | const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; |
Quick Sort
跟merge sort一樣用到divide and conquer的想法,比較不一樣的是這邊是會先選定一個pivot,比他大的放右邊,比她小的放左邊,透過這個pivot把陣列分割成兩個部分,每個部份再用相同的方式比較和排序直到所有元素都完成為止。如果有選到好的pivot可以幾乎都平分陣列,那時間複雜度就可以維持在O(nlogn),如果每次選定的pivot都剛好是陣列裡的最大值或最小值,沒有有效的分割的話,時間複雜度就會是O(n^2),不過相較於merge sort,quick sort的空間複雜度是O(logn)。
1 | const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; |
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
Sorting Interview
- Sort 10 schools around your house by distance → Insertion Sort(資料小且相近)
- eBay sorts listings by the current Bid amount. → Radix or Counting Sort(數字且有小範圍限制住)
- Sport scores on ESPN → Quick Sort(資料雜亂)
- Massive database (can’t fit all into memory) needs to sort through past year’s user data →Merge Sort(資料量太大,需要確保時間複雜度是O(nlogn))
- Almost sorted Udemy review data needs to update and add 2 new reviews →Insertion Sort(雖然資料量大但多數已經完成排序)
- Temperature Records for the past 50 years in Canada → Quick Sort , Radix or Counting Sort(如果資料量都是數字且有範圍限制住就可以用 Radix or Counting Sort)
- Large user name database needs to be sorted. Data is very random. → Merge Sort(資料雜亂要確保時間複雜度不會過於糟糕)
- 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功能等。