sorting-algorithm.md

정렬

데이터를 오름차순 / 내림차순으로 나열 하는 것.

✔ 종류

• 정렬
  • ✔ 종류
  • ✔ 시간 복잡도 ( Big-O )
  • ✔ 공간 복잡도 ( Big-O )
  • 정렬의 특성
    • Selection Sort
    • Insertion Sort
    • Bubble Sort
    • Merge Sort
    • Quick Sort
    • Shell Sort
    • Heap Sort
    • Radix Sort
    • Counting Sort

✔ 시간 복잡도 ( Big-O )

알고리즘	최선	평균	최악
선택 정렬	Ω(n^2)	Θ(n^2)	O(n^2)
버블 정렬	Ω(n)	Θ(n^2)	O(n^2)
삽입 정렬	Ω(n)	Θ(n^2)	O(n^2)
트리 정렬	Ω(nlogn)	Θ(nlogn)	O(n^2)
퀵 정렬	Ω(nlogn)	Θ(nlogn)	O(n^2)
셸 정렬	Ω(n)	Θ(n^1.5)	O(n^1.5)
힙 정렬	Ω(nlogn)	Θ(nlogn)	O(nlogn)
합병 정렬	Ω(nlogn)	Θ(nlogn)	O(nlogn)
큐브 정렬	Ω(n)	Θ(nlogn)	O(nlogn)
팀 정렬	Ω(n)	Θ(nlogn)	O(nlogn)
기수 정렬	Ω(nk)	Θ(nk)	O(nk)
계수 정렬	Ω(n+k)	Θ(n+k)	O(n+k)

---

✔ 공간 복잡도 ( Big-O )

알고리즘	최악
선택 정렬	O(1)
버블 정렬	O(1)
삽입 정렬	O(1)
셸 정렬	O(1)
힙 정렬	O(1)
퀵 정렬	O(logn)
합병 정렬	O(n)
큐브 정렬	O(n)
트리 정렬	O(n)
팀 정렬	O(n)
계수 정렬	O(k)
기수 정렬	O(n+k)

---

정렬의 특성

• 안정 정렬 ( stable sort )

  • 정렬되지 않은 상태의 같은 키값을 가진 원소의 순서가 정렬 후에도 유지 되는 정렬

  • 상황에 따라서 객체나 키값이 여러개인 값들을 정렬 하려고 할때 원래의 순서가 바뀌게 되면 안될 수 있기 때문에 그때는 stable한 sort를 이용해야한다.

  • Bubble, Insertion, Merge, Counting, Bucket, Radix Sort가 해당된다.

예를 들어, 같은 5이더라도 a가 앞에 있는 5, b가 뒤에 있는 5라고 한다면

  3 5(a) 1 4 5(b) 2

  이 정렬 후에

  1 2 3 4 5(a) 5(b)

  와 같이 같은 키값의 원소의 순서가 유지 되는 것.

• 불안정 정렬 ( unstable sort )

  • 정렬되지 않은 상태의 같은 키값을 가진 원소의 순서가 정렬 후에 유지되는 것을 보장 할 수 없는 정렬

  • Selection, Shell, Heap, Quick Sort가 해당된다.

예를 들어, 같은 5이더라도 a가 앞에 있는 5, b가 뒤에 있는 5라고 한다면

  3 5(a) 1 4 5(b) 2

  이 정렬 후에

  1 2 3 4 5(b) 5(a)

  와 같이 같은 키값의 원소의 순서가 유지 되지 않는 것.

Selection Sort

• Unstable sort
• 추가 메모리 생성할 필요 X
• 배열 쭉 탐색 후 가장 작은 값 왼쪽부터 차곡차곡 쌓는 방식

    int min;
    /*배열을 순차 탐색하며 제일 최솟값을 왼쪽부터 정렬*/
    for(int i=0; i<arrlen-1;i++){
        min=i;
        for(int j=i+1;j<arrlen;j++){
            //최솟값이 들어있는 인덱스 search
            if(array[j]<array[min]) min=j;
        }
        swap( &array[i], &array[min] );  //가장 작은값을 왼쪽으로 이동

    }

