알고리즘 - 퀵 정렬

퀵 정렬이란?

- 분할 정복 알고리즘의 하나로 평균적으로 빠른 수행 속도를 나타내는 정렬 방법이다

- 퀵 정렬은 리스트를 비균등 하게 분할하며, 피벗이란 임의로 고른 원소를 사용하여 정렬을 수행한다

- 피벗을 기준으로 작은 요소를 왼쪽으로, 큰 요소를 오른쪽으로 옮겨간다

- 피벗을 기분으로 분할된 요소들을 다시 정렬하기 위해 재귀 호출을 통해 정렬을 반복한다

- 리스트의 크기가 더 이상 분할할 수 없을 때까지 반복

먼저 PIVOT 계수를 정한다. PIVOT 계수는 임의로 선정한다

여기서는 첫 번째 요소를 PIVOT으로 결정

​

- PIVOT 값과 LEFT는 값을 비교하고 LEFT가 더 크면 RIGHT와 비교한다. 여기서 RIGHT 값이 PIVOT보다 작으면 LEFT와 RIGHT는 서로 SWAP 한다

​

-LEFT 값과 RIGHT 값이 만날 때까지 계속 반복하고 만나게 된다면, PIVOT 값을 해당 값과 비교한다.

- PIVOT 값이 크면 오른쪽 작으면 왼쪽에 배치한다.

예제를 한번 보자!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Test{
    
    public static void main(String[] args) {
    	try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			System.out.print("크기 입력 : "); int num = Integer.parseInt(br.readLine());
			int arr[] = new int[num];
			for(int i=0; i<arr.length; i++){
				arr[i] = Integer.parseInt(br.readLine());
			}
			Test quick = new Test();
			quick.sort(arr, 0, arr.length - 1);
			System.out.println(Arrays.toString(arr));
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
    }
    public void sort(int[] arr, int l, int r){
    	int leftValue = l;
    	int rightValue = r;
    	int pivot = arr[(l+r)/2];
    	do{
    		while(arr[leftValue] < pivot) {
    			leftValue++;
    		}
    		while(arr[rightValue] > pivot){
    			rightValue--;
    		}
    		if(leftValue <= rightValue){    
    			int temp = arr[leftValue];
    			arr[leftValue] = arr[rightValue];
    			arr[rightValue] = temp;
    			rightValue--;
    			leftValue++;
    		}
    	}while (leftValue <= rightValue);
    	
    	if(l < rightValue) sort(arr, l, rightValue);
    	if(r > leftValue) sort(arr, leftValue, r);
    }
}

정상적으로 출력이 된다!

​

이번엔 가운데를 PIVOT으로 설정해보자!

배열의 길이가 5이다. 5/2 = 2.5 즉 2번째 인덱스(6)가 PIVOT

- PIVOT과 LEFT를 비교하고 LEFT가 크면 RIGHT와 비교한다

- RIGHT가 PIVOT보다 크면 RIGHT를 왼쪽으로 이동 후 PIVOT과 비교

- RIGHT가 PIVOT보다 작으면 LEFT와 RIGHT 바꾸고 LEFT 오른쪽으로 이동

​

- LEFT와 RIGHT가 만날 때까지 반복한다

​

- LEFT와 RIGHT가 만나면 PIVOT을 비교해서 PIVOT이 작으면 왼쪽에, 크면 오른쪽에 둔다.

​

- 추후에 위 과정을 반복해서 정렬을 한다.

​

​