Shaker 排序法 - 改良的氣泡排序

說明

請看看之前介紹過的氣泡排序法，以 C 語言的實作為例：

void bubbleTo(int* arr, int to, int(*compar)(int, int)) {
    int i;
    for(i = 0; i < to - 1; i++) if(compar(arr[i + 1], arr[i]) < 0) {
        SWAP(arr[i + 1], arr[i]);
    }
}

void bubbleSort(int* arr, int len, int(*compar)(int, int)) {
    int i;
    for(i = 0; i < len; i++) { bubbleTo(arr, len - i, compar); }
}

實際上氣泡排序過程中，如果在bubbleTo中沒有發生過交換動作，左邊也已排序完成，bubbleSort的迴圈可以提前結束。也就是可以改為以下稍微增進效能。

int bubbleTo(int* arr, int to, int(*compar)(int, int)) {
   int i, swapped;
   for(i = 0, swapped = 0; i < to-1; i++) if(compar(arr[i+1], arr[i]) < 0) {
       SWAP(arr[i + 1], arr[i]);
       swapped = i;
   }
   return swapped;
}

void bubbleSort(int* arr, int len, int(*compar)(int, int)) {
    int i;
    for(i = 0; i < len && bubbleTo(arr, len - i, compar) != 0; i++);
}

最後交換發生的索引值會被bubbleTo傳回，如果為0，表示沒發生過交換動作，也就是左邊也已排序完成。整個排序過程中，排序的過程中，陣列右方排序好的元素會一直增加，反過來思考，如果此時氣泡排序方向不斷交換（也就是由左往右，再由右往左），利用兩邊排序好的元素，提早讓交換動作不再發生，是否可以增加排序效能？Shaker排序法利用這個觀念來改良氣泡排序法。

解法

在上述的氣泡排序法中，在交換動作不再發生時，提早讓排序結束，在排序過程中，陣列右方排序好的元素會一直增加，如我們的例子所示：

排序前：95 27 90 49 80 58 6 9 18 50

27 90 49 80 58 6 9 18 50 [95] 95浮出
27 49 80 58 6 9 18 50 [90 95] 90浮出
27 49 58 6 9 18 50 [80 90 95] 80浮出
27 49 6 9 18 50 [58 80 90 95] ......
27 6 9 18 49 [50 58 80 90 95] ......
6 9 18 27 [49 50 58 80 90 95] ......
6 9 18 [27 49 50 58 80 90 95] 沒有發生交換動作，排序結束

在第7步時，由於不再發生交換動作，排序提早結束，Shaker排序使用了這個概念，如果左右兩邊的元素都能先排序完成，如此未排序的元素會集中在中間，由於左右兩邊同時排序，中間未排序的部份將會很快的減少，不再出現交換動作的時間也會提前。

方法就在於氣泡排序的雙向進行，先讓氣泡排序由左向右進行，再來讓氣泡排序由右往左進行，如此完成一次排序的動作，而您必須使用left與right兩個旗標來記錄左右兩端已排序的元素位置。

一個排序的例子如下所示：

排序前：45 19 77 81 13 28 18 19 77 11

往右排序：19 45 77 13 28 18 19 77 11 [81]
向左排序：[11] 19 45 77 13 28 18 19 77 [81]

往右排序：[11] 19 45 13 28 18 19 [77 77 81]
向左排序：[11 13] 19 45 18 28 19 [77 77 81]

往右排序：[11 13] 19 18 28 19 [45 77 77 81]
向左排序：[11 13 18] 19 19 28 [45 77 77 81]

往右排序：[11 13 18] 19 19 [28 45 77 77 81]
向左排序：[11 13 18 19 19] [28 45 77 77 81]

如上所示，括號中表示左右兩邊已排序完成的部份，當left > right時，則排序完成。

實作：C Java Python Scala Ruby JavaScript Haskell

#include <stdio.h> 
#include <stdlib.h> 
#define LEN 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

void shakerSort(int*, int, int(*)(int, int)); 
int bubbleL2R(int* arr, int from, int to, int(*)(int, int));
int bubbleR2L(int* arr, int from, int to, int(*)(int, int));

