정렬 - 퀵 정렬

(보통 그럴 일은 없겠지만) 라이브러리를 전혀 사용할 수 없는 환경에 놓인다면 어떨까 생각을 하다가,

 

정렬에 대해 생각해보게 되었다.

 

예전엔 버블정렬을 구현해서 쓰다가, 라이브러리에서 주어지는 sort들이 비교할 수 없이 탁월하게 빠르기 때문에 통 안쓰다보니..

 

역시 정렬 알고리즘에는 여러가지가 있는데, 가장 원하는 측면이 속도이므로 퀵 정렬에 대해 알아봤다.

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬 - 위키백과, 우리 모두의 백과사전

(실제 알고리즘은 위 링크인 위키백과에 상세히 수록되어 있음. 아래는 개인 복습 정리용이라 그림 없이 누군가 보기는 어려움.)

 

 

배열에서 하나의 기준점(피벗)을 정하고,

(이 기준점은 어디든 상관없지만, 보통 양 끝 중 하나 혹은 중간을 택한다고 한다.)

 

(여기서는 오른쪽 끝으로 하겠음)

(왼쪽끝~오른쪽끝앞)/오른쪽끝 인 상태에서,

(왼쪽끝~오른쪽끝앞)을 처음과 끝으로 하여, i는 처음에서부터 오른쪽으로, j는 끝에서 왼쪽으로 탐색한다.

 

(오름차순 기준으로 설명. 즉, 큰 것이 오른쪽으로 가야할 때.)

i는 탐색하면서(i++) 기준점보다 크거나 같은 애를 찾다가 찾으면 그 위치에서 정지.

j는 탐색하면서(j--) 기준점보다 작거나 같은 애를 찾다가 찾으면 그 위치에서 정지.

 

i와 j의 수를 바꿔주면서 각각 한칸씩 전진(i++,j--)

 

 

i가 j를 넘으면(같은이 아님, 넘어가면) 전체 탐색 중지.

만약 위에서 그 위치에 서로 정지했어도 i가 j를 넘은상태라면 교환이 이루어지면 안됨.

 

이제 i와 기준점의 수를 교환하고,

기준점이 위치한 i를 기준으로

(왼쪽끝~i-1)/i/(i+1~오른쪽끝)으로 세 부분으로 나눌 수 있는데,

저 두 부분을 다시 재귀로 정렬함.

 

 

새로 호출한 부분에서도 기준점을 생성할텐데, 그 기준점은 항상 피벗되어 자리를 잡음.

그리고 이 자리 잡은 애는 제외되고 나머지 애들만 재귀를 반복함.

즉, 무수히 많은 재귀 중에도 하나씩은 자리를 잡으므로 결국 함수는 종료되긴 함.

 

 

public void sortAsc(int[] array, int start, int end) {
    int i = start;
    int j = end-1;
    while(i<=j) {    // i>j일 때 탐색 종료하고 피벗됨.
        if(array[i]<array[end] && i+1 <= end) i++;      // 오름차순 기준 왼편은 크거나같은 애만 오른쪽으로 보냄.
        if(array[j]>array[end] && j-1 >= start) j--;    // 오름차순 기준 오른편은 작거나같은 애만 왼쪽으로 보냄.
        if(i>j) break;
        if(i<j && array[i]>=array[end] && array[j]<=array[end]) {
            // 단순교환
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
            // 교환이 성사되면 i++/j--.
            if(i+1 <= end) i++;
            if(j-1 >= start) j--;
        }
        if(i==j && (i==end || j==start)) break;    // i와 j가 겹친상태에서, 어느 한 쪽의 끝이라도 쳐박혀서 움직일 수 없으면 빠져나온다.
    }
    // 단순교환
    int tmp = array[end];
    array[end] = array[i];
    array[i] = tmp;
    if((i-1)-start>0) sortAsc(array, start, i-1);
    if(end-(i+1)>0) sortAsc(array, i+1, end);
}

public void sortDesc(int[] array, int start, int end) {
    int i = start;
    int j = end-1;
    while(i<=j) {    // i>j일 때 탐색 종료하고 피벗됨.
        if(array[i]>array[end] && i+1 <= end) i++;      // 내림차순 기준 왼편은 작거나같은 애만 오른쪽으로 보냄.
        if(array[j]<array[end] && j-1 >= start) j--;    // 내림차순 기준 오른편은 크거나같은 애만 왼쪽으로 보냄.
        if(i>j) break;
        if(i<j && array[i]<=array[end] && array[j]>=array[end]) {
            // 단순교환
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
            // 교환이 성사되면 i++/j--.
            if(i+1 <= end) i++;
            if(j-1 >= start) j--;
        }
        if(i==j && (i==end || j==start)) break;    // i와 j가 겹친상태에서, 어느 한 쪽의 끝이라도 쳐박혀서 움직일 수 없으면 빠져나온다.
    }
    // 단순교환
    int tmp = array[end];
    array[end] = array[i];
    array[i] = tmp;
    if((i-1)-start>0) sortDesc(array, start, i-1);
    if(end-(i+1)>0) sortDesc(array, i+1, end);
}

 

