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]
