갑자기 순서대로 나가다가 이번에만 진도의 중반부인 QuickSort에 대하여
챌린지를 진행하게 되었다.
사유: 알고리즘 중간고사 시험이 와서...
약방의 감초인 퀵정렬답게 이곳저곳 안나오는 곳이 없다.
이번처럼 아예 시험에 나온다고 명시까지 해버리면, 진도를 바꾸더라도 안할 수가 없으니.
퀵정렬을 다시금 해보자.
일단, 강의에서도 나왔지만
퀵정렬은
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법이다.
이 부분에서 만약 알고리즘에 대해 잘 알고있다면 '분할 정복(Divide and Conquer)'을 떠올릴 것이다.
맞다. 퀵 정렬은 기본적으로 '분할 정복' 알고리즘을 기반으로 정렬되는 방식이다. 다만, 병합정렬(Merge Sort)과 다른 점은 병합정렬의 경우 하나의 리스트를 '절반'으로 나누어 분할 정복을 하고, 퀵 정렬(Quick Sort)의 경우 피벗(pivot)의 값에 따라 피벗보다 작은 값을 갖는 부분리스트와 피벗보다 큰 값을 갖는 부분리스트의 크기가 다를 수 있기 때문에 하나의 리스트에 대해 비균등하게 나뉜다는 점이 있다.
실제로도 정렬 방법에서 병합 정렬과 퀵 정렬은 많이 비교되곤 한다. (다만 일반적으로 병합정렬보다 퀵정렬이 빠르다.)
위 말만 들으면 잘 감이 안오실 것 같다.
구체적으로 알아보기에 앞서 미리 언급하자면 퀵 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 그러므로 '제자리 정렬(in-place sort)이다.'
퀵 정렬은 병합정렬과는 다르게 하나의 피벗을 두고 두 개의 부분리스트를 만들 때 서로 떨어진 원소끼리 교환이 일어나기 때문에 불안정정렬(Unstable Sort) 알고리즘이기도 하다.
위 말만 듣는다면 이해하기는 어려울 테니 정렬 방법에 대해 구체적으로 알아보도록 하자.
이번에 알고리즘 출석수업과제로 나온 문제 2번은 이거다.
//퀵정렬. 해줘. (Partition 함수가 1번 호출되었을 경우로.)
Integer A[] = {30,35,50,45,10,25,40};
//그리고 퀵정렬은 안정 정렬인지 제자리 정렬인지 설명해랏! - 제자리지만...30 35 40 25 10 45 50
이렇게 보니...
떠오르는 것은 파티션이 관건인 것 같다.(재귀를 돌리지 않고 한번만 호출이라고 하니깐.)
그래서 구글링해서 파티션 함수를 가져와 봤다.
/**
* pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메소드
*
* @param a 정렬 할 배열
* @param left 현재 배열의 가장 왼쪽 부분
* @param right 현재 배열의 가장 오른쪽 부분
* @return 최종적으로 위치한 피벗의 위치(hi)를 반환
*/
private static int partition(int[] a, int left, int right) {
// lo와 hi는 각각 배열의 끝에서 1 벗어난 위치부터 시작한다.
int lo = left - 1;
int hi = right + 1;
int pivot = a[(left + right) / 2]; // 부분리스트의 중간 요소를 피벗으로 설정
while(true) {
/*
* 1 증가시키고 난 뒤의 lo 위치의 요소가 pivot보다 큰 요소를
* 찾을 떄 까지 반복한다.
*/
do {
lo++;
} while(a[lo] < pivot);
/*
* 1 감소시키고 난 뒤의 hi 위치가 lo보다 크거나 같은 위치이면서
* hi위치의 요소가 pivot보다 작은 요소를 찾을 떄 까지 반복한다.
*/
do {
hi--;
} while(a[hi] > pivot && lo <= hi);
/*
* 만약 hi가 lo보다 크지 않다면(엇갈린다면) swap하지 않고 hi를 리턴한다.
*/
if(lo >= hi) {
return hi;
}
// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
swap(a, lo, hi);
}
}
파티션이 한번만 일어난다면...
내 쪽에서는 50,45,25,40 이 4개가 정렬되는 것으로
intellij 디버깅을 돌려보니 나오네.
자세한 것은 보충해서 이 블로그에 수정하면서 내용을 덧붙일 예정이다.
패스트캠퍼스 [직장인 실무교육]
프로그래밍, 영상편집, UX/UI, 마케팅, 데이터 분석, 엑셀강의, The RED, 국비지원, 기업교육, 서비스 제공.
fastcampus.co.kr
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.