homework for new c language programer

hw1.md

作業一 Sorting

實作 sorting algorithm 以熟悉演算法與程式語言。

預計實作

• bubble sort
• insertion sort
• merge sort
• quick sort
• heap sort

理論上難度應該是由易到難

根據虛擬碼，使用純 c language，實作上述演算法。

統一的規格

所有的演算法都會大致上會有下列的規格

void Sort(int target[], int len);

預期 Sort 執行完之後會得到已經由小到大排序好的 target。

Bubble sort

沒什麼好說的，最基礎沒效率現實中除了練習以外不太會用到的排序方法。

function bubble_sort (array, length) {
    var i, j;
    for(i from 0 to length-1){
        for(j from 0 to length-1-i){
            if (array[j] > array[j+1])
                swap(array[j], array[j+1])
        }
    }
}

Insertion sort

在已經大致符合排序的對象中，插入排序的複雜度可以達到 $$ O(n) $$

Merge Sort

Quick Sort

Heap Sort