Sorting Algorithm

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


종류



시간 복잡도 ( 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

  • 배열 쭉 탐색 후 가장 작은 값 왼쪽부터 차곡차곡 쌓는 방식


📃 코드 ( 접기 / 펼치기 )
#include <iostream>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <time.h>   //시간 측정

using namespace std;

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

//배열의 item을 random으로 삽입
void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%100;
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        cout.width(3);
        cout << i+1 <<". ";
        cout.width(2);
        cout << array[i] << endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

//선택 정렬
void Selection_sort(int *array,int arrlen){
    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] );       //가장 작은값을 왼쪽으로 이동
    }
}

int main(){
    int array[64];
    int arr_sz= sizeof(array)/sizeof(int);

    input_random(array,arr_sz);   //배열에 랜덤값 삽입
    start = clock();
    Selection_sort(array,arr_sz); //선택 정렬
    finish = clock();
    display(array,arr_sz);         //show array
    CalcTime();

    return 0;
}



Insertion Sort


  • stable sort

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

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

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


📃 코드 ( 접기 / 펼치기 )
#include <iostream>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <time.h>   //시간 측정

using namespace std;

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

//배열의 item을 random으로 삽입
void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%100;
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        cout.width(3);
        cout << i+1 <<". ";
        cout.width(2);
        cout << array[i] << endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

void Insertion_sort(int *array,int arrlen){


    int j,item;
    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;


    }
}

int main(){
    int array[64];
    int arr_sz= sizeof(array)/sizeof(int);

    input_random(array,arr_sz);   //배열에 랜덤값 삽입
    start = clock();
    Insertion_sort(array,arr_sz); //삽입 정렬
    finish = clock();
    display(array,arr_sz);         //show array
    CalcTime();

    return 0;
}



Bubble Sort


  • stable sort

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

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


📃 코드 ( 접기 / 펼치기 )
#include <iostream>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <time.h>   //시간 측정

using namespace std;

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

//배열의 item을 random으로 삽입
void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%100;
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        cout.width(3);
        cout << i+1 <<". ";
        cout.width(2);
        cout << array[i] << endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

void Bubble_sort(int *array,int arrlen){

    /*한번 탐색할때마다 배열의 끝에 제일 큰 값이 채워지므로
    배열의 길이-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]);
    }
}

int main(){
    int array[64];

    int arr_sz= sizeof(array)/sizeof(int);
    input_random(array,arr_sz);   //배열에 랜덤값 삽입
    start = clock();
    Bubble_sort(array,arr_sz);    //버블 정렬
    finish = clock();
    display(array,arr_sz);         //show array
    CalcTime();

    return 0;
}



Merge Sort


  • stable sort

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

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

  • 재귀를 이용 ( recursion )

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


📃 코드 ( 접기 / 펼치기 )
#include <iostream>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <time.h>   //시간 측정

using namespace std;

int sorted[64];

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

//배열의 item을 random으로 삽입
void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%100;
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        cout.width(2);
        cout << i+1 <<". ";
        cout.width(2);
        cout << array[i] << endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

void Merge(int array[],int left,int mid,int right){
    int l;
    int i=left;
    int j=mid+1;
    int k=left;

    /*왼쪽 배열과 오른쪽 배열 비교하며 sorted배열에 삽입*/
    while(i<= mid && j<=right){
        if(array[i]<=array[j])
            sorted[k++]=array[i++];
        else
            sorted[k++]=array[j++];
    }

    /*한쪽먼저 다 sorted에 삽입되어 남아있는 배열 값 모두 삽입*/
    if(i>mid){
        for(l=j;l<=right;l++)
            sorted[k++]=array[l];
    }
    else{
        for(l=i; l<=mid; l++)
            sorted[k++]=array[l];
    }

    /*배열 복사*/
    for(l=left; l<=right; l++){
        array[l]=sorted[l];
    }
}
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);
    }
}


int main(){
    int array[1];
    int arr_sz= sizeof(array)/sizeof(int);
    input_random(array,arr_sz);   //배열에 랜덤값 삽입

    start = clock();
    Merge_sort(array,0,arr_sz-1);    //합병 정렬
    finish = clock();
    display(array,arr_sz);         //show array
    CalcTime();

    return 0;
}



