4. 퀵 정렬

< 퀵 정렬 >

: 대표적인 '분할 정복' 알고리즘. 

: 평균 속도가 O ( N * logN ) 이다.

: 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다

( '왼/오'로 나눈다는 특징 때문에 굉장히 빠른 것 )

: 기준 값이 있다. = 피벗 ( pivot )

 

#include <stdio.h>

int number = 10;
int data[10] = {1, 10, 5, 8, 6, 4, 3, 2, 9};

// quickSort 함수
void quickSort(int *data, int start, int end) {
	if( start >= end) {     //원소가 1개인 경우
		return;
	}

	int key = start;    //키는 첫번째 원소
	int i = start + 1;  //왼쪽 출발 지점
	int j = end;        //오른쪽 출발 지점. 마지막 값.
	int temp;           //두가지 값의 위치를 바꿀 수 있도록 임시 변수 만들어줌

	while(i <= j) {    //엇갈릴 때까지 반복 
		while(data[i] <= data[key]) {  //키 값보다 큰 값을 만날때까지 오른쪽으로 이동
			i++;
		}

		while(data[j] >= data[key] && j > start) {  //키 값보다 작은 값을 만날때까지
			j--;
		}

		if(i > j) {  //현재 엇갈린 상태면 키 값과 교체
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		} else {   //엇갈리지 않은 상태면
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}

	quickSort(data, start, j - 1);  //왼쪽
	quickSort(data, j + 1, end);    //오른쪽
}

int main(void) {
	quickSort(data, 0, number - 1);
	for(int i = 0; i < number; i++) {
		printf("%d", data[i]);
	}
}
}

---

 

● 퀵 정렬 평균 시간 복잡도 : O ( N *  logN )

● 퀵 정렬 최악 시간 복잡도 : O ( N^2 )

 

▶ 최악 시간 복잡도인 경우 ) 1 2 3 4 5 6 7 8 9 10 이렇게 이미 정렬되어 있을 때

 

---

 

↓퀵 정렬 내림 차순

#include <stdio.h>

int number = 10;
int data[10] = {1, 10, 5, 8, 6, 4, 3, 2, 9};

// quickSort 함수
void quickSort(int *data, int start, int end) {
	if( start >= end) {     //원소가 1개인 경우
		return;
	}

	int key = start;    //키는 첫번째 원소
	int i = start + 1;  //왼쪽 출발 지점
	int j = end;        //오른쪽 출발 지점. 마지막 값.
	int temp;           //두가지 값의 위치를 바꿀 수 있도록 임시 변수 만들어줌

	while(i <= j) {    //엇갈릴 때까지 반복 
		while(data[i] >= data[key]) {  //바로 여기!!!!!!!!!!!부호만 바꿈
			i++;
		}

		while(data[j] <= data[key] && j > start) {  //바로 여기!!!!!!!!!!!부호만 바꿈
			j--;
		}

		if(i > j) {  //현재 엇갈린 상태면 키 값과 교체
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		} else {   //엇갈리지 않은 상태면
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}

	quickSort(data, start, j - 1);  //왼쪽
	quickSort(data, j + 1, end);    //오른쪽
}

int main(void) {
	quickSort(data, 0, number - 1);
	for(int i = 0; i < number; i++) {
		printf("%d", data[i]);
	}
}
}

 

 

 

[동빈나 유튜브 - 실전 알고리즘 강좌 강의 정리]