4. 퀵 정렬

문제: input.txt 파일에 있는 10만 개의 데이터를 읽어서 퀵 정렬을 한 후, 정렬된 데이터를 output.txt에 저장해라.

 

퀵 정렬이란?

1. 피벗을 기준으로 모든 배열안의 큰 수를 오른쪽, 작은 수를 왼쪽에 정렬한다.

2. 그 후 마지막 작은 수(피벗기준)의 위치와 피벗의 위치를 바꿔준다.

3. 0~(바뀐 위치 - 1), (바뀐 위치 +1)~마지막으로 분할 후 다시 퀵정렬을 각각해준다.

 

i를 low+1이라 정의, j를 top이라 정의

여러 경우들

1. 1,2,3같이 이미 정렬이 되어 있는 경우

2. 2,1같이 i, j가 같은 곳에서 시작되는 경우

3. 1,2같이 i, j가 같은 곳에서 시작되고, 정렬이 되어있는 경우

 

->i가 top을 넘어갈 수 있으면, 해결된다.

#include<stdio.h>

void quickSort(int a[], int top, int low);
FILE* fileOpen(char type);


void main() {

	//file(r)=============================================
	FILE* fp1 = fileOpen('r');
	int array[100000];
	int i = 0;
	while (fscanf_s(fp1, "%d", &array[i]) == 1 && i < 100000) {
		i++;
	}
	fclose(fp1);
	//===================================================


	//정렬===============================================
	quickSort(array, 99999, 0);
	//===================================================
	

	//file(w)============================================
	FILE* fp2 = fileOpen('w');
	for (int j = 0; j < 100000; j++) {
		fprintf(fp2, "%d ", array[j]);
	}
	fclose(fp2);
	//===================================================
}


void quickSort(int a[], int top, int low) {
	if (top <= low) { //배열이 2개 이상 이어야함
		return;
 }
	int i = low + 1;
	int j = top;
	int pivot = a[low];
	int temp;

	//엇갈릴 시  피벗값과 바꾼 후 빠져나오는 반복문
	while (i <= j) {
		while (pivot > a[i] && i <= top) {
			i++;
		}
		while (pivot < a[j] && j > low) {
			j--;
		}
		//i가 j를 넘어선 순간 피벗값과 j를 바꿔준다.(
		if (i > j) {
			temp = a[low];
			a[low] = a[j];
			a[j] = temp;
		}
		else {
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	quickSort(a, j - 1, low);
	quickSort(a, top, j + 1);
}

FILE* fileOpen(char type) {
	FILE* fp = NULL;
	if (type == 'r') {
		fopen_s(&fp, "input.txt", "r");
	}
	else {
		fopen_s(&fp, "output.txt", "w");
	}
	return fp;
}

시간 복잡도

1. N번 탐색, 동시에 반으로 쪼개어 탐색 logN

2. 최악의 경우 N^2