Sorting Algorithm

1. 종류


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

3. 공간 복잡도 ( 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)

4. 정렬의 특성

1) 안정 정렬( stable sort )

  • 정렬되지 않은 상태의 같은 키값을 가진 원소의 순서가 정렬 후에도 유지 되는 정렬
  • 상황에 따라서 객체나 키값이 여러개인 값들을 정렬 하려고 할때 원래의 순서가 바뀌게 되면 안될 수 있기 때문에 그때는 stable한 sort를 이용해야 한다.
  • Bubble, Insertion, Merge, Counting, Bucket, Radix Sort가 해당된다.

Note

예를 들어, 같은 5이더라도 a가 앞에 있는 5, b가 뒤에 있는 5라고 한다면
3 5(a) 1 4 5(b) 2 이 정렬 후에

1 2 3 4 5(a) 5(b) 와 같이 같은 키값의 원소의 순서가 유지 되는 것.


2) 불안정 정렬 ( unstable sort )

  • 정렬되지 않은 상태의 같은 키값을 가진 원소의 순서가 정렬 후에 유지되는 것을 보장 할 수 없는 정렬
  • Selection, Shell, Heap, Quick Sort가 해당된다.

Note

예를 들어, 같은 5이더라도 a가 앞에 있는 5, b가 뒤에 있는 5라고 한다면
3 5(a) 1 4 5(b) 2 이 정렬 후에

1 2 3 4 5(b) 5(a) 와 같이 같은 키값의 원소의 순서가 유지 되지 않는 것.



5. 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;
}


6. 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;
}


7. 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;
}


8. 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;
}



9. 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;
}


10. 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;
}


11. 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;
}


12. 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;
}


13. 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;
}

Tags :

Related Posts

Array와 List

Array와 List

1. 배열 가장 기본적인 자료구조로써, 논리적 저장 순서와 물리적 저장 순서가 일치하고 인덱스를 통하여 원소에 접근이 가능하다. 대부분의 언어에서 [] 를 이용해서 배열을 제공한다. 2. 리스트 배열과 달리 원소들 간의 논리적인 순서로 연결되어 구성있고, 삽입과 삭제를 수행하기 위해서는 첫 원소부터 모두 search해야한다. 자료구조 Tree에 기본이...

Read More
Hugo와 Github page로 블로그 구축

Hugo와 Github page로 블로그 구축

Note 블로그를 작성하기로 마음 먹은 후에 가장 먼저 할 일이 블로그를 만드는 것이었다. hugo와 github을 사용하면서 블로그를 open하는 과정과 겪었던 문제점들, 추가한 내용들을 정리하여 hugo를 선택하신분들에게 조금이나마 도움이 되고자 한다. hugo를 선택한 이유 github page를 이용하여 블로그를 운영하는데 다양한 generat...

Read More
포인트 적립을 위한 웹 제작기

포인트 적립을 위한 웹 제작기

방학때 엄마집에 있으며 엄마 가게를 도와주다가 갑자기 엄마가 운영하는 꽃집에 포인트 적립을 한번 도입해보고 싶다고 하셨다. 지류로 하는 도장형식은 하기 싫다고 하셨고 운영도 애매하다 하시면서 요즘 태블릿으로 전화번호만 입력하면 포스기랑 연동되어 적립이 된다더라라고 말을 하셨다. 그런데 이는 년단위 계약에 적지 않은 돈을 지불하는 유료 서비스이고 우...

Read More