Sorting Algorithm, 排序演算法

在資工的世界裡，第一個要學的演算法就是排序，而這也是進入演算法的一個開始，世上到底有多少排序的方法呢？其實很多，而且大多數都不在教科書上出現。有興趣的人可以上Wiki找一下，可以看到很多不同種的排序及時間。大部分會教的有Bubble Sort，Selection Sort，Insertion Sort，Merge Sort，Heap Sort，Quick Sort。在不同的應用上，比較常見的有Bubble Sort，Heap Sort及Quick Sort，原因無他，都是因為實作方便及好維護。至於時間上的考量，一般來說會使用Quick Sort及Heap Sort，但因為Quick Sort在Worst Case中是O(n^2)，所以很多情形下，還是比較偏好Heap Sort。

Bubble pseudo code:

procedure bubbleSort( A : list of sortable items ) defined as:
  n := length( A )
  do
    swapped := false
    n := n - 1
    for each i in 0 to n - 1  inclusive do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped
end procedure

Heap pseudo code:

 function heapSort(a, count) is
     input: an unordered array a of length count

     (first place a in max-heap order)
     heapify(a, count)

     end := count - 1
     while end > 0 do
         (swap the root(maximum value) of the heap with the last element of the heap)
         swap(a[end], a[0])
         (put the heap back in max-heap order)
         siftDown(a, 0, end-1)
         (decrease the size of the heap by one so that the previous max value will
         stay in its proper placement)
         end := end - 1

function heapify(a,count) is
     (start is assigned the index in a of the last parent node)
     start := (count - 2) / 2
    
     while start ≥ 0 do
         (sift down the node at index start to the proper place such that all nodes below
         the start index are in heap order)
         siftDown(a, start, count-1)
         start := start - 1
     (after sifting down the root all nodes/elements are in heap order)

function siftDown(a, start, end) is
     input: end represents the limit of how far down the heap
                   to sift.
     root := start

     while root * 2 + 1 ≤ end do          (While the root has at least one child)
         child := root * 2 + 1           (root*2+1 points to the left child)
         (If the child has a sibling and the child's value is less than its sibling's...)
         if child + 1 ≤ end and a[child] < a[child + 1] then
             child := child + 1           (... then point to the right child instead)
         if a[root] < a[child] then       (out of max-heap order)
             swap(a[root], a[child])
             root := child                (repeat to continue sifting down the child now)
         else
             return

Quick pseudo code:

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1 
         return array 
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right] // Move pivot to end
     storeIndex := left
     for i from left to right − 1
         if array[i] ≤ pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right] // Move pivot to its final place
     return storeIndex

 procedure quicksort(array, left, right)
     if right > left
         select a pivot index (e.g. pivotIndex := left)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex - 1)
         quicksort(array, pivotNewIndex + 1, right)

相關的程式碼，寫好再放上...