DSA/SortingAlgo: SelectionSort

前言:

選擇排序是最易懂的排序法，作法如下: 假設有10個數字(index0~9)，先在前10個數字找最小值，與第0個數字交換，再從1~9個數字找最小值，與第1個數字交換，依此類推…

Outline:
1. 找最小值
2. swap
3. 實作selectionSort

Question1: 如何找array的最小值？

Solution: 假設arr的最小值是arr[0] i.e. min=arr[0]，再反覆與其他數字比，如果數字比min小，則更換min

class Main{
    public static void main(String[] args) {
        int arr[] = {3,6,2,7,1,8,4};
        int min= arr[0];
        for(int i = 0; i < arr.length; i++){
            if(arr[i] < min){min = arr[i];}
        }
        System.out.println("min= " + min);
    }
}

Question2: 如何交換數字

For example: i = 0, j = 1 如何交換 i, j 的值

有此程式語言支援 i, j = j, i (or [i, j] = [j, i])的語法，如Python與Javascript，但大多數是不支援的，如C/C++, Java，需使用以下方法

int temp = i;
i = j;
j = temp;

Question2–1: 如果寫一個swap函式，可以交換數字嗎？

一般來說不會特別寫swap函數，Python可直接寫i, j = j, i ;
Java 直接寫int temp = i; i=j; j=temp; 這樣子會比較有效率

但如果大量使用swap的話，寫成函式可增加可讀性。
也可以用加減法或是xor來實作，有興趣的話可以去查查看

def swap(a,b):
  temp = a
  a = b
  b = temp

a = 3, b= 5
swap(a,b)
print(a,b) # a = 3, b = 5

這裡只交換了區域變數a,b，為了更好理解，我們可以換一下代號，避免混淆

def swap(x,y):
  temp = x
  x = y
  y = temp

a = 3, b= 5
swap(a,b)
print(a,b) # a = 3, b = 5

這裡做的事情是把a = 3, b=5當作swap的引數，所以執行 swap(x = 3, y = 5)，將區域變數x,y的值交換後，就清除x,y變數，因此不會更改到a,b

以上稱為傳值呼叫(call by value)

但如果透過傳址呼叫(call by address)，或是參照呼叫(call by reference), 就可以把數字交換，常見的方法會是傳入陣列元素，或是物件

def swap(arr,i,j):
  temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp 

arr = [1,2,3,4,5]
swap(0,2)
print(arr) # [3,2,1,4,5]

或是在Java中，可將int轉成Integer物件(不推薦此做法)

接下來，我們來實作SelectionSort

import java.util.Arrays;
class Main{
    public static void main(String[] args) {
        int arr[] = {5,2,6,1,7,9,3,4,8,0};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void selectionSort(int[] arr){
        for(int i = 0; i < arr.length-1; i++){ // 做n-1次
            int minIndex = i; //最小元素的index
            for(int j = i; j < arr.length;j++){ //i ~ (n-1)
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if(minIndex!=i){
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;}
        }
    }
}

以length為5的array為例，arr[] = {0,1,2,3,4} //這裡的0,1,2,3,4代表index
總共要做4個pass
0~4 找min, 與0交換
1~4 找min, 與1交換
2~4 找min, 與2交換
3~4 找min, 與3交換
i = 0, 1, 2, 3 (0 ~ n-2)
j = i,..4 (i ~ n-1)