iT邦幫忙

DAY 10
3

用Javascript征服演算法系列 第 7

用Javascript征服演算法 (6-Quick Sort)

Quick Sort~Sort如期名,快來看看他多快吧!!!!
今天要來介紹公認在某些case下,使用此排序法速度是最快的,那就是Quick Sort

Quick Sort主要是使用了Divide and Conquer的觀念,什麼是divide and conquer的觀念呢,那就是將大問題切割成小問題,等解決小問題之後,大問題也就解決了,如果小問題依舊很難,那就在切割成更小的問題,就能依序擊破,最後就能解決原本的大問題了

因此,Quick Sort在排序時,會選一個pivot的值,與其比較後,形成一段都比pivot小的集合與一段都比pivot大的集合,最後再將pivot放置奇中央,這樣就完成了divide得的動作,而conquer得部分,就是將小集合與大集合中間放置pivot後,再將小集合與大集合視為獨立的集合,在進行quick sort排序,如此一來,最後就能完成排序

一般而言,會說quick sort會是最快速排序法,是因為多數情況下可以獲得很好的效率,而為什麼多數情況下quick sort都能有比較好得效率?我想是因為他將排序切割成小的問題後,在解決小問題時,很有可能選中的pivot剛好就是能將小集合與大集合元素的個數左右相同的pivot,兩邊元素個數一樣,代表小問題的元素不會太多,那這樣就容易一下就排序完成

因此由上述可知,對quick sort來說,如何去選取pivot很可能就會影響整體的排序效率,而一般在書上可以見得的選取方式,最普通的就是直接選取數列開頭的元素當作pivot,之後就能分出一集合都比pivot小的元素集合,而另外一側則是都比pivot大的集合(如圖)

而此實作的方式大致上就是

  1. 設定變數i由左到右掃描,直到找到比pivot大的值
  2. 設定變數j由右到左掃描, 直到找到比pivot小的值
  3. 將i與j所對定的陣列值交換
  4. 如果i > j則表示排序已完成
  5. 將pivot所在陣列值與i-1所在陣列值互換
  6. 將左右兩側陣列在作遞迴排序

在此特別要介紹一下在演算法聖經Introduction to Algorithms中所計載的方式

以下為書上計載的pseudo code

QUICKSORT(A, p, r) 
   if p < r 
     then q <- PARTITION(A, p, r) 
               QUICKSORT(A, p, q-1) 
               QUICKSORT(A, q+1, r) 
end QUICKSORT 

PARTITION(A, p, r) 
    x <- A[r] 
    i <- p-1 
    for j <- p to r-1 
        do if A[j] <= x 
                 then  i <- i+1 
                         exchange A[i]<->A[j] 
    exchange A[i+1]<->A[r] 
    return i+1 
end PARTITION  

此方法中,是透過選取數列最後一項(或最左邊)為pivot的值,而i與j都會同時往右的方式去尋找出比pivot小集合與比pivot大的集合

上述方法可以大概去想像,i就是比pivot小的集合指標,j呢就是往右不斷尋找陣列值的變數,因此可以想見,只有在j所在的陣列值比pivot小的時候,我的i旗標才需要往右前進,表示又有一個元素是屬於比pivot小的集合裡囉

以下為實際運作pseudo code的演譯

完成後

此方法之所以有名,似乎是因為他pivot的選取方式,能夠使得pivot左右兩邊的小集合經常都能分布平均的個數,但這部分我仍舊不太清楚為何? 可能要在查查資料,希望明天可以進一步解釋

以上就是quick sort的介紹,下一篇就來實作看看吧,初次看或很久沒看quick sort都會有點難進入狀況,但我上圖的演繹應該可以讓各位初學或者複習者更快進入狀況: )

下一篇GOGO~~汗


上一篇
用Javascript征服演算法 (5-bubble sort&實作)
下一篇
用Javascript征服演算法 (6-Quick Sort-實作)
系列文
用Javascript征服演算法10
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言