Quick Sort


  • Unstable sort

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

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

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

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

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

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


📃 코드 ( 접기 / 펼치기 )
#include <iostream>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <time.h>   //시간 측정

using namespace std;

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%100;
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        cout.width(3);
        cout << i+1 <<". ";
        cout.width(2);
        cout << array[i] << endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

void QuickSort(int array[],int pivot, int arrlen){
   int left = pivot+1, right = arrlen-1;

    if(pivot>=arrlen-1) return;
    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]);
        else swap(array[pivot],array[right]);
   }
    QuickSort(array,pivot,right);
    QuickSort(array,right+1,arrlen);
}

int main(){

 int array[64];
    int arr_sz= sizeof(array)/sizeof(int);
    input_random(array,arr_sz);   //배열에 랜덤값 삽입

    start = clock();
    QuickSort(array,0,arr_sz);    //버블 정렬
    finish = clock();
    display(array,arr_sz);         //show array
    CalcTime();

    return 0;
}



Shell Sort


  • Unstable sort

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

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

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

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

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


📃 코드 ( 접기 / 펼치기 )
#include <iostream>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <time.h>   //시간 측정

using namespace std;

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

//배열의 item을 random으로 삽입
void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%100;
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        cout.width(3);
        cout << i+1 <<". ";
        cout.width(2);
        cout << array[i] << endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

/*기본은 삽입정렬 알고리즘
gap차이만큼의 숫자들을 삽입정렬로 정렬*/
void insertionSort(int *array,int first,int last,int gap){
    int item,j;
    for(int i=first+gap; i<last ; i+=gap ){
        item=array[i];
        /*배열의 제일 왼쪽이거나 앞의 값이 해당 값보다 작다면 배열을 한 칸씩 뒤로 미룸*/
        for(j=i-gap; j>=first && array[j]>item; j-=gap)
            array[j+gap]=array[j];
        array[j+gap]=item;
    }
}


void Shell_sort(int *array,int arrlen){
    int gap;
    for( gap = arrlen/2 ; gap>0; gap/=2){
        if(gap%2 == 0) gap++;         //gap이 짝수라면 홀수로 맞추는 것이 더 좋은 것으로 분석이 됨

        for(int i=0;i<gap;i++){
            insertionSort(array,i,arrlen,gap);
        }
    }
}



int main(){
    int array[64];
    int arr_sz= sizeof(array)/sizeof(int);
    input_random(array,arr_sz);   //배열에 랜덤값 삽입

    start = clock();
    Shell_sort(array,arr_sz); //삽입 정렬
    finish = clock();
    display(array,arr_sz);         //show array
    CalcTime();

    return 0;
}



Heap Sort


  • Unstable sort

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

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

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

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


📃 코드 ( 접기 / 펼치기 )
#include <iostream>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <time.h>   //시간 측정

using namespace std;

#define MAX_ARRAY_SIZE 64

int maxValue=0;     //가장 큰 값을 담을 변수

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

//배열의 item을 random으로 삽입
void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%99 + 1;
        maxValue = (maxValue < array[i]) ? array[i] : maxValue;
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        cout.width(3);
        cout << i+1 <<". ";
        cout.width(2);
        cout << array[i] << endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

/*top-down*/
void top_down_heapify(int* array,int arrlen){
/*인덱스 0을 루트(부모 노드)로 삼고 인덱스 1(왼쪽 자식)부터 maxHeap형태로
 *만들어 주기 위해 swap
 */
    for(int i=1; i < arrlen ; i++){
        int child = i;
        while(child > 0){
            int parent = (child -1) /2;

            if(array[parent] < array[child]){
                swap(array[parent],array[child]);
            }
            child = parent;
        }
    }
}

