Bubble Sort

原理

• 重複地走訪要排序的數列，一次比較兩個元素，如果順序錯誤就交換
  • 兩兩比較，若後者較大，則互換兩者的位置
  • 使用兩層for迴圈
  • 搭配swap

程式碼

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

int n; //n個數字作排列
int input[1001],output[1001]; // 存放輸入數字之陣列

int group[10][1001];
int group_index[10] = {0};

void swap(int*, int*);
void bubbleSort(int*, int, int);

int main(void) {
    
	int digit,length;
	
	while(scanf("%d", &n) != EOF) {
		for(int i = 0; i < n; i++) {
			scanf("%d", &input[i]);
		}
		
		//以個位數為標籤，進行分組
		for(int i = 0; i < n; i++) {
			digit = input[i] % 10; //取得個位數
			group[digit][group_index[digit]] = input[i];
			group_index[digit]++;
		}
		
		// 將個位數一樣的組別，進行排序
		// group 為二維陣列
		// 個位數為 0 ~ 9
		for(int i = 0; i < 10; i++) {
		    
		    //泡沫排序(陣列,起點,終點)
			bubbleSort(group[i], 0, group_index[i] - 1);
		}
		
		//將分組合併維output，並輸出
		int index = 0;
		for(int i = 0; i < 10; i++) {
			for(int j = 0; j < group_index[i]; j++) {
				output[index] = group[i][j];
				index++;
			}
			group_index[i] = 0;
		}
		
		//print num
		for(int i = 0; i < n; i++) {
			printf("%d ", output[i]);
		}
		printf("\\n");
	}
}

void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void bubbleSort(int arr[], int start, int end) {
	for(int i = end + 1; i > start + 1; i--) {
		for(int j = start; j < i - 1; j++) {
			if(arr[j] < arr[j + 1]) {
				swap(&arr[j], &arr[j + 1]);
			}
		}
	}
}