알고리즘 - 퀵정렬

✅퀵정렬에 대해서 알아보자.

퀵정렬은 분할정복(divde and conquer)알고리즘의 하나로, 평균적으로 가장 빠른 속도로 정렬을 수행한다.

✅수행단계

1. 배열에서 하나의 원소를 선택한다. 이를 피벗(pivot)이라고 한다.

2. 피벗을 기준으로 배열을 두 개의 부분 배열로 분할한다. 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽 배열에 위치시킨다.

3. 부분 배열을 재귀적으로 퀵정렬을 수행한다. 각 부분 배열은 다시 하나의 피벗을 선택하여 분할하는 과정을 거친다.

4. 재귀적인 분할 정복을 수행하다 보면, 최종적으로 크기가 1인 부분 배열이 만들어지게 된다.
   이 경우는 정렬할 필요가 없으므로 종료한다.

퀵 정렬은 평균적으로 시간복잡도가 O(n log n)이지만, 최악의 경우 O(n^2)의 시간 복잡도를 가질 수도 있다. 최악의 경우는 피벗을 선택하는 방법에 따라 달라진다. 따라서 퀵정렬의 성능을 개선하기 위해서는 피벗 선택 방법을 잘 선택해야 한다. 일반적으로는 중앙값을 선택하거나, 랜덤하게 선택하는 방법을 사용하여 최악의 경우가 발생할 확률을 줄인다.

✅코드

import java.io.*;

public class main{
	public static void Main(String[] args){
		BufferedReader br = new BufferedReader(System.in);
		BufferedWriter bw = new BufferedWriter(System.in);
	
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		for(i=0; i<n; i++){
			int[i] = Integer.parseInt(System.in);
		}
		
		quickSearch(arr, 0 , n-1);
		
		for(i=0; i<n ; i++){
			bw.write(arr[i] + "\n";
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static void quickSearch(int[] arr, int left, int right){
		int i = left;
		int j = right;
		
		int pivot = arr[(left + right)/2];
		
		while(i<= j ){
			while (i<= pivot) i++;
			while (j>= pivot) j--;
			
			if(i<=j){
				int temp = arr[i];
				arr [i] = arr[j];
				arr [j] = temp;
				i++;
				j--;
			}
		}
		quickSearch(arr, left, j);				//  왼쪽 부분 퀵정렬 수행
		quickSearch(arr, i , right);			// 오른쪽 부분 퀵정렬 수행
	}
}