알고리즘 (정렬) - 고급 정렬 알고리즘(Quick Sort)2

고급 정렬 알고리즘

퀵 정렬(Quick Sort)

퀵 정렬은 평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰는 정렬 알고리즘이다. 우선 [그림 4-6]을 예로 들어 설명을 시작한다. 첫째 줄에 정렬해야 할 원소가 10개인 배열이 주어졌다. 아무원소나 기준 원소로 삼아도 상관이 없는데 여기서는 맨 오른ㅉ고에 있는 원소 15를 기준 원소로 삼는다.

 

그림 4-6 퀵 정렬의 작동 과정을 보여주는 예

 

(a)에서는 기준원소인 15를 중심으로 이보다 작은 원소들은 15의 왼쪽에, 나머지 원소들은 15의 오른쪽에 재배치한다. 이 결과 8,11,3은 왼쪽에, 31,48,20,29,65,73은 15의 오른쪽에 오도록 재배치되었다.

 

(b)에서 왼쪽의 원소 3개와 오른쪽의 원소 6개를 각각 독립적으로 정렬한다. 왼쪽3개의 원소를 정렬할 때 15의 자리는 영향을 받지 않는다. 오른쪽 6개의 원소를 정렬할 때도 역시 15의 자리 영향을 받지 않는다. 즉, 기준 원소 15는 왼쪽과 오른쪽의 정령을 시작하기 전에 이미 제자리를 찾은 것이다. 왼쪽과 오른쪽의 정렬이 끝나는 순간 전체 배열의 정렬이 끝난다. 왼쪽과 오른쪽의 정렬을 위해서는 다시 퀵 정렬을 사용하면 된다. 즉, 퀵 정렬을 재귀적으로 수행한다.

 

(a),(b)의 내용을 바탕으로 더 자세히 설명하자면, 우선 정렬할 배열에서 "기준원소"를 하나 고른다. 아무 원소나 임의로 골라도 되나 여기서는 맨 뒤의 원소를 기준 원소로 삼기로 한다. 이 기준 원소를 중심으로 더 갖거나 같은 수는 왼쪽으로, 튼 수는 오른쪽으로 재배치한다. 기준원소는 이렇게 분할된 양쪽 부분 배열 사이에 자리하게 된다. 이렇게 분할된 왼쪽 부분 배열을 따로 정렬한다. 마찬가지로 오른쪽 부분 배열도 따로 정렬한다. 기준원소는 손대지 말고 제가질에 그대로 누다. 기준원소의 왼쪽에 기준원소보다 작은 원소들이 정렬되어 있고, 오른쪽에 기준원소보다 큰 원소들이 정렬되어 있으면 전체 배열은 정려려된 것이다. 여기서 왼쪽과 오른쪽 부분 배열을 정렬할 때 퀵 정렬을 재귀적으로 사용한다.

 

알고리즘 4-5 퀵 정렬

public int [] quickSort(int [] a,int p, int r){
    QuickSort qs = new QuickSort(a);
    int [] A = qs.getA();
    int q = 0;

    if(p < r){
        q = qs.partition(qs,p,r);
        qs.quickSort(A,p,q-1);
        qs.quickSort(A,q+1,r);
    }

    return A;
}

public int  partition(QuickSort qs,int p, int r) {
    int [] A = qs.getA();
    int x = A[r];
    int i = p-1;        //i는 1구역의 끝지점
    // j은 3구역의 시작 지점
    for (int j = p; j <= r-1; j++) {
        if (A[j] <= x){
            i++;
            int temp = A[j];
            A[j] = A[i];
            A[i] = temp;
        }
    }
    //1구역의 끝지점 다음에 기준 원소를 옮긴다.(2구역)
    A[r] = A[i+1];
    A[i+1] = x;

    qs.setA(A);
   return  i+1;
}

 

 

quickSort()메서드

public int [] quickSort(int [] a,int p, int r){  // ▷a[p···r]을 정렬한다. 
    QuickSort qs = new QuickSort(a);
    int [] A = qs.getA();
    int q = 0;

    1️⃣if(p < r){
        2️⃣q = qs.partition(qs,p,r);  // ▷분할
        3️⃣qs.quickSort(A,p,q-1);	  // ▷왼쪽 부분 배열 정렬
        4️⃣qs.quickSort(A,q+1,r);	  // ▷오른쪽 부분 배열 정렬
    }

    return A;
}

 

1️⃣재귀적 호출시 시작 index와 마지막 index가 같다는것은 정렬대상의 원소가 하나 뿐이라는 것으로 더이상 정렬할 필요가 없기 때문에 재귀적 호출을 멈춘다. 다시 말해 마막 index가 시작의 index보다 커야 정렬의 대상이 된다.

기준원소를 중심으로 양쪽으로 나누고 나서(2️⃣) 퀵 정렬을 두번 재귀적으로 호출하고 있다.(3️⃣,4️⃣) 이전 게시물에서 다룬 병합정렬이 먼저 재귀적으로 작은 문제를 해겨한 다음 후처리를 하는데 반해, 퀵정렬은 선행 작업을 한 다음 재귀적으로 작은 문제를 해결하고 나서 종료된다. 

 

기준원소를 중심으로 분할하는 방법에는 여러가지가 있다. 특별히 비효율적이지 않은 한 양쪽으로 나누어지기만 한다면 위 코드에서 소개된 방식과 다른 방법을 사용하더라도 문제가 없다. 

 

partition()메서드 

partition(A[],p,r){
    // 배열A[p···r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
    // A[r]이 자리한 위치를 리턴한다.
}

