알고리즘 : 퀵 정렬 (Java)

퀵정렬

 

• 분할정복 알고리즘의 일종!
• 시간복잡도 : O(NlogN)
• 피벗을 정한 후, 피벗을 기준으로 피벗보다 작은 쪽과 큰 쪽으로 분할하며 정렬하는 방식
• 최악의 경우는 이미 배열이 정렬되어 있거나 역순으로 되어있을 경우, O(n^2)의 시간복잡도 발생 가능

 

 

 

 

정렬 방식

 

1. 피벗을 선택 (맨 앞, 가운데 ,맨 끝, 랜덤 등...)
   
   
2. 피벗을 기준으로 피벗보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 정렬
   
   
3. 정렬이 완료되면 또다른 피벗을 정해 같은 방법으로 정렬
   
   

 

 

 

 

 

 

	static void quickSort(int left, int right) {
		if (left < right) {
			int pivot = left;
			int L = left + 1;
			int R = right;

			while (L <= R) {
				// pivot보다 큰놈 찾을 떄까지
				while (L <= R && arr[pivot] >= arr[L]) {
					L++;
				}
				// pibot보다 작은놈 찾을 때까지
				while (arr[pivot] < arr[R]) {
					R--;
				}

				// L, R 자리 바꾸기
				if (L < R) {
					int tmp = arr[L];
					arr[L] = arr[R];
					arr[R] = tmp;
				}
			}
			// R과 자리 바꾸기
			int tmp = arr[R];
			arr[R] = arr[pivot];
			arr[pivot] = tmp;

			pivot = R;
			quickSort(left, pivot - 1);
			quickSort(pivot + 1, right);
		}
	}