void print(int*, int len);
int ascending(int, int);
int descending(int, int);

int main(void) { 
    int number[LEN] = {10, 9, 1, 2, 5, 3, 8, 7, 12, 11};

    shakerSort(number, LEN, ascending); 
    print(number, LEN);
    
    shakerSort(number, LEN, descending); 
    print(number, LEN);

    return 0; 
} 

void shakerSort(int* number, int len, int(*compar)(int, int)) {
    int left, right;
    for(left = 0, right = len - 1; 
        left < right; 
        right = bubbleL2R(number, left, right, compar), 
        left = bubbleR2L(number, left, right, compar));
} 

int bubbleL2R(int* arr, int left, int right, int(*compar)(int, int)) {
    int i, swapped;
    for(i = left, swapped = left; 
            i < right; i++) if(compar(arr[i + 1], arr[i]) < 0) {
        SWAP(arr[i + 1], arr[i]);
        swapped = i;
    }
    return swapped;
}

int bubbleR2L(int* arr, int left, int right, int(*compar)(int, int)) {
    int i, swapped;
    for(i = right, swapped = right; 
            i > left; i--) if(compar(arr[i], arr[i - 1]) < 0) {
        SWAP(arr[i], arr[i - 1]);
        swapped = i;
    }
    return swapped;
}

void print(int* arr, int len) {
    int i;
    for(i = 0; i < len; i++) { printf("%d ", arr[i]); } 
    printf("\n");
}

int ascending(int a, int b) { return a - b; }
int descending(int a, int b) { return -ascending(a, b); }

Java

import java.util.*;
import static java.lang.System.out;
import static java.util.Collections.swap;

public class Sort {
    public static <T extends Comparable<? super T>> 
        int ascending(T t1, T t2) {  return t1.compareTo(t2); }

    public static <T extends Comparable<? super T>> 
        int descending(T t1, T t2) { return -ascending(t1, t2); }
    
    public static <T> int bubbleL2R(
                List<T> list, int left, int right, Comparator<? super T> c) {
        int swapped = left;
        for(int i = left; i < right; i++) {
            if(c.compare(list.get(i + 1), list.get(i)) < 0) {
                swap(list, i + 1, i);
                swapped = i;
            }
        }
        return swapped;
    }
    
    public static <T> int bubbleR2L(
                List<T> list, int left, int right, Comparator<? super T> c) {
        int swapped = right;
        for(int i = right; i > left; i--) {
            if(c.compare(list.get(i), list.get(i - 1)) < 0) {
                swap(list, i, i - 1);
                swapped = i;
            }
        }
        return swapped;
    }
    
    public static <T> void sharkSort(
        List<T> list, Comparator<? super T> c) {
        for(int left = 0, right = list.size() - 1; 
            left < right; 
            right = bubbleL2R(list, left, right, c), 
            left = bubbleR2L(list, left, right, c));
    }
    
    public static <T extends Comparable<? super T>> 
        void sharkSort(List<T> list) { sharkSort(list, Sort::ascending); }
    
    
    public static void main(String[] args) {
        List<Integer> list = 
            new ArrayList<>(Arrays.asList(10, 9, 1, 2, 5, 3, 8, 7, 12, 11));
        
        sharkSort(list);
        out.println(list);
        
        sharkSort(list, Sort::descending);
        out.println(list);
    }
}

Python

def ascending(a, b): return a - b
def descending(a, b): return -ascending(a, b)
    
def sharkSort(xs, compare = ascending):
    return [] if not xs else __up(xs, compare)
    
def __up(xs, compare):
    if not xs[1:]: 
        return xs
    else:
        s = __down(xs[1:], compare)
        return ([s[0]] + __up([xs[0]] + s[1:], compare) 
                    if compare(xs[0], s[0]) > 0
                    else [xs[0]] + s)

def __down(xs, compare):
    if not xs[0:-1]: 
        return xs
    else:
        s = __up(xs[0:-1], compare)
        return (__down(s[0:-1] + [xs[-1]] , compare) + [s[-1]]
                    if compare(xs[-1], s[-1]) < 0
                    else s + [xs[-1]])
                    
list = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11]

