정렬 알고리즘 2 (셸 정렬, 퀵 정렬)

• 셸  정렬

 셸 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완하여 좀 더 빠르게 정렬하는 알고리즘이다. 단순 삽입 정렬의 장점은 정렬이 되었거나 또는 그 상태에 가까우면 정렬 속도가 아주 빠르다는 것이고, 단점은 삽입할 곳이 멀리 떨어지면 이동하는 횟수가 많다는 것이다. 따라서 단점을 줄이기 위해 셸 정렬에서는 순서대로 값들을 정렬시키는게 아니라 거리가 h만큼 떨어진 값들끼리 정렬시키고 정렬이 끝나면 그다음은 h/3 만큼 떨어진 값들끼리 정렬시킨다. 이렇게 떨어진 거리를 h라 할때 정렬을 반복할 때마다 h = h/3으로 정의해 h가 1이 될때까지 반복하여 정렬을 완성한다. 이때 처음 h의 값은 1에서 시작하여 3을 곱하고 1을 더해 만들 수 있는 수중 배열의 크기보다 작은 값들 중 가장 큰 값부터 시작한다. 예를 들면 다음과 같다.

 

a = { 8, 1, 4, 2,  7, 6, 3, 5 }를 셸정렬 하기

a의 크기가 8이므로 처음 h(거리)는 h의 후보군들 중 8보다 작은 값 중 가장 큰 값인 4로 정한다.

( h의 값은 1, 4, 13, 40 .. 이렇게 커진다. 이중에 배열의 크기보다 작은 값들 중 최댓값을 골라 사용한다.)

 

{ 8, 1, 4, 2,  7, 6, 3, 5 } 에서 h = 4를 적용해 0번째 index부터 진행

8과 h=4 만큼 떨어진 7을 정렬 >> { 7, 1, 4, 2,  8, 6, 3, 5 }

다음 수인 1과 h만큼 떨어진 6을 정렬 >> { 7, 1, 4, 2,  8, 6, 3, 5 }

다음 수인 4와 h만큼 떨어진 3을 정렬 >> { 7, 1, 3, 2,  8, 6, 4, 5 }

다음 수인 2와 h만큼 떨어진 5를 정렬 >> { 7, 1, 3, 2,  8, 6, 4, 5 }

 

한 사이클을 돌렸으니 h = h/3 = 1로 바꾸고 다시 진행

h = 1이니 삽입할 값의 index = i라 하고  단순 삽입 정렬 실행

i = 0    >>   { 7, 1, 3, 2, 8, 6, 4, 5 }

i = 1    >>   { 1, 7, 3, 2, 8, 6, 4, 5 }

i = 2    >>   { 1, 3, 7, 2, 8, 6, 4, 5 }

i = 3    >>   { 1, 2, 3, 7, 8, 6, 4, 5 }

i = 4    >>   { 1, 2, 3, 7, 8, 6, 4, 5 }

i = 5    >>   { 1, 2, 3, 6, 7, 8, 4, 5 }

i = 6    >>   { 1, 2, 3, 4, 6, 7, 8, 5 }

i = 7    >>   { 1, 2, 3, 4, 5, 6, 7, 8 }

 

따라서 a =  { 1, 2, 3, 4, 5, 6, 7, 8 } 이렇게 정렬이 완료된다.

 

 이렇게 셸 정렬을 이용하면 h를 변경해가면서 계속 정렬을 해야하기 때문에 정렬해야 하는 횟수는 증가하지만 전체적으로 요소의 이동 횟수가 줄어 효율적인 정렬 알고리즘이 된다. 그러면 이를 코드로 구현해 보자.

