C언어 - Quick sort 구현

Pivot 선택을 위한 Partition

첫 번째 방법

---

int hoarePartition(int* a, int low, int high) {
		int p = a[low];
		int i = low;
		int j = high;
		while (i <= j) {
			while (i <= high && a[i] <= p) i++;
			while (j >= low && p < a[j]) j--;

			// 여기서 a[i]는 p 값보다 크고 a[j]는 p 값보다 작거나 같음을 알 수 있다.
			// 따라서 swap 두 개를 스왑한다.
			if (i < j) {
				int tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}

		// i와 j가 교차하면(i>j) i, j는 피봇을 기준으로 작은 값(j)과
		// 큰 값(i)들의 경계에 위치
        
        // low는 가장 왼쪽에 있으므로 피봇위치(low)에 있는 값과, j 위치에 있는 값 swap
        // j 위치에 있는 값은 피봇 보다 작은 값이므로
		int tmp = a[low];
		a[low] = a[j];  
		a[j] = tmp;

	return j; // 피봇이 j번째로 이동함
}


void quickSort(int* a, int low, int high) {
	if (low < high) {
		int pivot;
		pivot = hoarePartition(a, low, high);
		quickSort(a, low, pivot - 1);
		quickSort(a, pivot + 1, high);
	}
}

int main(){
	int n;
    int arr[10];
	scanf("%d", &n);
    
    for(int i=0;i<n;++i) scanf("%d",&arr[i]);
	quickSort(arr, 0, n-1); 
}

---

두 번째 방법

---

// 위 방법보다 조금 더 빠름
int lomutoPartition(int* a, int low, int high) {
	int p = a[high]; // high 위치가 pivot
	int i = low - 1;
	int j = low; // low!!

	for (; j < high; j++) {
		if (a[j] <= p) { // pivot보다 작은 값을 찾자
            // j번째 값이 pivot보다 작다면 i를 증가
			i++;

			if (i < j) { // i번째 값은 j번째 값보다 무조건 크다.
               // 따라서 swap
				int tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}
	}
    
	i++;
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;

	return i;
}

void quickSort(int* a, int low, int high) {
	if (low < high) {
		int pivot;
		pivot = lomutoPartition(a, low, high);
		quickSort(a, low, pivot - 1);
		quickSort(a, pivot + 1, high);
	}
}

int main(){
	int n;
    int arr[10];
	scanf("%d", &n);
    
    for(int i=0;i<n;++i) scanf("%d",&arr[i]);
	quickSort(arr, 0, n-1); 
}

 

 

파티셔닝 인라인화 

함수를 인라인화 하면 조금 더 빠르게 동작합니다.

---

// quicksort 인라인화 --> 시간복잡도 감소
int quickSort(int* a, int low, int high) {
	if (low < high) {
		int p = a[low];
		int i = low;
		int j = high;
		while (i <= j) {
			while (i <= high && a[i] <= p) i++;
			while (j >= low && p < a[j]) j--;

			if (i < j) {
				int tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}

		int tmp = a[low];
		a[low] = a[j];
		a[j] = tmp;

		quickSort(a, low, j - 1);
		quickSort(a, j + 1, high);
	}
}

---

[백준문제]

• 서로 다른 문자열의 개수 - 소스코드