---
title: 排序演算法簡明運動!
tags: Templates, Talk
description: View the slide with "Slide Mode".
---

# 排序演算法簡明運動!
**D1149682 資一乙 林允勝**
<!-- Put the link to this slide here so people can follow -->

---
## 用你挑選的四種排序演算法，來解答以下 LeetCode 題目，確保修改的程式碼，沒有錯誤。我使用的是這四種。
- [bubble sort](https://www.notion.so/ch-06-array-1709334d912f40bb82f03d9d0df106fb)
- [selection sort](https://www.notion.so/0e88f402e1824900a8a9fb0d0b9b6797)
- [insertion sort](https://www.notion.so/ch-06-array-1709334d912f40bb82f03d9d0df106fb)
- [quick sort](https://www.notion.so/ch-06-array-1709334d912f40bb82f03d9d0df106fb)

---
## 題目:
[sort an array](https://leetcode.com/problems/sort-an-array/)
---
### 四種sort方法submit後皆為TimeLimitExeed，但皆可以運行10到14筆的測資推測可能是因為測資太龐大的原因，導致部分因時間運行過久而TLE
* bubble sort-10筆
* selection sort-10筆
* insertion sort-10筆
* quick sort- 11~14筆
### 由以上結果可知節省記憶體方面:
### quick > bubble = selection = insertion
### 而其中bubble、selection、insertion所需使用的記憶體容量每次都相同，而quick所使用的記憶體容量每次都可能不同。

---
## attention:以下程式碼上方為含main function之程式，而下方註解處為進入leetcode測試之程式
### Bubble sort
原理是從第一筆資料開始，逐一比較相鄰兩筆資料，如果兩筆大小順序有誤則做交換，反之則不動，接者再進行下一筆資料比較，所有資料比較完第1回合後，可以確保最後一筆資料是正確的位置。

#include <stdio.h>
#include <stdlib.h>
//-----------------------------------------------
void bubblesortArray(int *nums, int numsSize) {
  int temp; // temp暫時存放函數。
  for (int i = 0; i <= numsSize - 1;i++) {
    for (int j = i+1; j <= numsSize-1; j++) {
      //如果前面一位較大，則交換。
      if (nums[i] > nums[j]) {
        temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
      }//完成小至大的排序
    }
  }
//---output----------------------------------------
  for (int i = 0; i <= numsSize-1; i++) {
      printf("%d ", nums[i]);
}
  printf("\n");
}
//===main==============================================
int main() {
  int case_num;
  int size;
  int nums[100000];
//-----------------------------------------------
  //scan所有的elements進array nums
    while(scanf("%d", &case_num)!=EOF){
    for (int i = 0; i <= case_num - 1; i++) {
      int index = 0;
      scanf("%d", &index);
      nums[i] = index;//scan index
    }
  bubblesortArray(nums, case_num);//call fuction
    }
}
/*
int* sortArray(int* nums, int numsSize, int* returnSize){
  int temp;//temp暫時存放函數
    for (int i =0; i<=numsSize-1;i++){
      for(int j=i+1;j<=numsSize-1;j++){
          //如果前面一位較大
          if(nums[i]>nums[j]){
              temp=nums[i];
              nums[i]=nums[j];
              nums[j]=temp;
          }
      }
  }
    *returnSize = numsSize;
    return returnSize, nums;
}
*/

### Runtime:3ms
---

### Selection sort
原理是反覆從未排序數列中找出最小值，將它與左邊的數做交換。可以有兩種方式排序，一為由大到小排序時，將最小值放到末端;若由小到大排序時，則將最小值放到前端。

#include<stdio.h>
#include<stdlib.h>
void selectionsortArray(int* nums, int numsSize){
    int i = 0;
    int j = 0;
    int k = 0;
    int temp = 0;//temp儲存最小的數值，並做線性搜尋
    for(i = 0; i < numsSize - 1; i++){
        j = i;
        for(k = i + 1; k < numsSize; k++ ){
            if(nums[k] < nums[j]) j = k;
        }
        if(j != i){
            temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }//找出最小值並放置到左邊的位置
    }
  //---output----------------------------------------
  for (int i = 0; i <= numsSize-1; i++) {
      printf("%d ", nums[i]);
}
  printf("\n");
}
//=======================================================
int main() {
  int case_num;
  int size;
  int nums[100000];
//-----------------------------------------------
  //scan所有的elements進array nums
    while(scanf("%d", &case_num)!=EOF){
    for (int i = 0; i <= case_num - 1; i++) {
      int index = 0;
      scanf("%d", &index);
      nums[i] = index;//scan index
    }
  selectionsortArray(nums, case_num);//call fuction
    }
}
/*int* sortArray(int* nums, int numsSize, int* returnSize){
    int i = 0;
    int j = 0;
    int k = 0;
    int temp = 0;
    for(i = 0; i < numsSize - 1; i++){
        j = i;
        for(k = i + 1; k < numsSize; k++ ){
            if(nums[k] < nums[j]) j = k;
        }
        if(j != i){
            temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
    }
    *returnSize = numsSize;
    return returnSize, nums;
}//sortArray
*/

### Runtime:6ms
---

### Insertion sort
逐一將原始資料加入已排序好資料中，並逐一與已排序好的資料作比較，找到對的位置插入。

#include<stdio.h>
#include<stdlib.h>
void insertionsortArray(int* nums, int numsSize){
    int i = 0;
    int j = 0;
    int insertVal = 0;//set insert vlaue
    for(j = 1; j <= numsSize - 1; j++){
        insertVal = nums[j];//將最左的數設為操作完成
        for(i = j - 1; i >= 0 && nums[i] > insertVal; i--){
            nums[i+1] = nums[i];
        }
        nums[i + 1] = insertVal;//做完一輪sort後下一個數也設為sort完成
    }

  //---output----------------------------------------
  for (int i = 0; i <= numsSize-1; i++) {
      printf("%d ", nums[i]);
}
  printf("\n");
}
//=======================================================
int main() {
  int case_num;
  int size;
  int nums[100000];
//-----------------------------------------------
  //scan所有的elements進array nums
    while(scanf("%d", &case_num)!=EOF){
    for (int i = 0; i <= case_num - 1; i++) {
      int index = 0;
      scanf("%d", &index);
      nums[i] = index;//scan index
    }
  insertionsortArray(nums, case_num);//call fuction
    }
}
/*int* sortArray(int* nums, int numsSize, int* returnSize){
    int i = 0;
    int j = 0;
    int insertVal = 0;
    for(j = 1; j <= numsSize - 1; j++){
        insertVal = nums[j];
        for(i = j - 1; i >= 0 && nums[i] > insertVal; i--){
            nums[i+1] = nums[i];
        }
        nums[i + 1] = insertVal;
    }
    *returnSize = numsSize;
    return returnSize, nums;
}//sortArray*/

### Runtime:4ms

---

### Quick sort
先找一個基準點，然後派兩個代理人分別從資料的兩邊開始往中間找，如果右邊找到一個值比基準點小，左邊找到一個值比基準點大，就讓他們互換。

#include<stdio.h>
#include<stdlib.h>
void quickSort(int * num, int start, int end);
void quicksortArray(int* nums, int numsSize){
    quickSort(nums, 0, numsSize - 1);
  //---output----------------------------------------
  for (int i = 0; i <= numsSize-1; i++) {
      printf("%d ", nums[i]);
}
  printf("\n");
}

void quickSort(int * num, int start, int end){
    if (start >= end)
        return;
    int temp = num[start]; //hold array第一個變數
    int i = start, k = end;//令i是開始的element k是結束的element
    while (i < k){         //當開始的element小於結束的element時
        for (k; num[k] >= temp && k > i; k--);//自切割處從最後sort到最前面
        num[i] = num[k];
        num[k] = temp;
        for (i; num[i] <= temp && i < k; i++);
        num[k] = num[i];
        num[i] = temp;
    }
    quickSort(num, start, i-1);
    quickSort(num, k+1, end);
}

//=======================================================
int main() {
  int case_num;
  int size;
  int nums[100000];
//-----------------------------------------------
  //scan所有的elements進array nums
    while(scanf("%d", &case_num)!=EOF){
    for (int i = 0; i <= case_num - 1; i++) {
      int index = 0;
      scanf("%d", &index);
      nums[i] = index;//scan index
    }
  quicksortArray(nums, case_num);//call fuction
    }
}
/*void quickSort(int * num, int start, int end);

int* sortArray(int* nums, int numsSize, int* returnSize){
    quickSort(nums, 0, numsSize - 1);
    *returnSize = numsSize;
    return nums;
}



void quickSort(int * num, int start, int end){
    if (start >= end)
        return;
    int temp = num[start];
    int i = start, k = end;
    while (i < k){
        for (k; num[k] >= temp && k > i; k--);
        num[i] = num[k];
        num[k] = temp;
        for (i; num[i] <= temp && i < k; i++);
        num[k] = num[i];
        num[i] = temp;
    }
    quickSort(num, start, i-1);
    quickSort(num, k+1, end);
}*/

### Runtime:4ms
---