[JAVA]Bubble Sort 及 Shaker Sort－Coding Life

關於氣泡排序的說明網路上很多，而且這應該是學校必教的項目，所以就不說明了~

如果有需要細項說明的話請參考這裡

為了測試執行的效率，所以設定了一個共1000個值的List給Bubble Sort做處理

第一種方法是過去學校教的，而第二種方法其實看起來沒什麼差，可是執行上出現15ms的差異

一、執行時間約62ms

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import static java.util.Collections.swap;

public class BubbleSort {
  public static void main(String[] args) throws InterruptedException {
    long time1, time2;
    time1 = System.currentTimeMillis();
		
    List list = new ArrayList<>();
		
    for(int i=0; i<1000; i++){
      list.add(new Random().nextInt(1000));
    }
		
    Comparator compar = new Comparator() {
      public int compare(Integer num1, Integer num2) {
	return num1 - num2;
      }	    
    };
		
    bubbleSort(list, compar);
    System.out.println(list);
        
    time2 = System.currentTimeMillis();
    System.out.println((time2-time1) + "/ms");
  }
	
  public static void bubbleSort(List list, Comparator compar) {
    for(int i = 0; i < list.size(); i++) { 
      for(int j = 0; j < list.size() - i - 1; j++) {
        if(compar.compare(list.get(j + 1), list.get(j)) < 0) {
          swap(list, j + 1, j);
        }
      }
    }
  }
}

二、執行時間約47ms

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import static java.util.Collections.swap;

public class BubbleSort {
  public static void main(String[] args) throws InterruptedException {
    long time1, time2;
    time1 = System.currentTimeMillis();
		
    List list = new ArrayList<>();
		
    for(int i=0; i<1000; i++){
      list.add(new Random().nextInt(1000));
    }
		
    Comparator compar = new Comparator() {
      public int compare(Integer num1, Integer num2) {
	return num1 - num2;
      }	    
    };
		
    bubbleSort(list, compar);
    System.out.println(list);
        
    time2 = System.currentTimeMillis();
    System.out.println((time2-time1) + "/ms");
  }
	
  public static void bubbleSort(List list, Comparator compar) {
    for(int i = 0; i < list.size(); i++) { 
      bubbleSwap(list, list.size() - i, compar); 
    }
  }
	
  public static void bubbleSwap(List list, int to, Comparator compar) {
    for(int i = 0; i < to - 1; i++) {
      if(compar.compare(list.get(i + 1), list.get(i)) < 0) {
	swap(list, i + 1, i);
      }
    }
  }
}

但在一些範例中會發現，List中的資料可能排序到一半就排完了，後面的資料雖然都沒有做到交換的動做，但還是一個一個做檢查

為了避免這些不必要的動作，要多加一個檢查，當資料完全沒做到交換的動做時List就視為排序完成並離迴圈

這樣執行的結果平均31~37ms就能執行完成

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import static java.util.Collections.swap;

public class BubbleSort {
  public static void main(String[] args) throws InterruptedException {
    long time1, time2;
    time1 = System.currentTimeMillis();
		
    List list = new ArrayList<>();
		
    for(int i=0; i<1000; i++){
      list.add(new Random().nextInt(1000));
    }
		
    Comparator compar = new Comparator() {
      public int compare(Integer num1, Integer num2) {
	return num1 - num2;
      }	    
    };
		
    bubbleSort(list, compar);
    System.out.println(list);
        
    time2 = System.currentTimeMillis();
    System.out.println((time2-time1) + "/ms");
  }
	
  public static void bubbleSort(List list, Comparator compar) {
    for(int i = 0; i < list.size(); i++) { 
      if(bubbleSwap(list, list.size() - i, compar)) break; 
    }
  }
	