• 1구역 : 15보다 작거나 같은 원소들
• 2구역 : 15보다 큰 원소들
• 3구역 : 아직 정해지지 않은 원소들 
• 4구역 : 기준원소 자기 자신

public int  partition(QuickSort qs,int p, int r) {
    int [] A = qs.getA();
    int x = A[r];		// ▷ 기준원소 
    int i = p-1;        // ▷ i는 1구역의 끝지점
    1️⃣for (int j = p; j <= r-1; j++) {  // ▷ j은 3구역의 시작 지점
        2️⃣if (A[j] <= x){
        // ▷ i값 증가후 A[i]<-> A[j]교환 
            3️⃣i++;
            int temp = A[j];
            A[j] = A[i];
            A[i] = temp;
        }
    }
    // ▷기준원소를 2구역으로 원소 교환
    4️⃣A[r] = A[i+1];
    A[i+1] = x;

   return  i+1;
}

 

우선 주어진 배열에 가장 오른쪽 값을 기준원소로 지정해 변수x에 넣어 준다.  그리고 1구역의 마지막 index를 나타 내는 i는 아직 판별전이므로 판별 대상이 될 index의 값보다 -1작다. 만약 시작 index가 1이라면 i는 -1된다. 

 

1️⃣ for문에서 에서 주어진 배열에 대한 판별을 시작한다.  for문은 판별 대상의 첫번째 부터 기준요소가 되는 마지막 요소를 제외하고 모든 원소를 살펴봐야 하므로 j는 시작인 index값을 가지고 j는 마지막 인덱스 값 직전까지만 증가한다.

 

2️⃣에서 3구역에 있는 제일 왼쪽에 있는 값과 x를 비교한다. 

 

3️⃣x값이 A[j]보다 클 경우 if문 안의 블록이 실행된다. 예를 들 j값이 0일 경우 A[0]에 해당하는 값은 1구역에 들어가야 하므로 일단 -1인 i값에 1을 더해 0을 만들어주고 A[i]에 값에 A[j]의 값을 서로 바꿔준다. if문 블록이 끝났으므로 j가 1증가해 1이 된다. A[1]의 값이 x보다 클때 A[1]의 값은 2구역에 들어가야 한다. 이때는 별다른 조치를 취하지 않고 for문을 통해 j값이 증가하게 하기만해도(아직 판별의 대상을 오른쪽으로 한칸 이동 시키는것)A[1]의 값과 해당 위가 자동으로 2구역이 된다. 2구역의 경우 1구역이 늘어나면 계속해서 인덱스가 이동된다. 따라서 2구역의 시작의 위치는 가변적이다. 모든 원소의 판변별이 끝난 후 1구역의 바로 다음 index i+1에는 기준원소의 index가 된다. 따라서 기준원소가 1구역과 2구역 사이로 이동하게되면 기준원소의 index다음 index가 비로소 2구역의 시작 index가 된다. 

 

4️⃣기준원소가 된 원소를 제외하고 배열에 있는 모든 원소를 1구역이나 2구역으로 보냈다면 for문이 종료된다. 이때 A[r]인 기준원소를 1구역의 마지막 원소의 뒤에 기준원소를 이동시키고 원해 해당 index의 자리 즉 i+1의 자리에 있었던 요소의 값은 배열의 맨 오른쪽으로 이동시킨다. 배열 A는 기준원소를 기준으로 해서 1구역 2구역으로 나누어지고 원래 i+1 자리에 있던 값은 어차피 같은 2구역에 위치하게 되므로 크게 신경쓰지 않는다. 또한 2구역은 quickSort은 재귀호출로 인해 다시 정렬되는 알고리즘을 거치게 된다. 

 

분할 알고리즘의 작동 원리를 예로 살펴보자. 배열의 맨 끝에 있는 15를 기준원소로 잡는다. 모표는 15보다 작거나 같은 원소는 15의 왼쪽에, 15보다 큰 원소는 15의 오른쪽에 오도록 원소들을 재배치하는 것이다. 알고리즘은 배열을 네 구역을 나누어 관리한다.

 

3구역에 있는 원소를 차례대로 하나씩 보면서 1구역 또는 2 구역에 포함시킨다. 변수 i는 1구역의 끝을 가리킨다.  변수 j는 3구역의 시작 부분을 가리킨다. 즉, 아직 1구역이나 2구역으로 가지 않은 변수중 가장 왼쪽에 있는 것을 가리킨다. 따라서 2구역은 1구역의 끝 원소 다음 부터 3 구역 시작 원소 전까지다. for 루프를 한 번 돌때 3구역의 있는 원소들을 기준 원소와 비교해서 1구역 혹은 2구역으로 보낸다. 그렇기 때문에 아직 판별하지 않은 원소를 나타내는 j는 하나씩 증가한다.

 

간단정리

• for루프가 한 바퀴 돌때마다 3구역이 한 칸씩 줄어든다.
• for루프가 한 바퀴 돌 때 마다 1구역 또는 2구역 중 하나가 한 칸 늘어난다.
• 2구역이 늘어날 때는 j만 1증가 한다. for루프가 한 바퀴 돌 때마다 j는 1 증가하므로 2구역을 늘리기위해서는 아무일도 할 필요가 없다.
• 1구역이 늘어날 때는 i와 j가 동시에 1증가한다.

 

 

 

 

[출처 - 쉽게 배우는 알고리즘(개정판),  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7707942187

IT CookBook, 쉽게 배우는 알고리즘(개정판)