재귀함수를 이용한 퀵 정렬 구현

퀵정렬

피벗을 기준으로 더 큰값과 작은값 두개의 집합으로 분리하는 과정을 반복하여 하는 정렬, 시간복잡도는 nlog(n)

구현방법

1. 피벗을 선정

2. start와 end를 만들고, start값이 피벗보다 작으면 한칸이동 크면 멈춤, end값이 피벗보다 크면 한칸이동 작으면 멈춤

3. start값이 피벗보다 크고, end값이 피벗보다 작으면 두 데이터를 swap하고 각각 한칸씩 이동

4. 위 과정을 start와 end가 만날 때까지 반복

5. start와 end가 만나는 지점의 값과 피벗을 비교하여 피벗이 크면 피벗을 만나는 지점의 오른쪽, 작으면 왼쪽에 삽입

6. (5)까지의 과정이 끝나면 두개의 집합으로 나뉘고 각 집합에서 위와 동일한 과정을 반복한다.

구현시 어려웠던점

• 재귀함수의 구현

  재귀함수를 구현하기 위해서는 절대 함수의 실행 순서를 순차적으로
  생각하지 말고 아래의 접근법을 통해 해결한다.

1. 베이스조건 찾기 – 재귀 함수에서 바로 답을 구할 수 있는 가장 간단한 입력값을 찾는다. 더 이상 재귀를 호출하지 않고 바로 return 되는 경우,

• 퀵정렬에서의 베이스조건은 배열의 크기(혹은 인덱스 범위)가 0혹은1인 경우이다.

2. 분해하기 – 자기자신을 호출할때마다 베이스조건에 가까워 지도록 입력값을 조작한다.

• 퀵정렬에서는 피벗을 정하고, 피벗을 기준으로 정렬한 뒤 배열을 두집합으로 반복하여 나눈뒤, 
  	 피벗을 제외한 두집합의 인덱스를 입력값으로 넣는다.
  이러한 과정을 반복하면 마지막 재귀에서는 인덱스크기가 1이하인 함수가 실행된다.

  예시) 35214 입력시 : 35214 – 21 (3) 54 – (1) 2 (3) 4 (5)

3. 조합하기 – 부분 답을 가지고 전체답을 구하는 방법을 생각해본다, 베이스조건의 바로 윗 단계와 3단계위의 상황에서 그 아래 단계를 가지고 해당단계(바로 위,3단계위)를 만드는 규칙을 찾는다.

• 배열의 인덱스 초과

  반복문의 실행조건설정시 부등호를 잘못 설정하여 인덱스를 벗어나 이 문제를 해결하는데 많은 시간이 소요됐다. 이 경우에는 디버깅 기능을 사용하면 빠른 해결이 가능할 것 같다.

구현된 코드

public class Regression {
		public static void main(String[] args) throws Exception {
			BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st= new StringTokenizer(in.readLine());
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			
			int[] arr = new int[n];
			st = new StringTokenizer(in.readLine());
			for(int i=0; i<n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			quickSort(arr, 0, n-1);
			for(int i= 0; i <n; i++) {
				System.out.print(arr[i]+" ");
			}
		}


	public static void quickSort(int[] arr, int s, int e) {
		if(s<e) {
			if(s+1 == e) {
				if(arr[s] > arr[e]) {
					int tmp = arr[s];
					arr[s] = arr[e];
					arr[e] = tmp;
					return;
				}
			}
			int pivot = arr[s];
			int index1 = s+1;
			int index2 = e;
			while(index1<index2) {
				while(arr[index1]<pivot) {
					index1++;
				}
				while(arr[index2]>pivot) {
					index2--;
				}
				if(index1<index2) {
					int tmp = arr[index1];
					arr[index1] = arr[index2];
					arr[index2] = tmp;
					index1++; index2--;
				}
				
			}
			int tmp = arr[index1-1];
			arr[index1-1] = arr[s];
			arr[s] = tmp;
			
			quickSort(arr, s, index1-2);
			quickSort(arr, index1, e);
		}
	}
}