# 排序演算法簡明運動
## bubble sort
氣泡排序。就是由左到右，相鄰兩兩比較，較大者往右挪，最後最大值會出現在陣列右端。遞迴處理尚未排序的 N-1 個數字。
### 範例

void bubble_sort(int array[], int N)
{
	for (int i=0; i<N-1; ++i)	
	    for (int j=0; j<N-i-1; ++j)
			if (array[j] > array[j+1])
				swap(array[j], array[j+1]);
}

### 原版

// D1123794_hw1_bubble.c
// Sorting an array's values into ascending order with bubble sort.
#include <stdio.h>

// function prototype
void printArray(int *array, int array_size);
void bubbleSort(int *array, int array_size);
void swap(int *number_A, int *number_B);

// function main begins program execution
int main(void)
{
    // initialize array
    int array[] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37};
    int array_size = sizeof(array) / sizeof(array[0]);

    puts("Data items in original order");

    // output original array
    printArray(array, array_size);

    // bubble sort
    bubbleSort(array, array_size);

    puts("\nData items in ascending order");

    // output sorted array
    printArray(array, array_size);

    puts("");

    return 0;
}

// A utility function to print an array of size n
void printArray(int array[], int array_size)
{
    int index;
    for (index = 0; index < array_size; index++)
        printf("%d ", array[index]);
    printf("\n");
}

// sort the array
void bubbleSort(int *array, int array_size)
{
    // current_data 和 next_data 比大小，大的往後排，這樣每一輪就會有一個最大數被排到後面

    // example 532
    // first loop 352 -> 325
    // second loop 235

    // loop to control number of passes
    for (unsigned int pass = 1; pass < array_size; ++pass)
    {
        // loop to control number of comparisons per pass
        // 有 pass - 1 的人已經被被排到後面，且排序完成
        for (size_t index = 0; index < array_size - pass; ++index)
        {
            // compare adjacent elements and swap them if current
            // element is greater than next element
            int *current_data = &array[index];
            int *next_data = &array[index + 1];
            if (*current_data > *next_data)
            {
                swap(current_data, next_data);
            }
        }
    }
}

// Swap two numbers
void swap(int *number_A, int *number_B)
{
    int temp = *number_A;
    *number_A = *number_B;
    *number_B = temp;
}

### 更改後

// Fig. 6.15: fig06_15.c
// Sorting an array's values into ascending order.
#include <stdio.h>
#define SIZE 5

// function main begins program execution
int main(void) 
{   
   // initialize array
   int array[SIZE] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}; 

   puts("Data items in original order");
   
   // output original array
   for (size_t a_variable_number_which_will_plus_one_in_for_loop = 0; a_variable_number_which_will_plus_one_in_for_loop < SIZE; ++a_variable_number_which_will_plus_one_in_for_loop) {
      printf("%4d", array[a_variable_number_which_will_plus_one_in_for_loop]);
   } 

   // bubble sort                                         
   // loop to control number of passes                    
   for (unsigned int pass = 1; pass < SIZE; ++pass) {                   
      // loop to control number of comparisons per pass   
      for (size_t a_variable_number_which_will_plus_one_in_for_loop = 0; a_variable_number_which_will_plus_one_in_for_loop < SIZE-pass; ++a_variable_number_which_will_plus_one_in_for_loop) {                     
         // compare adjacent elements and swap them if first 
         // element is greater than second element         
         if (array[a_variable_number_which_will_plus_one_in_for_loop] > array[a_variable_number_which_will_plus_one_in_for_loop + 1]) {
            int temporary = array[a_variable_number_which_will_plus_one_in_for_loop];                                   
            array[a_variable_number_which_will_plus_one_in_for_loop] = array[a_variable_number_which_will_plus_one_in_for_loop + 1];                             
            array[a_variable_number_which_will_plus_one_in_for_loop + 1] = temporary;                               
         }                                       
      }                                   
   }                                      

   puts("\nData items in ascending order");

   // output sorted array
   for (size_t a_variable_number_which_will_plus_one_in_for_loop = 0; a_variable_number_which_will_plus_one_in_for_loop < SIZE; ++a_variable_number_which_will_plus_one_in_for_loop) {
      printf("%4d", array[a_variable_number_which_will_plus_one_in_for_loop]);
   } 

   puts("");
}

---

## selection sort
就是選擇排序。掃描一遍所有數字，找到最小值，挪至陣列左端。遞迴處理尚未排序的 N-1 個數字。
### 範例