static void shell(int[] a, int n){
    int h=1;
    for(h=1; h<n; h=h*3+1);
    for(;h>0;h/=3){
        //// 단순 삽입 정렬 ////
        for(int i=h; i<n; i++){  // a[h] ~ a[n-1]까지 단순 삽입 정렬 진행
            int j;
            int temp = a[i]; // a[i] = 삽입할 요소
            for( j=i-h; j>=0&&a[j]>temp; j-=h){
                a[j+h] = a[j];  // a[j]>temp인 경우 a[j+h]값을 뒤로 미룸
            }
            a[j+h] = temp; // a[j]<=temp 이거나 j<0인경우(a[i]가 가장 작은 경우) a[j+h]에 temp 삽입
        }
        ///////////////////////
    }
}

 우선 첫번째 for문으로 가장 첫번째 h값을 찾는다.(n보다 작은 것들 중 최댓값). 그 h값으로 첫번째 단순 삽입 정렬을 진행한다. 그리고 첫번째 단순 삽입 정렬이 끝나면 h값을 바꾸는 for문을 통해 h=h/3이 되고, 그 h값으로 다시 단순 삽입 정렬을 진행한다. 단순 삽입 정렬 for문은 다음과 같이 진행된다. a[h] ~ a[n-1]까지 순서대로 단순 삽입 정렬을 시작하고, 안쪽의 for문을 통해 h거리 떨어진 값들을 비교하며 정렬을 한다. 이 내용은 h만큼 떨어진 값들끼리 비교한다는 것을 제외하면 단순 삽입 정렬과 비슷하기 때문에 설명은 생략하겠다. 셸 정렬의 시간 복잡도는 O(n^1.25)로 단순 정렬의 시간 복잡도인 O(n^2)에 비해 매우 빠르다. 그러나 이 알고리즘은 멀리 떨어져 있는 요소를 교환하므로 안정적이지 않은 알고리즘이다.  

 

• 퀵 정렬

  퀵 정렬은 일반적으로 폭넓게 사용되고 있는 아주 빠른 정렬 알고리즘이다. 퀵 정렬을 진행하려면 우선 그룹을 나누는 기준을 정해야하는데 이를 피벗(pivot)이라 한다. 피벗이 정해지면 피벗을 기준으로 왼쪽은 피벗보다 작은 값들의 그룹, 오른쪽은 피벗보다 큰 값들의 그룹으로 정렬한다. 그리고 이렇게 나눠진 2개의 그룹에서 각각의 피벗을 또 정해 피벗들을 기준으로 값을 나눈다. 이렇게 반복하다 보면 결국 모든 정렬이 끝나게 되고 이를 퀵 정렬 알고리즘이라 한다.

 

  그러면 피벗을 기준으로 두 그룹으로 나누는 방법에 대해 자세히 알아보자. 배열의 가장 왼쪽값의 index를 pl이라하고 가장 오른쪽의 index를 pr이라 하자. 그리고 피벗값을 x라고 하는데 이때 x = a[(pl+pr)/2]이다. 피벗을 설정했으니 이제 피벗값보다 작은 값은 피벗의 왼쪽으로, 큰 값은 오른쪽으로 옮겨보자. 우선 a[pl] >= x를 만족하는지 확인한다. 만족하지 않으면 pl++를 하고 다시 a[pl] >= x를 만족하는지 확인한다. 이렇게 조건을 만족하는 pl을 찾았으면 비슷한 방법으로 a[pr] <= x를 만족하는지 확인한다. 만족하지 않으면 pr--을 하고 다시 조건을 만족할때까지 반복한다. 이렇게 만족하는 pr과 pl값을 찾았으면 a[pl]값과 a[pr]값을 서로 교환한다. 그리고 pl이 pr보다 커질때까지 위 과정을 반복한다. 이 내용을 정리하면 다음과 같다.

1. a[pl] >= x를 만족하는 값을 찾을 때까지 pl++를 해준다.

2. a[pr] <= x를 만족하는 값을 찾을 때까지 pr--를 해준다.

3. pl > pr이면 반복을 종료한다.

4. 만약 pl > pr이 아니면 찾은 a[pl]과 a[pr]값을 교환해주고 1번으로 돌아가 다시 시작한다.

 

 위 반복에서 pl > pr 을 만족하여 끝나는 경우의 수가 2가지가 있다.

 

    1. pr = pl + 1인경우

  이 경우에는 2개의 그룹으로 나눠지는데 첫번째는 pr이하의 값들(a[0] ~ a[pr] : 피벗 이하)이 있고, 두번째는 pl이상의 값들(a[pl] ~ a[n-1] : 피벗 이상)이 있다. ex) [ a[0] ~~ a[pr] / a[pl] ~~ a[n-1] ]

 

    2. pr > pl + 1인 경우

  이 경우에는 3개의 그룹으로 나눠진다. 첫번째는 pr+1이하의 값들(a[0] ~ a[pr+1] : 피벗 이하)이 있고, 두번째는 pl-1이상의 값들(a[pl-1] ~ a[n-1] : 피벗 이상)의 값들이 있고, 마지막으로 pr+1 ~ pl-1의 값들이(a[pr+1] ~ a[pl-1] : 피벗과 같은 값을 갖는 그룹) 있다. ex) [ a[0] ~~ a[pr] / a[x] / a[pl] ~~ a[n-1] ]

 

  첫번째 사이클이 끝나면 왼쪽 그룹은 왼쪽 끝에서 pr까지의 범위에서, 오른쪽 그룹은 오른쪽 끝에서 pl까지의 범위에서 피벗을 정하고 정렬하는 과정을 반복한다. 그러면 재귀를 이용해 퀵 정렬을 한번 구현해 보자.

