[Algorithm] 퀵 정렬(Quick Sort)이란?

📖 퀵 정렬(Quick Sort)이란?

퀵 정렬은 분할 정복 알고리즘을 사용하며 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법입니다.

 

 

🔎 퀵 정렬의 특징

• 시간 복잡도는 최선의 경우엔 O(nlogn), 최악의 경우엔 O(n²)
• 평균적으로 가장 빠른 정렬 알고리즘
• 정렬하고자 하는 배열 내에서 교환하는 방식이므로 별도의 메모리 공간을 필요로 하지 않음
• 불안정 정렬(Unstable Sort)
• 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행 시간이 더 걸림

 

 

🗝️ GIF로 보는 퀵 정렬 알고리즘

 

1. 배열 가운데서 하나의 원소를 고른다. (고른 원소를 피벗이라 함)
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗 기준으로 배열을 둘로 나눈다. (분할 정복)
3. 분할된 두 개의 배열에 대해 재귀적으로 1, 2번을 반복한다.

 

 

피벗은 p, 리스트 왼쪽 끝과 오른쪽 끝에서 시작한 인덱스들을 i, j라고 하자.

5 - 3 - 7 - 6 - 2 - 1 - 4 
                               p

리스트 왼쪽에 있는 i 위치의 값이 피벗 값보다 크고, 오른쪽에 있는 j 위치의 값은 피벗 값보다 작으므로 둘을 교환한다.

5 - 3 - 7 - 6 - 2 - 1 - 4 
i                         j    p 
1 - 3 - 7 - 6 - 2 - 5 - 4 
i                         j    p

j 위치의 값이 피벗 값보다 작지만, i 위치의 값도 피벗 값보다 작으므로 교환하지 않는다.

1 - 3 - 7 - 6 - 2 - 5 - 4 
      i              j         p

i위치를 피벗 값보다 큰 값이 나올 때까지 진행해 j 위치의 값과 교환한다.

1 - 3 - 7 - 6 - 2 - 5 - 4 
           i         j         p 
1 - 3 - 2 - 6 - 7 - 5 - 4 
           i         j         p

i위치가 j 위치보다 커지면, i 위치의 값과 피벗 값을 교환한다.

1 - 3 - 2 - 6 - 7 - 5 - 4 
                               p 
1 - 3 - 2 - 4 - 7 - 5 - 6 
               p

피벗 값 좌우의 리스트에 대해 각각 퀵 정렬을 재귀적으로 수행한다.

1 - 3 - 2       7 - 5 - 6
1 - 2 - 3       5 - 6 - 7

완성된 리스트는 다음과 같다.

1 - 2 - 3 - 4 - 5 - 6 - 7

 

 

 

👨🏻‍💻 JAVA로 구현

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int arr[] = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2 };

		System.out.println("정렬 전");
		for (int value : arr) {
			System.out.print(value + " ");
		}
		System.out.println();

		quickSort(arr, 0, arr.length-1);
		
		System.out.println("정렬 후");
		for (int value : arr) {
			System.out.print(value + " ");
		}

	}

	public static void quickSort(int[] array, int left, int right) {
		if (left >= right)
			return;

		// 분할
		int pivot = partition(array, left, right);

		// 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
		quickSort(array, left, pivot - 1); // 정복(Conquer)
		quickSort(array, pivot + 1, right); // 정복(Conquer)
	}
	
	public static int partition(int[] array, int left, int right) {
		
		int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
		int i = left, j = right;

		while (i < j) {
			while (pivot < array[j]) {
				j--;
			}
			while (i < j && pivot >= array[i]) {
				i++;
			}
			swap(array, i, j);
		}

		array[left] = array[i];
		array[i] = pivot;

		return i;
	}

	public static void swap(int[] array, int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

}

 

📚 참고

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC