나동빈 실전 알고리즘 5강 - 퀵정렬(Quick Sort)

<문제> 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요
1 10 5 8 7 6 4 3 2 9

---

퀵정렬은 대표적인 분할정복 알고리즘중에 하나이다.

분할정렬이란 하나의 특정한 값을 기준으로 양 쪽을 나눠서 정렬하는 것이다.

 

퀵정렬은 이런 특정한 값을 토대로 두 개의 작은 문제를 푸는 방식으로 해결해 나가는 것이다.

 

blog.naver.com/ndb796/221226813382

5. 퀵 정렬(Quick Sort)

자세한 설명은 나동빈 블로그에서 확인할수 있다.

 

package excercise;

public class algorithm {
	
	static void quickSort(int[] data, int start, int end) {
		if(start >= end) {
			return;
		}
		
		int key = start;
		int i = start + 1; // 왼쪽부터 오른쪽으로 하나씩 큰 값을 찾을 때 사용하는 인덱스 값
		int j = end; // 마지막부터 왼쪽으로 작은 값을 찾을 때 사용하는 인덱스 값
		int temp;
		
		while(i <= j) { // 엇갈리기 전까지 반복
			while(i <= end && data[i] <= data[key]) { // 키 값보다 큰 값을 만날때까지 이동
				i++;
			}
			while(data[j] >= data[key] && j > start) { // 키 값보다 작은 값을 만날때까지 이동
				j--;
			}
			
			if(i > j) { // 현재 엇갈린 상태면 키 값과 교체
				temp = data[j];
				data[j] = data[key];
				data[key] = temp;
			} else {
				temp = data[i];
				data[i] = data[j];
				data[j] = temp;
			}
		}
		
		quickSort(data, start, j - 1);
		quickSort(data, j + 1, end);
	}
	
	public static void main(String[] args) {
		int arr[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
		int number = 10;
		
		quickSort(arr, 0, number - 1);
		
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}	
}

 

그래서 코드를 작성하고 실행시켜보면 정상적으로 작동된다.

 

 

특정한 상황에서는 짧은 시간안에 정렬되는걸 볼 수 있지만 이미 거의 정렬된 배열에서는 효과를 발휘하지 못한다.