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

Packet Capture Program 만들기

Packet Capture Program 만들기

Linux환경에서 C를 이용해 raw socket을 이용한 tcpdump의 interface를 모방하는 패킷 캡쳐 프로그램 작성하는 것을 목표로 시작했습니다. 캡쳐할 정보는 IPv4(이더넷 타입이 0x0800 (ip헤더의 버전이 4)를 기반으로 2계층인 Ethernet 정보부터 패킷을 수집하여 앞에서부터 잘라내면서, Ethernet header | ip header | TCP/UDP/ICMP header | data(payload) 캡쳐 하는 프로그램을 작성해보았습니다....

Read More
인증된 사용자 정보 조회

인증된 사용자 정보 조회

Spring Security의 Filter들을 모두 거쳐 인증에 통과한 User가 특정 Controller에 도달했을 때, User의 정보가 필요할때가 있다. 이때, Url의 도메인으로 id를 표시하거나 param/body로 계속 전달하기도 무리이며, Filter를 통한 인증시에 이미 한번 유저 정보를 조회하는 로직을 수행하게 된다. 그런데 한번더 select로 조회시 두번 조회하게 되는 비효율적인 상황이 발생하기 때문에 Spring Security의 Context Holder에 들어있는 인증 정보를 가져다 사용하면 Filter에서 인증을 수행한 User의 정보(Details)에 접근할 수 있다....

Read More
데이터 중심 애플리케이션 설계

데이터 중심 애플리케이션 설계

  • Books
  • 2022년 4월 27일

이 책은 총 3부로 구성되어 1부에서는 근본 개념에 대해 설명하고 2부에서는 데이터를 분산 저장하기 위한 내용을, 3부에서는 한 데이터셋에서 다른 데이터셋을 파생하는 시스템애 대해 설명한다. 1장. 데이터 시스템의 기초 1) 신뢰성 잘못될 수 있는 일을 결함이라 부른다. 이 결함을 예측하고 대처할 수 있는 시스템을 내 결함성/탄력성을 가졌다고 말할 수 있다. 결함과 장애는 동일하지 않은데, 결함은 사양에서 벗어난 시스템의 한 구성 요소로 정의되지만, 장애는 사용자에게 필요한 서비스를 제공하지 못하고 시스템 전체가 멈춘 경우이다....

Read More