print(sharkSort(list))
print(sharkSort(list, descending))

Scala

object Sort {    
    def shark[T](xs: List[T], compare: (T, T) => Boolean):List[T] = {
        if(xs.isEmpty) Nil
        else up(xs, compare)
    }
    private def up[T](xs: List[T], 
                   compare: (T, T) => Boolean): List[T] = {
        if(xs.tail.isEmpty) xs
        else {
            val s = down(xs.tail, compare)
            if(!compare(xs.head, s.head)) 
                s.head :: up(xs.head :: s.tail, compare)
            else xs.head :: s
        }
    }
    private def down[T](xs: List[T], 
                   compare: (T, T) => Boolean): List[T] = {
        if(xs.init.isEmpty) xs
        else {
            val s = up(xs.init, compare)
            if(compare(xs.last, s.last)) 
                 down(s.init ++ List(xs.last), compare) ++ List(s.last)
            else s ++ List(xs.last)
        }
    }
}

val list = List(10, 9, 1, 2, 5, 3, 8, 7, 12, 11)

println(Sort.shark[Int](list, _ > _))
println(Sort.shark[Int](list, _ < _))

Ruby

class Sort
    @@ascending = ->(a, b) { a - b }
    @@descending = ->(a, b) { -@@ascending.call(a, b) }
    
    def self.ascending; @@ascending end
    def self.descending; @@descending end
    
    def self.shark(xs, compare)
        xs.empty? ? [] : up(xs, compare)
    end
    def self.up(xs, compare)
        if xs[1..-1].empty?
            xs
        else
            s = down(xs[1..-1], compare)
            compare.call(xs[0], s[0]) > 0 ? 
                [s[0]] + up([xs[0]] + s[1..-1], compare) : [xs[0]] + s
        end
    end
    private_class_method :up
    
    def self.down(xs, compare)
        if xs[0..-2].empty?
            xs
        else
            s = up(xs[0..-2], compare)
            compare.call(xs[-1], s[-1]) < 0 ? 
                down(s[0..-2] + [xs[-1]] , compare) + [s[-1]] : s + [xs[-1]]
        end
    end
    private_class_method :down
end

list = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11]

print(Sort.shark(list, Sort.ascending).to_s + "\n")
print(Sort.shark(list, Sort.descending).to_s + "\n")

JavaScript

function swap(list, i, j) {
    var ele = list[i];
    list[i] = list[j];
    list[j] = ele;
}

function ascending(a, b) {return a - b;}
function descending(a, b) {return -ascending(a, b);}
    
function sharkSort(list, compare) {
    for(var left = 0, right = list.length - 1; 
        left < right;
        right = bubbleL2R(list, left, right, compare), 
        left = bubbleR2L(list, left, right, compare));
}

function bubbleL2R(list, left, right, compare) {
    for(var i = left, swapped = left; i < right; i++) {
        if(compare(list[i + 1], list[i]) < 0) {
            swap(list, i + 1, i);
            swapped = i;
        }
    }
    return swapped;
}

function bubbleR2L(list, left, right, compare) {
    for(var i = right, swapped = right; i > left; i--) {
        if(compare(list[i], list[i - 1]) < 0) {
            swap(list, i, i - 1);
            swapped = i;
        }
    }
    return swapped;
}

var list = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11];

sharkSort(list, ascending);
print(list);

sharkSort(list, descending);
print(list);

Haskell

ascending a b = a - b
descending a b = -ascending a b

sharkSort xs compare =
    if xs == [] then [] else up xs compare
    
up xs compare =
    if tail xs == []
        then xs
        else
            let s = down (tail xs) compare
            in if compare (head xs) (head s) > 0
                    then head s : up (head xs : tail s) compare
                    else head xs : s
                    
down xs compare =
    if init xs == []
        then xs
        else
            let s = up (init xs) compare
            in if compare (last xs) (last s) < 0
                    then down (init s ++ [last xs]) compare ++ [last s]
                    else s ++ [last xs]

main = sequence [print \$ sharkSort list ascending, 
                 print \$ sharkSort list descending]
    where list = [10, 9, 1, 2, 5, 3, 8, 7, 12, 11]