정렬: 퀵 정렬 알고리즘

Algorithm : 퀵 정렬 알고리즘

: 어느 하나의 요소를 선택하고, 그 요소를 기준으로 요소보다 작은 그룹과 큰 그룹으로 나눕니다. 이 때 이 기준이 되는 요소를 피벗(pivot)이라고 합니다. 퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마칩니다.

 

1. 퀵 정렬의 과정

피벗 : x, 왼쪽 끝 요소 pl : 왼쪽 커서, 오른쪽 끝 요소 pr : 오른쪽 커서

• 배열을 두 그룹으로 나누기
  • array[pl] >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔
  • array[pr] <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔
  • 찾으면 pl과 pr이 가리키는 요소 array[pl]과 array[pr]의 값을 교환하고 다시 반복
    
  • 두 커서가 교차하게 되면 종료
• I 과정이 끝난 후에 배열은 피벗 이하의 그룹과 피벗 이상의 그룹으로 나뉩니다.
• 요소의 개수가 2개 이상인 그룹은 아래처럼 배열을 반복해서 나누고 요소의 개수가 1개인 그룹만 남을 때까지 다시 I의 과정을 반복합니다.
  
  • pr이 array[0]보다 오른쪽에 있으면(left < pr) 왼쪽 그룹을 나눕니다.
  • pl이 array[n-1]보다 왼쪽에 있으면(pl<right) 오른쪽 그룹을 나눕니다.

 

2. 퀵 정렬 알고리즘의 시간복잡도

: O(n log n). 그러나 매번 단 하나의 요소와 나머지 요소로 나누어지면 n번의 분할이 필요하기에 O(n²)

 

3. 퀵 정렬 알고리즘 코드

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

출처 : https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

Sort.java

package naram.algorithm_study;

import java.util.Scanner;

class QuickSort {
	
	static void swap(int[] array, int x, int y) {
		
		int temp = array[x];
		array[x] = array[y];
		array[y] = temp;
		
	}
	
	static void quickSort(int[] array, int left, int right) {
		int pl = left; // 왼쪽 커서
		int pr = right; // 오른쪽 커서
		int x = array[(pl + pr) / 2]; // 피벗
		
		do {
			while (array[pl] < x) pl++;
			while (array[pr] > x) pr--;
			
			if(pl <= pr) swap(array, pl++, pr--); // 왼쪽 커서와 오른쪽 커서의 값 교환
		} while(pl <= pr); // 배열 array를 피벗 x를 기준으로 나누기
		
		if (left < pr) quickSort(array, left, pr); // 재귀호출 
		if (pl < right) quickSort(array, pl, right); // 재취호출
	}
	
}

public class QuickSort_Algorithm {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		QuickSort Sort = new QuickSort();
		
		int n;
		
		Scanner stdIn = new Scanner(System.in);
		
		n = stdIn.nextInt(); // n 입력
		int[] sorting = new int[n];
		
		for(int i = 0; i < n; i++) {

			sorting[i] = stdIn.nextInt();
			
		} // n개의 수 입력
		
		Sort.quickSort(sorting, 0, n-1);
		
		for(int i = 0; i < n; i++) { 
			
			System.out.println(sorting[i]);
			
		}

	}

}