Shaker 排序- 改良的氣泡排序

December 9, 2021

氣泡排序時,若交換動作不再發生,可以提早讓排序結束,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](58 浮出)
27 6 9 18 49 [50 58 80 90 95](50 浮出)
6 9 18 27 [49 50 58 80 90 95](49 浮出)
6 9 18 [27 49 50 58 80 90 95](沒有發生交換動作,排序結束)

Shaker 排序使用了這個概念,將氣泡排序雙向進行,左右兩邊的元素排序完成,未排序的元素會集中在中間,不再交換的時間有機會提前。

氣泡排序雙向進行時,先讓氣泡排序由左向右進行,再讓氣泡排序由右往左進行,如此完成一次排序的動作,例如排序前 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](向左排序)

程式實作

#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); } 
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);
    }
}
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))
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, _ < _))
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")
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);
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]