[C-language] quick-sort (median, left,right)

단순 무식하게 하드 코딩 했습니다 . 알고리즘은 간단하게 짰는데, 이를 c언어로 푸는 과정이 어려웠었습니다. 

 

코드

 

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int findMedian(int list[], int left, int mid, int right) {
	int median = left;

	if (list[left] > list[mid] && list[mid] < list[right]) {
		median = mid;
	}
	else if (list[mid] > list[right] && list[right] < list[left]) {
		median = right;
	}
	else if (list[mid] > list[left] && list[left] < list[right]) {
		median = left;
	}

	return median;
}

void swap(int list[], int from, int to) {
	int dummy = list[to];
	list[to] = list[from];
	list[from] = dummy;
}

int partition(int list[], int left, int right, char mode) {
	int row = left;
	int high = right;
	int mid =  left + (right - left) / 2;
	int pivot;
	if (mode == 'm') {

		pivot = findMedian(list, left, mid, right);
	}
	else if (mode == 'l') {
		pivot = left;
	}
	else {
		pivot = right;
	}
	int pivotValue = list[pivot];
	while (row < high) {
		if (pivot == left || pivot == right) {
			while (list[row] <= pivotValue && row < high)
				row++;
			while (list[high] >= pivotValue && high >= row)
				high--;
		}
		if (pivot ==  mid) {
			while (list[row] <= pivotValue && row <= high)
				row++;
			while (list[high] > pivotValue && high >= row)
				high--;
		}

		if (row >= high)
			break;
		swap(list, row, high);
	}
	if (pivot == left) {
		swap(list, pivot, high);
	}
	else if (pivot == right) {
		swap(list, pivot, high + 1);
	}

	return high;
}


void quickSort(int list[], int left, int right, char mode) {
	if (left < right) {
		int pivot = partition(list, left, right, mode);
		quickSort(list, left, pivot, mode);
		quickSort(list, pivot + 1, right, mode);
	}
}

void performQuickSort(int list[], char mode, int n) {
	int newArrM[120];
	
	for (int i = 0; i < n- 1; i++) {
		newArrM[i] = list[i];
	}
		

	quickSort(newArrM, 0, n -2 , mode);

	printf("\n");
	for (int i = 0; i < n -1; i++) {
		printf("%d", newArrM[i]);
		if (i + 1 < n) {
			printf(", ");
		}
	}
	printf(" : %c" , mode);

	system("pause");
	printf("\n");
}

int main() {
	int tmpNum;
	char tmpChar;
	int rowCount = 0;
	int lastColumnSize = 0;
	int numArr[120];
	int columnSize[99];
	FILE* fpInput = fopen("ex_input.txt", "r");
	if (!fpInput) {
		return printf("file does not exist.");
	}
	while (!feof(fpInput)) {
		fscanf(fpInput, "%d%c", &tmpNum, &tmpChar);
		numArr[lastColumnSize++] = tmpNum;
		if (tmpChar == '\n') {
			performQuickSort(numArr, 'l',lastColumnSize);
			performQuickSort(numArr, 'm',lastColumnSize);
			performQuickSort(numArr, 'r',lastColumnSize);
			lastColumnSize = 0;
		}
	}
	//by kmu's lee jong ho 
	performQuickSort(numArr, 'l', lastColumnSize);
	performQuickSort(numArr, 'm', lastColumnSize);
	performQuickSort(numArr, 'r', lastColumnSize);
	system("pause");
	
	return 0;
}