3. 빠른정렬(Quick Sort) - 1

이번 포스팅은 퀵소트입니다. 퀵소트는 이름에서는 그 특성을 따오기 힘드네요. 그저 빠른 정렬? 퀵소트라는 이름이 붙었을 정도면 그만큼 빠르겠죠? 그럼 퀵소트가 일단 어떻게 움직이는지 한번 볼까요?

출처 : wikipedia.org

이해가 되셨나요? 이걸 보고 이해하셨다면... 당신은 천재? 이해 못하신 경우에는 아래 설명을 보고 한번 다시 보시죠.

     1. 우선 pivot(중심점)이라는 것을 하나 정합니다. 이 pivot 을 정하는게 퀵소트의 성능을 좌우하는 중요한 것이기는 하지만 이게 퀵소트의 핵심 내용은 아니기 때문에 넘어갑니다. 위의 애니메이션을 자세히 보시면 pivot 은 전체 중에 가운데(비슷한?) 값을 정합니다.

     2. pivot 을 정했으면 전체를 두 부류로 나눕니다. 이 pivot 보다 작은지, 큰지를요. 그 두개의 그룹을 만듭니다.

     3. 전체를 봤으면 작은 그룹 + pivot + 큰 그룹으로 정렬합니다. 그럼 왼쪽은 항상 오른쪽보단 작아집니다.

     4. 이것을 또 반복합니다. 작은 그룹 내에서, 큰 그룹 내에서 반복적으로 진행합니다. 그러면 최종적으로는 왼쪽보단 오른쪽이 항상 커지게 되고, 이게 다 끝나면 전체적으로 정렬이 되는겁니다.

이를 바로 Java Code로 구현을 해보겠습니다. 언제나처럼 Test 코드 먼저 만들어줍니다.

private int[] original_array = {3, 5, 1, 4, 2, 8, 7, 6, 9, 0};
private int[] sorted_array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

private List<Integer> original_list = new ArrayList<>();
private List<Integer> sorted_list = new ArrayList<>();

@Before
public void setup() {
	for (int num : original_array) original_list.add(num);
	for (int num : sorted_array) sorted_list.add(num);
}

@Test
public void quickSortTest() {
	original_list = Sort.quickSort(original_list);
	assertThat(original_list, is(sorted_list));
}

     . 이전 정렬들과는 다르게 가변적으로 하기 위해 배열대신 List를 사용했습니다.

     . 나머지는 동일합니다. quickSort 실행 후, 정렬된 List와 비교합니다.

이 Test를 통과하기 위한 quickSort 메소드를 구현합니다.

public static List<Integer> quickSort(List<Integer> list) {
	if (list.size() < 2) {
		return list;
	}
	
	int pivot = list.get(0);
	
	List<Integer> lowerList = new ArrayList<>();
	List<Integer> higherList = new ArrayList<>();
	
	for (int i=1; i<list.size(); i++) {
		if (list.get(i) <= pivot) {
			lowerList.add(list.get(i));
		} else {
			higherList.add(list.get(i));
		}
	}
	
	lowerList = quickSort(lowerList);
	higherList = quickSort(higherList);
	
	List<Integer> sortedList = new ArrayList<>(lowerList);
	sortedList.add(pivot);
	sortedList.addAll(higherList);
	
	return sortedList;
}

출처 : JAVA 프로그래밍 면접 이렇게 준비한다. (노엘 마크업 지음, 정원천 옮김)

     . 위의 gif에서는 하나의 List 내에서만 정렬했지만 구현에서는 추가로 List를 생성했습니다.

     . pivot을 하나 정하고, 전체를 scan하면서 pivot보다 작은것은 lower에, 큰것은 higher에 모아뒀습니다.

     . lower와 higher 내에서 위의 작업을 반복합니다.

     . lower + pivot + higher를 return 하는 것으로 코드를 종료합니다.

여태 본 퀵소트 코드 중에서 가장 간단한 코드였습니다. 충분히 이해가 되셨을거라 생각하면서 포스팅을 마칩니다.

출처 : wikipedia.org