number.txt

• Please design a C language program for multiple sorting algorithms: • 1. First, design a main menu, the menu has 4 types of sorting options including: • - Bubble Sort • - Quick Sort • - Selection Sort • - Exit Program • 2. The data sequence to be sorted should be read from the file number.txt, and sorted in ascending order. • 3. For each sorting algorithm, please display the result of each ROUND in sequence, and also show how many rounds were needed to complete the sorting.

請以C語言設計一個多個排序的程式: • 1. 先設計一個主選單, 選單有4種排序的選項包含: • 氣泡排序法 • 快速排序法 • 選擇排序法 • 離開程式 • 2.欲排序的資料數列請至number.txt的檔案讀取, 以小到大的進行排序 • 3.每個排序法請將每個回合所執行的結果依序顯示, 並且顯示共計有幾次 rounds才完成排序.

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

int round = 0;
int ttnum = 13;

int partition(int array[], int low, int high);
int quicksort(int , int , int );
void swap(int *p,int *q)
{
	//p=&n1 so p store the address of n1, so *p store the value of n1
	//q=&n2 so q store the address of n2, so *q store the value of n2

    int tmp;
    tmp = *p; // tmp store the value of n1
    *p=*q;    // *p store the value of *q that is value of n2
    *q=tmp;   // *q store the value of tmp that is the value of n1
}

//void printArray(int array, int);

void printfArray(int array[]){
	printf("Round %d:",round);
	for(int i=0;i<ttnum;i++){
		printf("%d ",array[i]);
	}
}

void bubbleSort(int array[]){
	round++;
	for(int i=0; i<ttnum-1; i++){
		if(array[i]>array[i+1]){
			swap(&array[i],&array[i+1]);
		}
	}
}

int checkAns(int array[]){
	for(int i=0; i<ttnum-1; i++){
		if(array[i]>array[i+1]){
			return 1;
		}
	}
	return 0;
}

// Function for Selection sort
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
        if(checkAns(arr)==0){
    			return;
			}
        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
        if (min_idx != i)
            swap(&arr[min_idx], &arr[i]);
            round++;
            printfArray(arr);
    		printf("\\n");

    }
}

void quicksort(int array[], int low, int high){
	if (low < high) {
		int j = partition(array, low, high); // Perform the partitioning and get the pivot position
		quicksort(array, low, j - 1); // Recursively apply quicksort to the left subarray 
		quicksort(array, j + 1, high); // Recursively apply quickSort to the right subarray
		}
	}

int partition(int array[], int low, int high) {
	int pivot = array[low]; // step: Assume the pivot Kis the first key value.
	int i = low;
	int j = high + 1; // start from one position beyond the current segment

do {
    // Increment i while the element at index i is less than the pivot
    do {
        i++;
    } while (array[i] < pivot);

    // Decrement j while the element at index j is greater than the pivot
    do {
        j--;
    } while (array[j] > pivot);

    // Swap the elements at indices i and j if i is less than j
    if (i < j) {
    	printf("swapped %d and %d\\n",array[j], array[i]);
        swap(&array[i], &array[j]);
    }
} while (i < j);

	
	// Step : If i >= j then swap K with Kj. 
	printf("swapped %d and %d\\n",array[j], array[i]);

	swap(&array[low], & array[j]);
	
	// After a full pass, print the state of the entire array. 
	printf("After a full pass:");
	round++;
	printfArray(array);
	printf("\\n");
	return j; // Return the pivot's final position
}

int main(){
	//create array 
	int array[ttnum] = {0};
	
	//	FILE is a variable in stdio.h
    FILE *file; 
    file = fopen("number.txt", "r");
    
//  null in stdlib.h
    if (file == NULL) {
        printf("The file can't open\\n");
        return 1;
    }

    for (int i = 0; i < ttnum; i++) {
        fscanf(file, "%d", &array[i]);
    }
//    for (int i = 0; i < ttnum; i++) {
//        printf("%d\\n", array[i]);
//    }
//
	printfArray(array);
	printf("\\n");
    
//    main program start here
	int choice;
	while(1){
	
		printf("Menu:\\n1. Bubble Sort\\n2. QuickSort\\n3. Selection Sort\\n4. Exit Program\\n");
		scanf("%d",&choice);
		
		
		    switch(choice) {
	            case 1: 
	            	while(checkAns(array)==1){
	            		bubbleSort(array);
	            		printfArray(array);
	            		printf("\\n");
	            	printf("Total round:%d\\n",round);
					}
					break;
	            
	            case 2:
                while (checkAns(array) == 1) {
                    quicksort(array, 0, ttnum - 1);
                    printf("\\n");
                }
                printf("Total round:%d\\n", round);
                break;
	                break;
	            case 3:
	            	while(checkAns(array)==1){
	            		selectionSort(array, ttnum);
	            	printf("Total round:%d\\n",round);
					}
	                break;
	            case 4:
	                exit(0);
	                break;
	            default:
	                printf("Wrong Choice.\\n");
	                break;
	        }
	        
}
	return 0;

}