Quiz 11
===
# Index
1. [總說明](#%E7%B8%BD%E8%AA%AA%E6%98%8E)
- [`main()`](#main-line-1--line-25)
- [`sort()`](#main-line-1--line-25)
- [`weight()`](#weightchar-c-line-79--line-85)
2. [[A] Bubble Sort](#A-Bubble-Sort)
- [Explanation](#Explanation)
- [Code](#Code)
3. [[B] Selection Sort]()
- [Explanation](#Explanation1)
- [Code](#Code1)
4. [[C] Insertion Sort]()
- [Explanation](#Explanation2)
- [Code](#Code2)

# 總說明
這週三題的解法相差無幾，差別僅在於演算法而已，因此會先在這裡一次說明他們的做法。
以下將以[[B] Selection Sort](https://hackmd.io/gvmuZuSMSlSeTEsvD5h2Lg#B-Selection-Sort)做範例說明。

### `main()` (line 1 ~ line 25)
1. 首先先建立一個字元陣列，其長度（在此為`SIZE` = 60）隨意，只要能存入所有輸入的字元即可。
2. 欲將使用者輸入的字串存入陣列中的方法有許多種，`scanf`（需一個一個字元慢慢讀取，無法一次讀取完整的含有空白的字串）, `gets`, `fgets`等等，因使用`gets`有時會有warning，因此在此我選則使用`fgets`。
`gets`及`fgets`有點類似，當未有任何字串被輸入，將會回傳NULL，所以若想讓程式執行直到輸入EOF，直接寫`while(gets(string))`即可。
- `gets(string)`
- `fgets(string, string_length, FILE)`
- 讀取鍵盤的輸入時，將FILE設為stdin

3. 為了符合題目所要求的輸出規則（每組不同input之間需有一行空白，而最後一次輸出後則無一行空白），需另外設立一個變數(在此為`printed`)來判斷此次input是否為第一次，若為第一次，則不需留空，若是，則輸出一行空白行。

4. 呼叫函式，排序及輸出等等的皆會在函式中進行。

5. 結束以上工作後，再進行下一輪前需要先將陣列初始化，避免上一次所輸入的字串較下一次的長，使得一些上次所存的字元仍留在字串中，被誤認為是新輸入的字串內容。
- 可使用`for` loop將字元陣列裡的每一格皆設定為一個非使用者會輸入的值(e.g. 空白， , ，& 等等)
- 在此使用動態陣列calloc
- calloc會將每格皆初始化為0
- [動態陣列說明](https://openhome.cc/Gossip/CGossip/MallocFree.html)

### `sort(char arr[])` (line 27 ~ line 77)
sort()可簡單為以下執行事項
1. 建立一個新字元陣列，其中只留下我們需要的字元
2. 輸出(`pass`)
3. 排序

說明：
1. 新字元陣列
- 此陣列的長度隨意，只要能夠儲存每一項即可
- 使用for loop，並判段`arr`（原陣列）裡的每個字元是否為所求，若是，則將它存入`new_arr`（新陣列）之中。
- 在將各個字元存入新陣列的同時，需同時紀錄新陣列所儲存的項目數，這將在之後的排序及輸出用到
- [A]題因為有負數的關係，因此新陣列的變數型態需設為`int`，才有辦法儲存負數，其餘字元將以ascii 表中所對應到的數值儲存。
- 註：B, C題中在字元陣列的尾端加上`\0`僅僅是為了方便測試，此行非必要
2. 輸出
- 此三題皆會用到兩層迴圈，而輸出的部分需放在外層迴圈內。
4. 排序
- 詳見各題

### `weight(char c)` (line 79 ~ line 85)
因為B, C題須依照題目所規定的大小優先順序排列，因此需另外使用一個陣列（在此為`w_arr` (line 8)）儲存它們所對應到的大小，並使用此函式以得到各個字元的數值。
此函式將會利用for loop在`w_arr`中尋找與parameter `c`相同的字元，若找到了，將會回傳字元在`w_arr`的index，其index即為它的大小、先後順序。

# [A] Bubble Sort
## Explanation
Bubble Sort動畫說明：https://www.youtube.com/watch?v=nmhjrI-aW5o
## Code

#include <stdio.h>
#include <stdlib.h>
#define SIZE 60

void bubble_sort(char arr[]);

int main(){
    char *input = calloc(SIZE, sizeof(char));
    int printed = 0;
    
    while(fgets(input, SIZE, stdin)){
        if(printed){
            puts("");
        }
        else{
            printed = 1;
        }

        bubble_sort(input);

        free(input);
        input = calloc(SIZE, sizeof(char));
    }
}

void bubble_sort(char arr[]){
    //create new array without spaces and other useless char
    int *new_arr = malloc(SIZE * sizeof(int));
    int len = 0;
    int negative = 0;

    int swapped;
    int tmp;
    for(int i=0; i<SIZE; i++){
        if(((arr[i] >= 'a') && (arr[i] <= 'z')) || ((arr[i] >= 'A') && (arr[i] <= 'Z'))){
            new_arr[len++] = arr[i];
        }
        else if((arr[i] >= '0') && (arr[i] <= '9')){
            new_arr[len++] = arr[i];
            if(negative){
                new_arr[len-1] *= (-1);
                negative = 0;
            }
        }
        else if(arr[i] == '-'){
            negative = 1;
        }
    }

    for(int i=0; i<len; i++){
        //print
        printf("Pass %d:", i);
        for(size_t idx=0; idx<len; idx++){
            if(new_arr[idx] < 0){
                printf(" -%c", new_arr[idx]*(-1));
            }
            else{
                printf(" %c", new_arr[idx]);
            }

            if(idx == (len-i-1)){
                printf(" /");
            }
        }
        puts("");

        //sort, swap
        swapped = 0;
        for(int j=1; j<len-i; j++){
            if(new_arr[j] < new_arr[j-1]){
                tmp = new_arr[j];
                new_arr[j] = new_arr[j-1];
                new_arr[j-1] = tmp;
                swapped = 1;
            }
        }

        if(!swapped){
            break;
        }
    }
}

# [B] Selection Sort
## Explanation
Selection Sort動畫說明：https://www.youtube.com/watch?v=xWBP4lzkoyM
## Code

#include <stdio.h>
#include <stdlib.h>
#define SIZE 60

void selection_sort(char arr[]);
size_t weight(char c);

char w_arr[22] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F'};

int main(){
    char *input = calloc(SIZE, sizeof(char));
    int printed = 0;

    while(fgets(input, SIZE, stdin)){
        if(printed){
            puts("");
        }
        else{
            printed = 1;
        }
        selection_sort(input);
        free(input);
        input = calloc(SIZE, sizeof(char));
    }
}

void selection_sort(char arr[]){
    //create new array without spaces and other useless char
    char *new_arr = malloc(SIZE * sizeof(char));
    int len = 0;
    for(int i=0; i<SIZE; i++){
        if(((arr[i] >= '0') && (arr[i] <= '9')) || ((arr[i] >= 'a') && (arr[i] <= 'f')) || ((arr[i] >= 'A') && (arr[i] <= 'F'))){
            new_arr[len++] = arr[i];
        }
    }
    new_arr[len] = '\0';

    size_t smallest_idx;
    size_t smallest_w, curr_w;
    char tmp;

    //sorting
    for(int pass=0; pass<len; pass++){
        //print
        printf("Pass %d:", pass);
        for(size_t i=0; i<len; i++){
            if(i == pass){
                printf(" /");
            }

            printf(" %c", new_arr[i]);
        }
        puts("");

        if(pass == len-1){
            break;
        }
        
        //find smallest
        smallest_idx = pass;
        smallest_w = weight(new_arr[smallest_idx]);
        for(size_t curr=pass+1; curr<len; curr++){
            curr_w = weight(new_arr[curr]);
            if(curr_w < smallest_w){
                smallest_idx = curr;
                smallest_w = curr_w;
            }
        }

        //swap
        tmp = new_arr[pass];
        new_arr[pass] = new_arr[smallest_idx];
        new_arr[smallest_idx] = tmp;
    }

    free(new_arr);
}

size_t weight(char c){
    for(int i=0; i<22; i++){
        if(c == w_arr[i]){
            return i;
        }
    }
}

# [C] Insertion Sort
## Explanation
Insertion Sort 動畫說明：https://www.youtube.com/watch?v=OGzPmgsI-pQ
## Code

#include <stdio.h>
#include <stdlib.h>
#define SIZE 60

void insertion_sort(char arr[]);
size_t weight(char c);

char w_arr[14] = {'2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A'};

int main(){
    char *input = calloc(SIZE, sizeof(char));
    int printed = 0;

    while(fgets(input, SIZE, stdin)){
        if(printed){
            puts("");
        }
        else{
            printed = 1;
        }
        insertion_sort(input);
        free(input);
        input = calloc(SIZE, sizeof(char));
    }
}

void insertion_sort(char arr[]){
    //create new array without spaces and other useless char
    char *new_arr = malloc(SIZE * sizeof(char));
    int len = 0;
    for(int i=0; i<SIZE; i++){
        if(((arr[i] >= '0') && (arr[i] <= '9')) || ((arr[i] >= 'a') && (arr[i] <= 'z')) || ((arr[i] >= 'A') && (arr[i] <= 'Z'))){
            new_arr[len++] = arr[i];
        }
    }
    new_arr[len] = '\0';

    size_t key_w;
    size_t k, ptr;
    char key;

    //sorting
    for(int pass=0; pass<len; pass++){
        //print
        printf("Pass %d:", pass);
        for(int i=0; i<len; i++){
            printf(" %c", new_arr[i]);
            if(i == pass){
                printf(" /");
            }
        }
        puts("");

        if(pass == len-1){
            break;
        }

        //swap
        k = pass+1;
        key = new_arr[k];
        key_w = weight(key);
        ptr = k;
        while((ptr >= 1) && (weight(new_arr[ptr-1]) > key_w)){
            new_arr[ptr] = new_arr[ptr-1];
            ptr--;
        }
        new_arr[ptr] = key;
    }

    free(new_arr);
}

size_t weight(char c){
    for(int i=0; i<14; i++){
        if(c == w_arr[i]){
            return i;
        }
    }
}

###### tags: `程設一quiz`