void selection_sort(int array[], int N)
{
	for (int i=0; i<N; ++i)	// N改為N-1更精準
	{
		// 從尚未排序的數字當中，找出最小的數字。
		// （它也是全部數字當中第i小的數字。）
		int min_index = i;
		for (int j=i+1; j<N; ++j)
			if (array[j] < array[min_index])
				min_index = j;

		// 把第i小的數字，放在第i個位置。
		swap(array[i], array[min_index]);
	}
}

### 原版

* // C program for implementation of selection sort
#include <stdio.h>


void swap(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

void selectionSort(int arr[], int n)
{
	int i, j, min_idx;

	// One by one move boundary of unsorted subarray
	for (i = 0; i < n-1; i++)
	{
		// Find the minimum element in unsorted array
		min_idx = i;
		
		for (j = i+1; j < n; j++){
			if (arr[j] < arr[min_idx]){
					min_idx = j;
			}
		}
		// Swap the found minimum element with the first element
		swap(&arr[min_idx], &arr[i]);
	}
}

/* Function to print an array */
void printArray(int arr[], int size)
{
	int i;
	for (i=0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

// Driver program to test above functions
int main()
{
	int arr[] = {64, 25, 12, 22, 11};
	int n = sizeof(arr)/sizeof(arr[0]);
	selectionSort(arr, n);
	printf("Sorted array: \n");
	printArray(arr, n);
	return 0;
}

### 更改後

// C program for implementation of selection sort
#include <stdio.h>


void swap(int a_number_A_which_will_be_replaced_with_B, int a_number_B_which_will_be_replaced_with_A)
{
	int temp = a_number_A_which_will_be_replaced_with_B;
	a_number_A_which_will_be_replaced_with_B = a_number_B_which_will_be_replaced_with_A;
	a_number_B_which_will_be_replaced_with_A = temp;
}

void selectionSort(int array[], int n)
{
	int a_varable_number, compare_number, min_idx;

	// One by one move boundary of unsorted subarray
	for (a_varable_number = 0; a_varable_number < n-1; a_varable_number++)
	{
		// Find the minimum element in unsorted array
		min_idx = a_varable_number;
		
		for (compare_number = a_varable_number+1; compare_number < n; compare_number++){
			if (array[compare_number] < array[min_idx]){
					min_idx = compare_number;
			}
		}
		// Swap the found minimum element with the first element
		swap(&arr[min_idx], &arr[a_varable_number]);
	}
}

/* Function to print an array *

---
/
void printArray(int arr[], int size)
{
	int a_varable_number;
	for (a_varable_number=0; a_varable_number < size; a_varable_number++)
		printf("%d ", arr[a_varable_number]);
	printf("\n");
}

// Driver program to test above functions
int main()
{
	int array[] = {64, 25, 12, 22, 11};
	int n = sizeof(array)/sizeof(array[0]);
	selectionSort(array, n);
	printf("Sorted array: \n");
	printArray(array, n);
	return 0;
}

---

## insertion sort
插入排序。由左到右，逐一把數字插入到目前已排序的陣列當中。將大量數字往右挪，以騰出空間插入數字。
### 範例

void insertion_sort(int array[], int N)
{
	for (int i=1; i<N; ++i)
	{
		int pivot = array[i];

		int j;
		for (j=i; j>0; --j)
			if (pivot < array[j-1])
				array[j] = array[j-1];	// 往右挪
			else
				break;

		array[j] = pivot;		// 插入
	}
}

### 原版

// C program for insertion sort
#include <math.h>
#include <stdio.h>

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
	int i, key, j;
	for (i = 1; i < n; i++) {
		key = arr[i];
		j = i - 1;

		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j = j - 1;
		}
		arr[j + 1] = key;
	}
}

// A utility function to print an array of size n
void printArray(int arr[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

/* Driver program to test insertion sort */
int main()
{
	int arr[] = { 12, 11, 13, 5, 6 };
	int n = sizeof(arr) / sizeof(arr[0]);

	insertionSort(arr, n);
	printArray(arr, n);

	return 0;
}

### 更改後

// Fig. 6.15: fig06_15.c
// Sorting an array's values into ascending order.
#include <stdio.h>
#define SIZE 5

// function main begins program execution
int main(void) 
{   
   // initialize array
   int array[SIZE] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}; 

   puts("Data items in original order");
   
   // output original array
   for (size_t a_variable_number = 0; a_variable_number < SIZE; ++a_variable_number) {
      printf("%4d", array[a_variable_number]);
   } 

   // bubble sort                                         
   // loop to control number of passes                    
   for (unsigned int pass = 1; pass < SIZE; ++pass) {                   
      // loop to control number of comparisons per pass   
      for (size_t a_variable_number = 0; a_variable_number < SIZE-pass; ++a_variable_number) {                     
         // compare adjacent elements and swap them if first 
         // element is greater than second element         
         if (array[a_variable_number] > array[a_variable_number + 1]) {
            int hold = array[a_variable_number];                                   
            array[a_variable_number] = array[a_variable_number + 1];                             
            array[a_variable_number + 1] = temp;                               
         }                                       
      }                                   
   }                                      

   puts("\nData items in ascending order");

   // output sorted array
   for (size_t a_variable_number = 0; a_variable_number < SIZE; ++a_variable_number) {
      printf("%4d", array[a_variable_number]);
   } 

   puts("");
}

---

## merge sort
合併排序。 Divide-and-Conquer Method 。分兩半、分別排序、合併。
可參考Rosetta Code
[http://www.rosettacode.org/wiki/Sorting_algorithms/Merge_sort#C](https://)

### 原版

/* C program for Merge Sort */
#include <stdio.h>
#include <stdlib.h>

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
	int i, j, k;
	int n1 = m - l + 1;
	int n2 = r - m;

	/* create temp arrays */
	int L[n1], R[n2];

	/* Copy data to temp arrays L[] and R[] */
	for (i = 0; i < n1; i++)
		L[i] = arr[l + i];
	for (j = 0; j < n2; j++)
		R[j] = arr[m + 1 + j];

	/* Merge the temp arrays back into arr[l..r]*/
	i = 0; // Initial index of first subarray
	j = 0; // Initial index of second subarray
	k = l; // Initial index of merged subarray
	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}

	/* Copy the remaining elements of L[], if there
	are any */
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}

	/* Copy the remaining elements of R[], if there
	are any */
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
	if (l < r) {
		// Same as (l+r)/2, but avoids overflow for
		// large l and h
		int m = l + (r - l) / 2;

		// Sort first and second halves
		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, r);

		merge(arr, l, m, r);
	}
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", A[i]);
	printf("\n");
}

