針對亂序資料的常見排序演算法，包含Bubble sort、Selection sort、Insertion sort、Merge sort、Quick sort、BinaryTree track，而亂序資料的TXT是由此篇 產生多筆亂序的二進位及文字檔資料 所產生的，如果有興趣的夥伴可以參考此篇來做出許多亂序。由於筆者目前正在求職階段，因此無法將所有系列的文章逐一地以教學文的方式呈現引導讀者，日後會在將以前的文章重構以增加可讀性及教學性，若前輩們有什麼建議，歡迎於下方告知筆者。
完整程式碼:
/* arr1:Bubble sort *\
arr2:Selection sort
arr3:Insertion sort
arr4:Merge sort
arr5:Quick sort
\* arr6:BinaryTree track */
#include "pch.h"
#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#define MAX 16
int* load_add(int *, char*);//讀txt檔案
void show(int*, int); //顯示陣列
//***********Bubble sort ***********
void bubble_sort(int*, int);
//***********Selection sort***********
void select_sort(int*, int);
//***********Insertion sort***********
void insert_sort(int*, int);
//***********Merge sort***********
void merge(int *, int*, int*, int, int);
//***********Quick sort***********
void quick_sort(int*, int, int);
int Partition(int*, int, int);
//***********BinaryTree track***********
typedef struct node{
int value;
struct node *rightsub, *leftsub;
}Node;
void find(Node* , int);
void output(Node *);
void binarytree(int*, int);
Node *newnode(int);
//**********END***********
int main()
{
//***********1.宣告未排序好的陣列***********//
int *arr1 =NULL, *arr2 = NULL, *arr3 = NULL;//1,2,3
int inde_num = 1,i=0,j=0,cnt = 0;//通用變數
int *arr4 = (int*)calloc(200, sizeof(int));//Merge sort
int *arr5 = (int*)calloc(20, sizeof(int)); //Quick sort
int *arr6 = (int*)calloc(20, sizeof(int)); //BinaryTree track
char path1[] = "D:/檔案存放區/想變強嗎人類/那就來寫程式吧/binary資料產生/data_txt/total_value_100_1.txt";
char path2[] = "D:/檔案存放區/想變強嗎人類/那就來寫程式吧/binary資料產生/data_txt/total_value_100_2.txt";
char path3[] = "D:/檔案存放區/想變強嗎人類/那就來寫程式吧/binary資料產生/data_txt/total_value_100_3.txt";
char path4[] = "D:/檔案存放區/想變強嗎人類/那就來寫程式吧/binary資料產生/data_txt/total_value_100_4.txt";
arr1 = load_add(arr1, path1);//Bubble sort
arr2 = load_add(arr2, path2);//Selection sort
arr3 = load_add(arr3, path3);//Insertion sort
while(cnt <20){
for (j = 0; j < i; j++) {
if (arr5[j] == arr1[i])inde_num = 0;
}
if (inde_num) {
arr5[cnt] = arr1[i];//Quick sort
arr6[cnt] = arr1[i];//BinaryTree track
cnt++;
i++;
}
else {
inde_num = 1;
i++;
}
}
//***********2.前置準備***********//
int totalnum1=100,totalnum2 = 20,totalnum4 =200;//arr1~arr6內部資料數量
//***********Bubble sort ***********
bubble_sort(arr1,totalnum1);
printf("\nBubble sort:\n");
show(arr1, totalnum1);
//***********Selection sort ***********
select_sort(arr2, totalnum1);
printf("\nSelection sort:\n");
show(arr2, totalnum1);
//***********Insertion sort***********
insert_sort(arr3,totalnum1);
printf("\nInsert sort:\n");
show(arr3, totalnum1);
//***********Merge sort***********
merge(arr1, arr2, arr4, totalnum1, totalnum1);
printf("\nMerge sort(merge the arr1 and arr2):\n");
show(arr4, totalnum4);
//***********Quick sort***********
quick_sort(arr5, 0, totalnum2);
printf("\nQuick sort:\n");
show(arr5, totalnum2);
//***********BinaryTree Track***********
printf("\nBinaryTree Track:\n");
binarytree(arr6, totalnum2);
printf("\n\n");
return 0;
}
int* load_add(int *arr,char* path) {//以倍增算法來開動態陣列空間
int totalnum = 0, limit = MAX;
FILE *fp = fopen(path, "r");
if (fp == NULL) {
perror("Error printed by perror");
}
arr = (int*)calloc(MAX, sizeof(int));
while (fscanf(fp, "%d", &arr[totalnum]) != EOF) {
if (totalnum >= limit) {
limit *= 2;
int *arr_new = (int*)calloc(limit, sizeof(int));
for (int i = 0; i < totalnum; i++) {
arr_new[i] = arr[i];
}
free(arr);
arr = arr_new;
}
totalnum++;
}
return arr;
}
//***********Bubble sort ***********
void bubble_sort(int*arr, int totalnum) {
int i = 0, j = 0, temp = 0;
bool isend = true;
for (; i < totalnum; i++) {
isend = true;
for (j=0; j < totalnum - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
isend = false;
}
}
if (isend)break;
}
}
void show(int*arr, int totalnum) {
for (int i = 0; i < totalnum; i++) {
printf("%d ", arr[i]);
if((i+1)%25==0)printf("\n");
}
printf("\n");
}
//***********Selection sort***********
void select_sort(int* arr, int totalnum) {
int index = 0, temp = 0, i = 0, j = 0;
for (; i < totalnum; i++) {
temp = arr[i];
index = i;
for (j = i; j < totalnum; j++) {
if (temp > arr[j]) {
index = j;
temp = arr[j];
}
}
if (index != i) {
arr[index] = arr[i];
arr[i] = temp;
}
}
}
//***********Insertion sort***********
void insert_sort(int *arr, int totalnum) {
int index = 0, i = 1, temp = 0;
for (; i < totalnum; i++) {
temp = arr[i];
index = i;
while (index > 0 && arr[index - 1] > temp) {
arr[index] = arr[index-1];
arr[index - 1] = temp;
index--;
if (index == 0)break;
}
}
}
//***********Merge sort***********
void merge(int *arr1, int*arr2, int*arrsum, int totalnum1, int totalnum2) {
int index1 = 0, index2 = 0, sumnum = totalnum1 + totalnum2, index3 = 0;
while (sumnum > index3) {
if (index1 >= totalnum1) {
if (index2 >= totalnum2 )break;
arrsum[index3++] = arr2[index2++];
}
else if (index2 >= totalnum2 ) {
if (index1 >= totalnum1 )break;
arrsum[index3++] = arr1[index1++];
}
else {
if (arr1[index1] < arr2[index2]) {
arrsum[index3++] = arr1[index1++];
}
else if(arr1[index1] > arr2[index2]) {
arrsum[index3++] = arr2[index2++];
}
else {
arrsum[index3++] = arr1[index1++];
arrsum[index3++] = arr2[index2++];
}
}
}
}
//***********Quick sort***********
void quick_sort(int* arr, int left, int right) {
int q;
if (left < right) {
q = Partition(arr, left, right);
quick_sort(arr,left,q-1);
quick_sort(arr, q + 1, right);
}
}
int Partition(int* arr, int left, int right){
int i = 0, j = 0, temp = 0, mid = 0;
mid = arr[right];//中間值
i = left - 1;
j = left;
for (; j < right; j++) {
if (mid >= arr[j]) {
i++;
if (j != i) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i+1;
}
//***********BinaryTree track***********
Node *newnode(int target) {
Node *node = (Node*)malloc(sizeof(Node));
node->value = target;
node->leftsub = NULL;
node->rightsub = NULL;
return node;
}
void find(Node* node, int target) {
int leftnull = 0, rightnull = 0;
if (node->rightsub == NULL)rightnull = 1;
if (node->leftsub == NULL)leftnull = 1;
if (target > node->value) {
if (rightnull)node->rightsub = newnode(target);
else find(node->rightsub,target);
}
else if (target < node->value) {
if (leftnull)node->leftsub = newnode(target);
else find(node->leftsub,target);
}
else printf("ERROR:CANNOT ENTER TWO SAME VALUE IN THE ARRAY!\n");
}
void output(Node * node) {
if (node != NULL) {
output(node->leftsub);
printf("%d ",node->value);
output(node->rightsub);
}
}
void binarytree(int* arr, int totalnum) {
Node *root = newnode(arr[0]);
if (totalnum <= 0)printf("ERROR:THE ARRAY IS NULL!\n");
else if (root == NULL)printf("ERROE:MUST GIVE THE MEMORY TO ROOT!/ n");
else {
for (int index = 1; index < totalnum; index++) {
find(root, arr[index]);
}
}
output(root);
}
執行結果:
_______________________________________________
我們透過閱讀，拼湊出真實世界的面貌，
並在反覆的探索及思維中，打破由自我無知與偏見所建立的籓籬。