재귀 대신 Stack을 통한 정렬

public void sortAsc(int[] array) {
    Stack<int[]> toDo = new Stack<>();
    toDo.push(new int[] {0,array.length-1});
    while(!toDo.isEmpty()) {
        int[] now = toDo.pop();
        int i = now[0];
        int j = now[1]-1;
        while(i<=j) {    // i>j일 때 탐색 종료하고 피벗됨.
            if(array[i]<array[now[1]] && i+1 <= now[1]) i++;    // 오름차순 기준 왼편은 크거나같은 애만 오른쪽으로 보냄.
            if(array[j]>array[now[1]] && j-1 >= now[0]) j--;    // 오름차순 기준 오른편은 작거나같은 애만 왼쪽으로 보냄.
            if(i>j) break;
            if(i<j && array[i]>=array[now[1]] && array[j]<=array[now[1]]) {
                // 단순교환
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
                // 교환이 성사되면 i++/j--.
                if(i+1 <= now[1]) i++;
                if(j-1 >= now[0]) j--;
            }
            if(i==j && (i==now[1] || j==now[0])) break;    // i와 j가 겹친상태에서, 어느 한 쪽의 끝이라도 쳐박혀서 움직일 수 없으면 빠져나온다.
        }
        // 단순교환
        int tmp = array[now[1]];
        array[now[1]] = array[i];
        array[i] = tmp;
        if(now[1]-(i+1)>0) toDo.push(new int[] {i+1,now[1]});
        if((i-1)-now[0]>0) toDo.push(new int[] {now[0],i-1});
    }
}

 

C++에서 재귀를 통한 std::vector<int>의 내림차순 정렬

(StackOverflow 되지 않을 여유가 있을 때의 Stack메모리를 사용하도록)

void SortDesc(std::vector<int>& v, std::vector<int>::iterator start, std::vector<int>::iterator end)
{
    std::vector<int>::iterator i = start;
    std::vector<int>::iterator j = end - 1;
    while (i <= j)
    {
        if (*i > *end && i + 1 <= end)
        {
            ++i;
        }
        if (*j < *end && j - 1 >= start)
        {
            --j;
        }
        if (i > j)
        {
            break;
        }
        if (*i <= *end && *j >= *end)
        {
            int temp = *i;
            *i = *j;
            *j = temp;
            if (i + 1 <= end)
            {
                ++i;
            }
            if (j - 1 >= start)
            {
                --j;
            }
        }
        if (i == j && (i == end || j == start))
        {
            break;
        }
    }
    int temp = *end;
    *end = *i;
    *i = temp;
    if (end > i + 1)
    {
        SortDesc(v, i + 1, end);
    }
    if (i - 1 > start)
    {
        SortDesc(v, start, i - 1);
    }
}

 

C++에서 std::stack을 통한 std::vector<int>의 내림차순 정렬

(최대한 Heap메모리를 사용하도록)

void SortDescending(std::vector<int>& v)
{
    std::stack<std::vector<int>::iterator*> toDo;
    toDo.push(new std::vector<int>::iterator[2] { v.begin(), v.end() - 1 });
    while (toDo.empty() == false)
    {
        std::vector<int>::iterator* tmp = toDo.top();
        toDo.pop();
        std::vector<int>::iterator i = *tmp;
        std::vector<int>::iterator j = *(tmp + 1) - 1;
        std::vector<int>::iterator k = *(tmp + 1);
        std::vector<int>::iterator l = *tmp;
        delete[] tmp;

        while (i <= j)
        {
            if (*i > * k && i + 1 <= k)
            {
                ++i;
            }
            if (*j < *k && j - 1 >= l)
            {
                --j;
            }
            if (i > j)
            {
                break;
            }
            if (i < j && *i <= *k && *j >= *k)
            {
                int temp = *i;
                *i = *j;
                *j = temp;
                if (i + 1 <= k)
                {
                    ++i;
                }
                if (j - 1 >= l)
                {
                    --j;
                }
            }
            if (i == j && (i == k || j == l))
            {
                break;
            }
        }
        int temp = *k;
        *k = *i;
        *i = temp;
        if (k > i + 1)
        {
            toDo.push(new std::vector<int>::iterator[2] { i + 1, k });
        }
        if (i - 1 > l)
        {
            toDo.push(new std::vector<int>::iterator[2] { l, i - 1 });
        }
    }
}