/* Driver code */
int main()
{
	int arr[] = { 12, 11, 13, 5, 6, 7 };
	int arr_size = sizeof(arr) / sizeof(arr[0]);

	printf("Given array is \n");
	printArray(arr, arr_size);

	mergeSort(arr, 0, arr_size - 1);

	printf("\nSorted array is \n");
	printArray(arr, arr_size);
	return 0;
}

### 更改後

#include <stdio.h>
#include <stdlib.h>

// Merges two subarrays of arr[].
// First subarray is array[l..m]
// Second subarray is array[m+1..r]
void merge(int array[], int first_index, int second_index, int third_index)
{
	int first_number, second_number, third_number;
	int n1 = second_index - first_index + 1;
	int n2 = third_index - second_index;

	/* create temp arrays */
	int array_one[n1], array_two[n2];

	/* Copy data to temp arrays array_one[] and R[] */
	for (first_number = 0; first_number < n1; first_number++)
		array_one[first_number] = array[first_index + first_number];
	for (second_number = 0; second_number < n2; second_number++)
		array_two[second_number] = array[third_number + 1 + second_number];

	/* Merge the temp arrays back into arr[l..r]*/
	first_number = 0; // Initial index of first subarray
	second_number = 0; // Initial index of second subarray
	third_number = array_one; // Initial index of merged subarray
	while (first_number < n1 && second_number < n2) {
		if (array_one[first_number] <= array_two[second_number]) {
			array[third_number] = array_one[first_number];
			first_number++;
		}
		else {
			array[third_number] = array_two[second_number];
			second_number++;
		}
		third_number++;
	}

	/* Copy the remaining elements of L[], if there
	are any */
	while (first_number < n1) {
		array[third_number] = array_one[first_number];
		first_number++;
		third_number++;
	}

	/* Copy the remaining elements of R[], if there
	are any */
	while (second_number < n2) {
		array[third_number] = array_two[second_number];
		second_number++;
		third_number++;
	}
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int array[], int first_index, int third_index)
{
	if (first_index < third_index) {
		// Same as (l+third_index)/2, but avoids overflow for
		// large l and h
		int second_index = first_index + (third_index - first_index) / 2;

		// Sort first and second halves
		mergeSort(array, first_index, second_index);
		mergeSort(array, second_index + 1, third_index);

		merge(array, first_index, second_index, third_index);
	}
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
	int first_number;
	for (first_number = 0; first_number < size; first_number++)
		printf("%d ", A[first_number]);
	printf("\n");
}

/* Driver code */
int main()
{
	int array[] = { 12, 11, 13, 5, 6, 7 };
	int arr_size = sizeof(array) / sizeof(array[0]);

	printf("Given array is \n");
	printArray(array, arr_size);

	mergeSort(array, 0, arr_size - 1);

	printf("\nSorted array is \n");
	printArray(array, arr_size);
	return 0;
}