static void swap(int[] a, int x, int y){
    int t = a[x];
    a[x] = a[y];
    a[y] = t;
}
static void quick(int[] a, int left, int right) {
    int pl = left;
    int pr = right;
    int x = a[(pl + pr) / 2];

    while (pl<=pr) {          // pl>pr인 경우 반복문 탈출
        while (a[pl]<x) pl++;
        while (a[pr]>x) pr--;
        if(pl<=pr)            // pl <= pr :  swap 실행
        swap(a,pl++,pr--);
    }
    if(left < pr) quick(a,left,pr);   // left < pr  : 2개 이상 남아서 정렬이 필요한 경우
    if(pl < right) quick(a,pl,right); // pl < right : 2개 이상 남아서 정렬이 필요한 경우
}

  quick 메서드를 실행할 때마다 입력한 left와 right를 이용해 pl, pr, x를 설정하고  while문을 이용해 pl값, pr값을 찾는다. 그리고 pl <= pr이 성립하면 swap 메서드를 이용해 a[pl]과 a[pr]값을 바꿔주고 pl++, pr--를 해준다.(안해주면 무한 루프에 빠진다) 만약 pl>pr이어서 반복문을 빠져나오면 이제 두개로 나눠진 그룹을 다시 quick메서드에 넣어야한다. 이때 왼쪽 그룹은 left < pr을 만족할 때 quick 메서드에 넣고, 오른쪽 그룹은 pr < right일때 quick 메서드에 넣는다. 그 이유는 위 두 조건에 맞지 않으면 그룹의 요소가 1개 뿐이라 정렬을 할 필요가 없기 때문이다. 

 

 

 비재귀적인 퀵 정렬 구현

 

  위의 코드는 재귀를 이용한 퀵 정렬의 구현이었고, 비재귀적인 퀵 정렬도 구현이 가능하다. 스택을 2개 만들고 마지막 재귀 호출을 할 때 재귀 호출 대신 정렬 하고 싶은 그룹의 left값과 right값을 2개의 스택에 각각 넣으면 된다. 그리고 다시 올라가서 while문의 조건을 만족하면 pl, pr, x값을 스택에서 꺼낸 값을 이용해 초기화한다. 이렇게 스택을 이용하면 재귀를 사용하지 않아도 재귀를 이용한 퀵 정렬과 같은 결과를 얻을 수 있다.

static void swap(int[] a, int x, int y){
    int t = a[x];
    a[x] = a[y];
    a[y] = t;
}
static void quick(int[] a, int left, int right) {
    Stack<Integer> lst = new Stack<>();
    Stack<Integer> rst = new Stack<>();
    lst.push(left);
    rst.push(right);
    while(!lst.isEmpty()) {
        int pl = lst.pop();
        int pr = rst.pop();
        int x = a[(pl + pr) / 2];
        left = pl ; right = pr;
    /////// 재귀일 떄랑 같은 코드 //////
        while (pl <= pr) {
            while (a[pl] < x) pl++;
            while (a[pr] > x) pr--;
            if (pl <= pr)
                swap(a, pl++, pr--);}
    //////////////////////////////////
        if (left < pr){
            lst.push(left);
            rst.push(pr);
        }
        if (pl < right){
            lst.push(pl);
            rst.push(right);
        }
    }
}

 

    피벗 선택하기

 

 지금까지 피벗은 배열(그룹)의 가운데값으로 정하고 진행했다. 만약 가운데값으로 정한 피벗값이 배열에서 가장 큰 값이면 어떨까? 그러면 모든 값이 8보다 작으므로 8만 가장 오른쪽에 정렬이 될 뿐 나머지값들은 다시 정렬시켜야해서 퀵 정렬이란 이름이 무색하게 효율이 크게 떨어진다. 그래서 우리는 피벗을 선택하는 것도 규칙을 정해야 한다. 그래서 사람들이 생각해낸 방법이 바로 다음과 같다.

 

