Sorting

剛開始先介紹排序，把數字由小排到大或由大排到小。

以下是相關排序演算法的時間複雜度跟空間複雜度

今天是 Bubble Sort 和 Selection Sort 的演算法。

Bubble Sort

Bubble Sort 通常用於對小型資料集進行排序。

它的原理相對簡單，但效率較低，因此在處理大型資料集時不太實用。

以下是 Bubble Sort 的基本工作原理：

1. 比較相鄰元素： 演算法從列表的第一個元素開始，比較相鄰的兩個元素。

2. 交換元素位置： 如果這兩個元素的順序不正確，就交換它們的位置，將較大的元素移到右邊。

3. 繼續比較和交換： 接下來，演算法繼續比較並交換相鄰元素，直到達到列表的末尾。這樣，最大的元素會像氣泡一樣冒到列表的最右邊。

4. 重複以上步驟： 重複執行以上步驟，每次都會將當前未排序部分的最大元素冒泡到合適的位置。

5. 重複多次： 以上步驟需要重複多次，直到整個列表都排好序。

Bubble Sort 的優點是其實現簡單易懂，但它的缺點是效率較低，特別是在大型資料集上。它的時間複雜度為，其中是要排序的元素數量。

因此，對於大規模資料集，更高效的排序演算法如 Quick Sort 或 Merge Sort 通常更合適。

Bubble Sort 通常用於教學和理解排序演算法的基本原理，而不是實際應用中的首選演算法。

// Bubble sort algorithm

class BubbleSort {
    fun sort(arr: IntArray) {
        val n = arr.size
        for (i in 0 until n - 1) {
            for (j in 0 until n - i - 1) {
                if (arr[j] > arr[j + 1]) {
                    // swap arr[j+1] and arr[j]
                    val temp = arr[j]
                    arr[j] = arr[j + 1]
                    arr[j + 1] = temp
                }
            }
        }
    }
}

/*
Sorted array
11 12 22 25 34 64 90
*/

// main function
fun main(args: Array<String>) {
    val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    val bubbleSort = BubbleSort()
    bubbleSort.sort(arr)
    println("Sorted array")
    for (i in arr.indices) {
        print(arr[i].toString() + " ")
    }
}

Selection Sort

Selection Sort 主要思想是在未排序的數列中，從頭至尾不斷選擇最小（或最大）的元素，然後將它與未排序部分的第一個元素進行交換，以此方式逐步將數列分為已排序和未排序兩部分，最終完成排序。

Selection Sort 的主要步驟有：

1. 首先，將整個數列視為未排序部分。
2. 在未排序部分中尋找最小的元素，並記錄其位置。
3. 將找到的最小元素與未排序部分的第一個元素交換位置，使其成為已排序部分的一部分。
4. 現在，已排序部分的長度增加了一個元素，未排序部分的長度減少了一個元素。
5. 重複上述步驟，直到整個數列都排好序為止。

Selection Sort 的時間複雜度為，其中是要排序的元素數量。

在處理大型數據集時，通常建議使用更高效的排序算法，以減少排序時間。

// Selection sort

class SelectionSort {
    fun sort(arr: IntArray) {
        val n = arr.size
        for (i in 0 until n - 1) {
            var min_idx = i
            for (j in i + 1 until n) if (arr[j] < arr[min_idx]) min_idx = j
            // Swap the found minimum element with the first
            // element
            val temp = arr[min_idx]
            arr[min_idx] = arr[i]
            arr[i] = temp
        }
    }
}

/*
Sorted array
-8 7 12 22 25 34 64 90
*/

// main function
fun main(args: Array<String>) {
    val arr = intArrayOf(12, 7, -8, 22, 25, 34, 64, 90)
    val selectionSort = SelectionSort()
    selectionSort.sort(arr)
    println("Sorted array")
    for (i in arr.indices) {
        print(arr[i].toString() + " ")
    }
}

所有 Code 可以在 Github 找到 ～

明天接著介紹 Insertion Sort 和 Merge Sort

Reference

• If Sorting Algorithms Were Pokemon
• Bubble sort in C
• Selection Sort