  public static boolean bubbleSwap(List list, int to, Comparator compar) {
    boolean complete = true;
		
    for(int i = 0; i < to - 1; i++) {
      if(compar.compare(list.get(i + 1), list.get(i)) < 0) {
	swap(list, i + 1, i);
	complete = false;
      }
    }
		
    return complete;
  }
}

最後是 Shark Sort 又稱為雙向氣泡排序法

以氣泡排序法為基礎做雙向排序，讓未排序的值集中到 List 中間

而雙向排序會讓中間未排序的部份快速減少，結束的時間自然也就提前了

而 Shark Sort 的執行速度則是穩穩的在31ms上下

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

import static java.util.Collections.swap;

public class BubbleSort {
  public static void main(String[] args) throws InterruptedException {
    long start, end;
    start = System.currentTimeMillis();
		
    List list = new ArrayList<>();
		
    for(int i=0; i<1000; i++){
      list.add(new Random().nextInt(1000));
    }
		
    Comparator com = new Comparator() {
      public int compare(Integer num1, Integer num2) {
        return num1 - num2;
      }
    };
		
    sharkSort(list, com);
    System.out.println(list);
        
    end = System.currentTimeMillis();
    System.out.println((end-start) + "/ms");
  }
	
  public static void sharkSort(List list, Comparator com) {
    int left = 0;
    int right = list.size() -1;
    while(left < right){
      right = leftToRight(list, left, right, com);
      left = rightToLeft(list, left, right, com);
    }
    //上面的while也可以改寫成下面的for，但下面這樣的寫法不易閱讀所以不建議這樣寫
    //for(int left = 0, right = list.size() - 1; left < right; right = leftToRight(list, left, right, com), left = rightToLeft(list, left, right, com));
  }
	
  public static int leftToRight(List list, int left, int right, Comparator com) {
    int tag = left;
    for(int i = left; i < right; i++) {
      if(com.compare(list.get(i + 1), list.get(i)) < 0) {
        swap(list, i + 1, i);
        tag = i;
      }
    }
    return tag;
  }
	 
  public static int rightToLeft(List list, int left, int right, Comparator com) {
    int tag = right;
    for(int i = right; i > left; i--) {
      if(com.compare(list.get(i), list.get(i - 1)) < 0) {
        swap(list, i, i - 1);
        tag = i;
      }
    }
    return tag;
  }
}

然而上面的方法只能給型態為 Integer 的資料使用

為了讓程式能夠 reuse，下面將它加入泛型的用法，使它可以排序其它型態的資料，並將 Sort 程式獨立出來

Main:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class SortDemo {
  public static void main(String[] args) {
    List list = new ArrayList<>();
		
    for(int i=0; i<1000; i++){
      list.add(new Random().nextInt(1000));
    }
		
    Comparator com = new Comparator() {
      public int compare(Integer num1, Integer num2) {
	return num1 - num2;
      }
    };
		
    list = new Sort().sharkSort(list, com);
    System.out.println(list);
  }
}

Sort:

import java.util.Comparator;
import java.util.List;
import static java.util.Collections.swap;

public class Sort {
  public <T> List sharkSort(List<T> list, Comparator<? super T> com) {
    int left = 0;
    int right = list.size() -1;
      while(left < right){
        right = leftToRight(list, left, right, com);
	left = rightToLeft(list, left, right, com);
      }
      return list;
  }
	
  private <T> int leftToRight(List<T> list, int left, int right, Comparator<? super T> com) {
    int tag = left;
    for(int i = left; i < right; i++) {
      if(com.compare(list.get(i + 1), list.get(i)) < 0) {
        swap(list, i + 1, i);
        tag = i;
      }
    }
    return tag;
  }
	 
  private <T> int rightToLeft(List<T> list, int left, int right, Comparator<? super T> com) {
    int tag = right;
    for(int i = right; i > left; i--) {
      if(com.compare(list.get(i), list.get(i - 1)) < 0) {
	swap(list, i, i - 1);
	tag = i;
      }
    }
    return tag;
  }
}