< 피벗 정하는 방법 >

1. 가장 왼쪽, 가운데, 오른쪽 값들을 정렬한다.

2. 가운데로 정렬된 값과 가장 오른쪽에서 두번째의 값을 교환한다.

3. 피벗값을 오른쪽에서 두번째의 값으로 정한다.

4. 가장 왼쪽에서 2번째 ~ 가장 오른쪽에서 3번째로 정렬 범위를 좁힌다. 

 

 예시를 통해 위 규칙을 익혀보자.

< 피벗 정하는 예시 >

배열 : a = { 8, 7, 6, 5, 4, 3, 2, 1, 0 }

 

1. 가장 왼쪽, 가운데, 오른쪽 값인 8, 4, 0을 정렬한다. >>  a = { 0, 7, 6, 5, 4, 3, 2, 1, 8 }

2. 가운데로 정렬된 값 4와 가장 오른쪽에서 두번째의 값 1을 교환한다. >>  a = { 0, 7, 6, 5, 1, 3, 2, 4, 8 }

3. 피벗값을 오른쪽에서 두번째의 값인 4로 정한다. ( pivot = 4 ) >>  a = { 0, 7, 6, 5, 1, 3, 2, 4, 8 }

4. 가장 왼쪽에서 2번째 ~ 가장 오른쪽에서 3번째로 정렬 범위를 좁힌다. >>  a = { 0, 7, 6, 5, 1, 3, 2, 4, 8 }

 

  다음 예시를 통해 이렇게 피벗을 정하면 좋은 점을 알아보자. 우선 가장 왼쪽 값인 0과 가장 오른쪽에서 첫번째, 두번째 값인 4, 8은 이미 정렬된 상태이므로 정렬해야 하는 범위를 7, 6, 5, 1, 3, 2 로 줄일 수 있다. 그리고 <피벗 정하는 방법>의 1번에서 나온 대로 0, 4, 8 중에 피벗값을 골랐으므로 최악의 피벗값을 고르는 경우를 피할 수 있다. 정리해보면 이 방법은 피벗을 기준으로 나눈 2개의 그룹의 크기가 불균형해지는 것을 피할 수 있고, 정렬시 범위 요소를 3개 줄일 수 있는 장점이 있다. 따라서 정렬 속도가 더 빨라진다. 이를 코드로 확인해보자. 

static void swap(int[] a, int x, int y){
    int t = a[x];
    a[x] = a[y];
    a[y] = t;
}
static void fstsort(int[] a, int first, int center, int last){
    // 버블 정렬 사용
    if(a[last]<a[center]) swap(a, center, last);
    if(a[center]<a[first]) swap(a, first, center);
    if(a[last]<a[center]) swap(a, center, last);
}
static void quick(int[] a, int left, int right) {
    ///////// 피벗 정하는 방법 1 ~ 4번/////////
    fstsort(a,left,(left+right)/2,right); // 1번 
    swap(a,(left+right)/2,right-1); // 2번
    int x = a[right-1]; // 3번
    int pl = left+1;  // 4번
    int pr = right-2; // 4번
    ////////////////////////////////////////
    while (pl<=pr) {
        while (a[pl]<x) pl++;
        while (a[pr]>x) pr--;
        if(pl<=pr)
            swap(a,pl++,pr--);
    }
    if(left < pr) quick(a,left,pr);
    if(pl < right) quick(a,pl,right);
}

  fstsort 메서드를 통해 버블 정렬(단순 교환 정렬)로 1번을 수행한다. swap으로 2번을 수행하고 3, 4번을 통해 피벗을 정하면 나머지 코드가 똑같아도 효율은 전에서 봤던 코드랑 다르게 훨씬 좋아진다. 

 퀵 정렬은 시간 복잡도가 O(n log n)이다 하지만 피벗을 잘못 선택하면 최악의 경우 O(n^2)까지 느려질 수 있으므로 피벗 선택하는 방법이 필요한 것을 알 수 있다.