[Algorithm] 퀵정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법입니다.
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다.
• 병합정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다.
• 가장 기본적인 퀵정렬은 첫번째 데이터를 기준 데이터로 설정합니다.
• 자바의 Arrays.sort()도 quickSort를 사용합니다.

static void quickSort(int[] array, int start, int end) {
    //배열의 길이가 1인 경우는 종료
    if(start >= end) return;

    //pivot는 배열의 첫번째 원소
    int pivot = start;
    //left는 pivot을 제외한 첫번째 원소
    int left = start + 1;
    //right는 해당 배열의 마지막 원소
    int right  = end;

    //left indext와 right index가 교차되지 않은 경우에만 반복문을 진행
    while (left <= right) {
        //left index를 구하는 과정
        //end를 넘지 않는 범위에서 피벗보다 값이 작거나 같다면 다음 값을 찾습니다.
        while(left <= end && array[pivot] >= array[left]) left++;

        //right index를 구하는 과정
        //(pivot이 첫 index를 가지기 때문에 큰 경우)
        //start보다 작은 범위에서 피벗 값보다 크거나 같다면 다음 값을 찾습니다.
        while(right > start && array[right] >= array[pivot]) right--;

        if(left > right) {
            //left index와 right index가 교차된 경우
            //pivot과 pivot보다 작은 값을 구한 right의 위치를 바꿉니다.
            //다음 로직으로 넘어간다.
            int temp = array[pivot];
            array[pivot] = array[right];
            array[right] = temp;
        } else {
            //left index와 right index가 교차되지 않은 경우
            //left와 right의 값을 바꾼다.
            //다시 반복한다.
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }

    //pivot을 기준으로 왼쪽을 실행
    //pivot보다 작은 값을을 sort하는 로직
    quickSort(array, start, right - 1);
    //pivot을 기준으로 오른쪽을 실행
    //pivot보다 큰 값들을 sort하는 로직
    quickSort(array, right + 1, end);
}

 

---

참고자료

• 나동빈 - 이코테