Code 보기 (c++)

Insertion Sort

• Stable sort

• 추가 메모리 생성할 필요 X

• 인덱스값을 한개씩 늘려가며 해당 값이 맞는 위치에 삽입

• 상황에 따라 모두 비교하지 않으므로 best case 경우 O(n)으로 빠른 시간을 갖는다.

    for(int i=1;i<arrlen;i++){
        item=array[i];

        /*배열의 첫번째 가 아니고, 앞의 값보다 작다면 교체*/
        for(j=i-1;j>=0 && item < array[j] ;j--)
            array[j+1]=array[j];
        array[j+1]=item;
    }

Code 보기 (c++)

Bubble Sort

• Stable sort

• 추가 메모리 생성할 필요 X

• 배열을 모두 탐색하며 가장 큰 값을 오른쪽부터 쌓는다.

    /*한번 탐색할때마다 배열의 끝에 제일 큰 값이 채워지므로 배열의 길이-1만큼 반복문이 돈다*/
        for(int i=arrlen-1;i>0;i--){
            /*배열의 첫번째부터 다음 값과 비교해보면서 큰 값은 점점 뒤로 민다*/
            for(int j=0;j<i;j++)
                if(array[j]>array[j+1]) swap(&array[j],&array[j+1]);

Code 보기 (c++)

Merge Sort

• stable sort

• 분할과 정복 원리 ( Divide & Conquer )

• 더이상 나누어지지 않을 때까지 반으로 분할하다가 더이상 나누어지지 않은경우, 원소(value)를 결합(combine)할 때,양쪽의 value를 비교 후 정렬방식대로 combine을 실행한다.

• 재귀를 이용 ( recursion )

• 추가 메모리가 필요하다.

    /*merge (병합) 과정*/
    /*
     * 왼쪽 배열과 오른쪽 배열 비교하며 sorted배열 ( 추가 메모리 공간 )에 삽입
     *
     * 한쪽먼저 다 sorted에 삽입되었다면 남아 있는 다른쪽 배열 값 sorted 배열에 모두 삽입
     *
     * sorted의 배열 ( 정렬되어 있는 배열 )을 원래 배열에 복사
     */


    void Merge_sort(int array[],int left, int right){
        int mid;
        if(left<right){
            mid = (left+right) /2;
            Merge_sort(array,left,mid);     // 재귀
            Merge_sort(array,mid+1,right);  // 재귀
            Merge(array,left,mid,right);    // merge (병합)
        }
    }

Code 보기 (c++)

Quick Sort

• Unstable sort

• 분할과 정복 이용 ( Divide & Conquer )

• 분할시 기준 값 (pivot)을 설정 후 해당 pivot을 기준으로 좌, 우로 작은, 큰 값을 배치 시킨 후 pivot보다 작은 숫자들, 큰 숫자들의 집합을 다시 재귀 함수를 이용하여 분할 정렬을 하는 방식

• pivot은 기준점으로 중간값이기 때문에 재귀에 포함시키지 않는다.

• pivot을 계속 가장 작은 값 or 가장 큰 값을 설정시 worst case로 O(n^2)이 된다.

• 따라서 pivot을 어떻게 잡아서 partitioning할지가 중요하다.

• balanced partitioning : 좌우가 동일한 사이즈로 나누어지도록 pivot을 설정한 경우 => 가장 좋은 경우

/*pivot을 0 ( 시작 점 )으로 설정하였을 경우*/
void QuickSort(int array[],int pivot, int arrlen){
   int left = pivot+1, right = arrlen-1;

    if(pivot>=arrlen-1) return;

    /*right가 left와 같거나 더 작아질때까지*/
    while(left<=right){
        while(left <= arrlen-1 && array[left]<=array[pivot])left++;    //피벗보다 큰 값 왼쪽부터 찾기
        while(right > pivot && array[right]>=array[pivot])right--;   //피벗보다 작은 값 오른쪽부터 찾기
        if(left<right) swap(array[left],array[right]);  //left와 right가 교차하지 않았다면 두 값을 swap

        /*교차 했다면, pivot의 값과 right값을 swap ( 이때 right값은 pivot보다 작은 값을 가리키고 있기 때문이다.)*/
        else swap(array[pivot],array[right]);
   }
    QuickSort(array,pivot,right);   //pivot의 왼쪽 배열 정렬
    QuickSort(array,right+1,arrlen); //pivot의 오른쪽 배열 정렬
}

Code 보기 (c++)

Shell Sort

• Unstable sort

• 삽입정렬을 보완한 알고리즘 ( 어느정도 정렬된 배열에서 속도가 빠른 것에서 착안 )

• 삽입정렬은 삽입할 때, 이웃한 위치로만 이동이 가능하다는 단점이 있다. -> 이를 보완하여 셀 정렬은 멀리 떨어진 곳을 삽입정렬을 이용하여 정렬한다.

• 삽입정렬과 다르게 한 번에 정렬하지 않는다.

• 간격을 설정 하여 k번째 요소들을 추출하여 해당 숫자들을 삽입정렬로 정렬 후, k를 절반으로 줄여 1이 될 때까지 반복

• 간격(gap) : 초깃값 = 정렬할 값의 수/2
  생성된 부분 리스트의 개수는 gap과 같다.

    void shell_sort(int list[], int n){
        int i, gap;  // gap의 초기 값 : 정렬할 값의 수/2

        for(gap=n/2; gap>0; gap=gap/2){
            if((gap%2) == 0){
                gap++; // gap을 홀수로 만든다.
            }

            // 부분 리스트의 개수는 gap과 같다.
            for(i=0; i<gap; i++){
            // 부분 리스트에 대한 삽입 정렬 수행
            insertion_sort(list, i, n-1, gap);
            }
        }
    }

Code 보기 (c++)

Heap Sort

• Unstable sort

• Heap 자료구조 ( Complete Binary Tree 의 일종 )을 이용한 정렬 방법

• 배열을 heapify( heap으로 만들어 주는 것 ) 을 거쳐서 value를 꺼내는 방식의 정렬

• 추가 메모리 생성이 필요 없다.

• 오름차순 정렬을 위해 최대 힙을 구성하고, 내림차순 정렬을 위해 최소 힙을 구성.

• heapify를 작성할때 top-down 방식과 bottom-up방식으로 구현할 수 있으며 bottom-up이 살짝 더 성능이 좋다.

  • top-down : 아래에서 부터 위까지 올라가며 비교/교환하여 heapify를 수행
  • bottom-up : 위에서부터 아래로 내려가며 비교/교환하여 heapify를 수행
    • leaf node는 heapify를 수행하지 않아도 되기 때문에 leaf node의 부모 부터 heapify를 수행하기 때문에 build heap과정에서 top-down방식은 n번을 비교하지만 bottom-up방식은 2/n 번만 수행가능하다.

void top_down_HeapSort(int *array, int arrlen){
    //build heap
    top_down_heapify(array,arrlen);

    for(int i= arrlen-1 ; i>=0; i--){
        swap(array[i],array[0]);    //가장 큰 숫자(루트)를 맨 뒷 노드로 swap해준다.
        top_down_heapify(array,i);  //swap한 마지막 노드를 제외하고 heapify를 해준다.
    }                               //결과적으로 큰 숫자들이 뒤에 오게 되며 오름차순으로 정렬이 된다.
}

void bottom_up_HeapSort(int *array, int arrlen){
    //build heap
    for(int i= arrlen / 2 - 1; i >= 0; i--){
        bottom_up_heapify(array,i,arrlen);
    }

    for(int i = arrlen-1; i >= 0; i--){
        swap(array[i],array[0]);         //가장 큰 숫자(루트)를 맨 뒷 노드로 swap해준다.
        bottom_up_heapify(array,0,i);   //swap한 마지막 노드를 제외하고 heapify를 해준다.
    }                                   //결과적으로 큰 숫자들이 뒤에 오게 되며 오름차순으로 정렬이 된다.
}

Code 보기 (c++)

Radix Sort

• Stable sort

• Non-Comparisions Sorting Algorithm ( 비교하지 않는 정렬 알고리즘 )

• 기수 (Radix) : 데이터를 구성하는 기본요소

• 하나의 기수마다 버킷 (데이터 공간)을 생성하여 분류하여 버킷안에서 다시 정렬하는 방식

• 정렬 방식

  • LSD ( Least Significant Digit ) : 덜 중요한 기수부터 정렬
    예를들어서 일의 자리수자부터 정렬하는 방식이다. 따라서 중간에 정렬 결과를 확인할 수 없다.
  • MSD ( Most Significant Digit ) : 가장 중요한 기수부터 정렬
    예를들어서 백의 자리숫자부터 정렬하는 방식이다. 따라서 중간에 정렬 결과를 확인 할 수있으나 확인하는 과정에서 메모리를 더 사용하게 된다.

void RadixSort(int *array,int arrlen){
    int digit=1;
    int k;  //k는 radix(기수 = 각 자리수의 숫자)

    /*배열의 값 중 가장 큰 값의 자릿수 알아내기*/
    while(digit<MAXVALUE)
        digit*=10;

    /*가장 큰 값의 자릿수 만큼 만큼 반복*/
    for(int i=1; i<digit ; i*=10){
        /*queue(bucket)에 옮기기*/
        for(int j=0;j<arrlen;j++){
            k=(array[j]/i)%10;
            q[k].push(array[j]);  //q는 bucket
        }

        /*array에 옮기기*/
        int idx=0;
        for(int j=0;j<10;j++){
            while(!q[j].empty()){
                array[idx]=q[j].front();
                q[j].pop();
                idx++;
            }
        }
    }
}

Code 보기 (c++)

Counting Sort

• stable sort

• Non-Comparisions Sorting Algorithm( 비교하지 않는 정렬 알고리즘 )

• 좁은 범위의 데이터를 정렬할 때 유용 ( ex. Score )

• 법위가 넓어지게 되면 추가 메모리 공간이 많이 필요해지기 때문에 비효율

• 위와 같은 이유로 Radix Sort와 같이 사용할 경우 메모리를 아낄 수 있다.

• 정렬을 위해 추가 배열을 생성하는데 사이즈를 정렬할 배열의 가장 큰 값만큼 생성해 준다.

• 과정

  • 정렬할 배열 A, 추가 배열 C를 생성해준다.
  • 배열 C는 모든 값을 0으로 초기화해준다.
  • 배열 A의 값을 토대로 배열 C의 인덱스값을 참조하여 값을 1씩올려준다. (예를 들어 배열 A의 값중 3이 있다고 한다면, C의 3번째 인덱스 값을 1더해준다.)
  • 배열 c의 각 값들을 직전 값을 더해 업데이트 해준다.
    (예를 들어, 배열 C가 1,0,2,2 였다면, 1,1,3,5로 업데이트 해준다.)
  • 배열 C는 배열 A의 값들의 인덱스 값이므로, 배열 A를 끝에서부터 역순으로 훑으면서 배열 B에 정렬해 준다. (이때, 한 값을 B에 옮겨주었다면, 해당하는 인덱스의 배열 C의 값은 1을 빼준다.)

    int *c = new int[maxValue+1];   //0도 포함한 숫자를 정렬 할 경우 maxValue + 1만큼 생성해주어야 한다.

/*각 숫자 횟수 카운틱하며 c배열 인덱스 값 증가*/
    for(int i = 0; i < a_size ; i++){
        c[a[i]]++;
    }

    /*배열 c의 인덱스 값 누적합 구하기*/
    for(int i=1; i < c_size; i++){
        c[i] += c[i-1];
    }

    /*배열 A역순으로 훑으며, 배열 C참조하여 정렬*/
    for(int i = a_size-1; i >= 0; i-- ){
        b[c[a[i]]-1] = a[i];
        --c[a[i]];
    }

Code 보기 (c++)