/*bottom-up*/
void bottom_up_heapify(int* array,int parent,int arrlen){
/*인덱스 0을 루트(부모 노드)로 삼고 인덱스 1(왼쪽 자식)부터 maxHeap형태로
 *만들어 주기 위해 swap */
    while(parent <= arrlen){
        int largest = parent;
        int l = parent * 2 + 1;
        int r = parent * 2 + 2;

        if(l < arrlen && array[largest] < array[l]){
            largest = l;
        }
        if(r < arrlen && array[largest] < array[r]){
            largest = r;
        }

        /*largest가 값이 바뀌었다면 swap해야한다는 뜻
        swap했다면 child로 내려가 아래 서브트리도 확인하기 위해
        parent값 largest로 변환 */
        if(largest != parent) {
            swap(array[parent],array[largest]);
            parent = largest;
        }
        else parent = l;
    }
}

void top_down_HeapSort(int *array, int arrlen){
    top_down_heapify(array,arrlen);  //maxHeap형태로 만들어준다.

    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 max-heap
        루트 노드가 0 기준 ) n개의 노드를 가진 트리라면,
                            마지막 노드 n의 부모 인덱스 번호는 n/2 -1 이다.
        루트 노드가 1 기준 )  n개의 노드를 가진 트리라면,
                            마지막 노드 n의 부모 인덱스 번호는 n/2  이다.
        leafnode들은 더이상 heapify를 안해줘도 되기 때문에 마지막 노드의 부모 노드 부터
        heapify를 시작
        --> heap sort의 초반 build heap부분에서 bottom-up방식은 n/2개만 큼만 수행하므로
        top-down방식보다 bottom-up 방식이 조금 더 성능이 좋다.
    */
    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를 해준다.
    }
}



int main(){
    int *array = new int[MAX_ARRAY_SIZE];

    input_random(array,MAX_ARRAY_SIZE);     //배열에 랜덤값 삽입
    start = clock();
    bottom_up_HeapSort(array,MAX_ARRAY_SIZE);         //계수 정렬
    finish = clock();
    display(array,MAX_ARRAY_SIZE);          //show array
    CalcTime();

    return 0;
}



Radix Sort


  • stable sort

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

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

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

  • 정렬 방식

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


📃 코드 ( 접기 / 펼치기 )

#include <iostream>
#include<queue>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <time.h>   //시간 측정

std::queue<int> q[10];   //10진수 정수형을 정렬하기 때문에 0-9의 버킷
int MAXVALUE=0;         //정렬할 수 중 가장 큰 수

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%1000;
        if(MAXVALUE<array[i]) MAXVALUE=array[i];
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        std::cout.width(3);
        std::cout << i+1 <<". ";
        std::cout.width(2);
        std::cout << array[i] << std::endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

void RadixSort(int *array,int arrlen){
    int digit=1;
    int k;

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

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

    }
}

int main(){
    int array[64];
    int arr_sz= sizeof(array)/sizeof(int);
    input_random(array,arr_sz);   //배열에 랜덤값 삽입

    start = clock();
    RadixSort(array,arr_sz);
    finish = clock();
    display(array,arr_sz);         //show array
    CalcTime();

    return 0;
}



Count Sort


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

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

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

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

  • 과정

    • 정렬할 배열 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을 빼준다.)


📃 코드 ( 접기 / 펼치기 )
#include <iostream>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <string.h> //memset
#include <time.h>   //시간 측정

using namespace std;

#define MAX_ARRAY_SIZE 64

int maxValue=0;

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

//배열의 item을 random으로 삽입
void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%99 + 1;
        maxValue = (maxValue < array[i]) ? array[i] : maxValue;
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        cout.width(3);
        cout << i+1 <<". ";
        cout.width(2);
        cout << array[i] << endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

int* count_sort(int *array,int arrlen){
    int *c = new int[maxValue+1];
    int c_size = maxValue+1;
    int *b = new int[arrlen];

    memset(c,0,c_size*sizeof(int)); //배열c 0으로 초기화

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

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

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

    return b;
}

int main(){
    int *array = new int[MAX_ARRAY_SIZE];

    input_random(array,MAX_ARRAY_SIZE);     //배열에 랜덤값 삽입
    delete array;

    start = clock();
    array = count_sort(array,MAX_ARRAY_SIZE);       //계수 정렬
    finish = clock();
    display(array,MAX_ARRAY_SIZE);          //show array
    CalcTime();

    delete array;
    return 0;
}