Sort

์ •๋ ฌ์ด๋ž€ ๋ฌผ๊ฑด์„ ํฌ๊ธฐ ์ˆœ์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ์ด๋‚˜ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ๋‚˜์—ดํ•œ ๊ฒƒ์ด๋‹ค.

  • ๋‹จ์ˆœํ•˜์ง€๋งŒ ๋น„ํšจ์œจ์  : ์‚ฝ์ž…, ์„ ํƒ, ๋ฒ„๋ธ” ์ •๋ ฌ

  • ๋ณต์žกํ•˜์ง€๋งŒ ํšจ์œจ์  : ํ€ต, ํžˆํ”„, ํ•ฉ๋ณ‘, ๊ธฐ์ˆ˜ ์ •๋ ฌ

์„ ํƒ์ •๋ ฌ(selection sort)

๊ฐ€์žฅ ์ž‘์€ ๋ฐ์ดํ„ฐ๋ฅผ ์„ ํƒํ•ด ๋งจ ์•ž์— ์žˆ๋Š” ๋ฐ์ดํ„ฐ์™€ ๋ฐ”๊พธ๊ณ , ๊ทธ ๋‹ค์Œ ์ž‘์€ ๋ฐ์ดํ„ฐ๋ฅผ ์„ ํƒํ•ด ์•ž์—์„œ ๋‘ ๋ฒˆ์งธ ๋ฐ์ดํ„ฐ์™€ ๋ฐ”๊พธ๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜๋Š” ๋ฐฉ๋ฒ•

  1. ์ฃผ์–ด์ง„ ๋ฆฌ์ŠคํŠธ ์ค‘์— ์ตœ์†Ÿ๊ฐ’์„ ์ฐพ๋Š”๋‹ค.

  2. ๊ทธ ๊ฐ’์„ ๋งจ ์•ž์— ์œ„์น˜ํ•œ ๊ฐ’๊ณผ ๊ต์ฒดํ•œ๋‹ค(ํŒจ์Šค(pass)).

  3. ๋งจ ์ฒ˜์Œ ์œ„์น˜๋ฅผ ๋บ€ ๋‚˜๋จธ์ง€ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ๊ต์ฒดํ•œ๋‹ค.

void selection_sort(int list[], int n){
    int i, j, least,tmp;

    for(i=0;i<n-1;i++){
        least = i;
        for(j=i+1;j<n;j++){
            if(list[j]<list[least]){
                least = j;
            }
            SWAP(list[i],list[j],tmp);
        }
    }
}
array = [7,5,9,0,3,1,6,2,4,8]



for i in range(0,len(array)-1):
    min = i;
    for j in range(i+1,len(array)):
        if array[j] < array[min]:
            min = j;

    array[i], array[min] = array[min], array[i];
    print(array)

๋น„๊ตํ•˜๋Š” ๊ฒƒ์ด ์ƒ์ˆ˜ ์‹œ๊ฐ„์— ์ด๋ฃจ์–ด์ง„๋‹ค๋Š” ๊ฐ€์ • ์•„๋ž˜, n๊ฐœ์˜ ์ฃผ์–ด์ง„ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ด์™€ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ๋ฐ์—๋Š” O(n^2) ๋งŒํผ์˜ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค. ์ด๋Š” ์ •๋ ฌํ•ด์•ผํ•˜๋Š” ๋ฐ์ดํ„ฐ ๊ฐœ์ˆ˜๊ฐ€ 100๋ฐฐ ๋Š˜์–ด๋‚˜๋ฉด ์ด๋ก ์ ์œผ๋กœ ์ˆ˜ํ–‰์‹œ๊ฐ„์€ 10,000๋ฐฐ ๋Š˜์–ด๋‚˜๋Š” ๊ฒƒ์ด๋‹ค.

์‚ฝ์ž…์ •๋ ฌ(insertion sort)

์ž๋ฃŒ ๋ฐฐ์—ด์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ์•ž์—์„œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ์ด๋ฏธ ์ •๋ ฌ๋œ ๋ฐฐ์—ด ๋ถ€๋ถ„๊ณผ ๋น„๊ตํ•˜์—ฌ, ์ž์‹ ์˜ ์œ„์น˜๋ฅผ ์ฐพ์•„ ์‚ฝ์ž…ํ•จ์œผ๋กœ์จ ์ •๋ ฌ์„ ์™„์„ฑํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

์‚ฝ์ž… ์ •๋ ฌ์€ ํ•„์š”ํ•  ๋•Œ๋งŒ ์œ„์น˜๋ฅผ ๋ฐ”๊พธ๋ฏ€๋กœ ๋ฐ์ดํ„ฐ๊ฐ€ ๊ฑฐ์˜ ์ •๋ ฌ๋˜์–ด ์žˆ์„ ๋•Œ ํ›จ์”ฌ ํšจ์œจ์ ์ด๋‹ค.

void insert_sort(int arr[],int n){
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i-1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
    }
}
def insert_sort(array):
    # print(array)
    for i in range(1,len(array)):
        for j in range(i,0,-1):
            if array[j] < array[j-1]:
                array[j], array[j-1] = array[j-1], array[j]
            else:
                break
    # print(array)
    return array
  • ๋ณต์žก๋„

    • ์ตœ์„ ์˜ ๊ฒฝ์šฐ(์ด๋ฏธ ์ •๋ ฌ) : O(n)

    • ์ตœ์•…์˜ ๊ฒฝ์šฐ(์—ญ์ˆœ์œผ๋กœ ์ •๋ ฌ๋œ ๊ฒฝ์šฐ) : O(n^2)

๋ณดํ†ต ์‚ฝ์ž… ์ •๋ ฌ์ด ํ€ต ์ •๋ ฌ๋ณด๋‹ค ๋น„ํšจ์œจ ์ ์ด๋‚˜, ์ด๋ฏธ ์ •๋ ฌ๋˜์–ด์žˆ๋Š” ๊ฒฝ์šฐ์—๋Š” ํ€ต์ •๋ ฌ๋ณด๋‹ค ๋” ๊ฐ•๋ ฅํ•˜๋‹ค. ๋”ฐ๋ผ์„œ ๊ฑฐ์˜ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ์ƒํƒœ๋ผ๋ฉด, ์‚ฝ์ž… ์ •๋ ฌ์„ ์ด์šฉํ•˜๋Š” ๊ฒƒ์ด ๋” ์ข‹๋‹ค.

๋ฒ„๋ธ”์ •๋ ฌ(bubble sort)

์ธ์ ํ•œ 2๊ฐœ์˜ ๋ ˆ์ฝ”๋“œ๋ฅผ ๋น„๊ตํ•˜์—ฌ ์ˆœ์„œ๋Œ€๋กœ ๋˜์–ด ์žˆ์ง€ ์•Š์œผ๋ฉด ์„œ๋กœ ๊ตํ™˜ํ•œ๋‹ค.

void bubble_sort(int list[], int n){
    int i,j,tmp;
    for(i=n-1;i>0;i--){
        for(j=0;j<i;j++){
            if(list[i]<list[j])SWAP(list[i], list[j], tmp);
        }
    }
}
  • ๋ณต์žก๋„(์ตœ์ƒ, ํ‰๊ท , ์ตœ์•…) : O(n^2)

ํ•ฉ๋ณ‘ ์ •๋ ฌ(merge_sort)

  1. ๋ฆฌ์ŠคํŠธ๋ฅผ ๋‘ ๊ฐœ์˜ ๊ท ๋“ฑํ•œ ํฌ๊ธฐ๋กœ ๋ถ„ํ• ํ•˜๊ณ  ๋ถ„ํ• ๋œ ๋ถ€๋ถ„๋ฆฌ์‹œํŠธ๋ฅผ ์ •๋ ฌํ•œ๋‹ค.

  2. ์ •๋ ฌ๋œ ๋‘๊ฐœ์˜ ๋ถ€๋ถ„ ๋ฆฌ์ŠคํŠธ๋ฅผ ํ•ฉํ•˜์—ฌ ์ „์ฒด ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•œ๋‹ค.

void merge(int array[], int left, int mid, int right)
{
    int i, j, k, m;

    i = left;
    j = mid + 1;
    k = left;    //๊ฒฐ๊ณผ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค

    int tempArray[MAX];

    //left๋ถ€ํ„ฐ mid ๊นŒ์ง€์˜ ๋ธ”๋ก๊ณผ mid+1๋ถ€ํ„ฐ right๊นŒ์ง€์˜ ๋ธ”๋ก์„ ์„œ๋กœ ๋น„๊ตํ•˜๋Š” ๋ถ€๋ถ„
    while (i <= mid && j <= right) {
        if (array[i] < array[j]){   //left index ๊ฐ’์ด right index ๊ฐ’๋ณด๋‹ค ์ž‘์œผ๋ฉด left index ๊ฐ’์„ ๊ฒฐ๊ณผ result์— ๋ณต์‚ฌ
            tempArray[k] = array[i];
            i++;
        }else{        //์•„๋‹ˆ๋ผ๋ฉด right index ๊ฐ’์„ ๊ฒฐ๊ณผ result์— ๋ณต์‚ฌ
            tempArray[k] = array[j];
            j++;
        }
        k++;
    }

    // left ๋ธ”๋ก์˜ ๊ฐ’์€ ๋‹ค ์ฒ˜๋ฆฌ๋˜์—ˆ๋Š”๋ฐ right ๋ธ”๋ก์˜ index๊ฐ€ ์•„์ง ๋‚จ์•„์žˆ์„ ๊ฒฝ์šฐ
    // right index๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ๊ฒฐ๊ณผ result์— ๋ณต์‚ฌ
    if (i > mid){
        for (m = j; m <= right; m++){
            tempArray[k] = array[m];
            k++;
        }
    } else {                    // left ๋ธ”๋ก์˜ index๊ฐ€ ์•„์ง ๋‚จ์•„์žˆ์„ ๊ฒฝ์šฐ left index๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ๊ฒฐ๊ณผ result์— ๋ณต์‚ฌ
        for (m = i; m <= mid; m++){
            tempArray[k] = array[m];
            k++;
        }
    }

    for(m = left; m <= right; m++){
        array[m] = tempArray[m];
    }
}

void merge_sort(int array[], int left, int right)
{
    int mid;

    // ๋ถ„ํ• ์ด ๋‹ค ๋˜์ง€ ์•Š์•˜์„ ๊ฒฝ์šฐ if ๋ฌธ ์‹คํ–‰
    if(left < right){
        mid = (left + right)/2;

        merge_sort(array, left, mid);      //์™ผ์ชฝ ๋ธ”๋ก ๋ถ„ํ• 
        merge_sort(array, mid+1, right);  //์˜ค๋ฅธ์ชฝ ๋ธ”๋ก ๋ถ„ํ• 
        merge(array, left, mid, right);   //๋ถ„ํ• ๋œ ๋ธ”๋ก ๋ณ‘ํ•ฉ
    }
}
  • ๋ณต์žก๋„ : O(n*log(n))

๊ธฐ์ˆ˜์ •๋ ฌ(Radix Sort)

๊ธฐ์ˆ˜ ์ •๋ ฌ์€ ์ •์ˆ˜์˜ ์ž๋ฆฌ์ˆ˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‚ฎ์€ ์ž๋ฆฌ์ˆ˜๋ถ€ํ„ฐ ๋น„๊ตํ•ด ์ •๋ ฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด 3์ž๋ฆฌ ์ˆ˜๋ผ๋ฉด 1์˜์ž๋ฆฌ, 10์˜์ž๋ฆฌ , 100์˜ ์ž๋ฆฌ ์ˆซ์ž๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ๋น„๊ตํ•ด์„œ ์ •๋ ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.

void radix_sort(int a[])
{
    int i, b[MAX], m=0, exp=1;


    // m์— ์ตœ๋Œ€๊ฐ’์„ ์ €์žฅ
    for( i=0 ; i<MAX ; i++ )
    {
        if( a[i] > m )
            m = a[i];
    }

    // m์˜ ์ž๋ฆฌ์ˆ˜๋ณด๋‹ค exp๊ฐ€ ์ปค์ง€๋ฉด ์ข…๋ฃŒ
    while( m/exp > 0 )
    {
        int bucket[10] = {0}; //์ˆ˜๋ณ„๋กœ ๋น„๊ตํ•ด์„œ ์ž„์‹œ๋กœ ์ €์žฅํ•ด๋‘˜ ๊ณต๊ฐ„

        for( i=0 ; i<MAX ; i++ )
            bucket[a[i]/exp%10]++;

        for( i=1 ; i<10 ; i++ )
            bucket[i] += bucket[i-1];

        for( i=MAX-1 ; i>=0 ; i-- )
            b[--bucket[a[i]/exp%10]] = a[i];

        for( i=0 ; i<MAX ; i++ )
            a[i] = b[i];

        exp *= 10; //์ž๋ฆฌ์ˆ˜ ๋น„๊ต๊ฐ€ ๋๋‚˜๋ฉด ๋‹ค์Œ ์ž๋ฆฌ์ˆ˜!
    }
}
def counting_sort(arr, digit):
    n = len(arr)

    # ๋ฐฐ์—ด์˜ ํฌ๊ธฐ์— ๋งž๋Š” output ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•˜๊ณ  10๊ฐœ์˜ 0์„ ๊ฐ€์ง„ count๋ž€ ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•œ๋‹ค.
    output = [0] * n
    count = [0] * 10

    # ๊ฐ ์ž๋ฆฌ์ˆ˜์— ๋งž๊ฒŒ count๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ์ค€๋‹ค.
    for i in range(0, n):
        index = int(arr[i] / digit)
        count[(index) % 10] += 1

    # count ๋ฐฐ์—ด์— ์•ž์˜ ์ˆ˜๋ฅผ ์ฐจ๋ก€๋Œ€๋กœ ๋”ํ•ด ๊ฐ ์ž๋ฆฟ์ˆ˜๋ฅผ ์ •ํ•ด์ค€๋‹ค.
    # ex) 123,134,151,121
    # before : [ 0, 2, 0, 1, 1 ]
    # after : [ 0, 2, 2, 3, 4 ]
    for i in range(1, 10):
        count[i] += count[i - 1]

    # ๊ฐ ์ž๋ฆฟ์ˆ˜ ๋ณ„๋กœ output ๋ฐฐ์—ด์— ์ฐจ๋ก€๋Œ€๋กœ ์ •๋ ฌํ•œ๋‹ค.
    # ex) 1์˜ ์ž๋ฆฌ ์˜ˆ์ œ
    # [ 0, 121, 0, 0]
    # [ 151, 121, 0, 0]
    # [ 151, 121, 0, 134]
    # [ 151, 121, 123, 134]
    i = n - 1
    while i >= 0:
        index = int(arr[i] / digit)
        output[count[(index) % 10] - 1] = arr[i]
        count[(index) % 10] -= 1
        i -= 1

    # arr์— output์„ ํ• ๋‹นํ•œ๋‹ค.
    return output


# Method to do Radix Sort
def radix_sort(arr):
    # arr ๋ฐฐ์—ด์ค‘์—์„œ ์ตœ๋Œ€๊ฐ’์„ ๊ฐ€์ ธ์™€ ์ž๋ฆฟ์ˆ˜๋ฅผ ํŒŒ์•…ํ•œ๋‹ค.
    # ex) ์ตœ๋Œ€๊ฐ’์ด 9833 ์ด๋ฉด 1000๊นŒ์ง€
    maximum = max(arr)
    # ์ž๋ฆฟ์ˆ˜๋งˆ๋‹ค countingSorting์„ ์‹œ์ž‘ํ•œ๋‹ค.
    digit = 1
    while int(maximum / digit) > 0:
        arr = counting_sort(arr, digit)
        digit *= 10

    return arr
  • ๋ณต์žก๋„ : O(dn) d๋Š” ์ž๋ฆฟ์ˆ˜

ํ€ต์ •๋ ฌ(Quick sort)

  1. pivot(๊ธฐ์ค€๊ฐ’) ์ •ํ•˜๊ธฐ

  2. pivot๋ณด๋‹ค ์ž‘์€ ์›์†Œ๋“ค์€ ์™ผ์ชฝ, ํฐ ์›์†Œ๋Š” ์˜ค๋ฅธ์ชฝ

  3. pivot์„ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ ๋ฐฐ์—ด๊ณผ ์˜ค๋ฅธ์ชฝ ๋ฐฐ์—ด์„ ์ƒˆ๋กœ์šด ๋ฐฐ์—ด๋กœ ์ •ํ•˜๊ณ  ๊ฐ ๋ฐฐ์—ด๊ตฌ๊ฐ„์—์„œ 1๋ฒˆ๊ณผ์ • ์žฌ๊ท€์  ๋ฐ˜๋ณต

  4. ์ผ๋ฐ˜์ ์œผ๋กœ ์ฒ˜์Œ ๋˜๋Š” ๋งˆ์ง€๋ง‰ ์›์†Œ๋ฅผ pivot์œผ๋กœ ์žก๋Š”๋‹ค.

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high- 1; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        //pi = partition index
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
#include <algorithm>

bool compare(int a, int b){
// ์˜ค๋ฆ„์ฐจ์ˆœ   
//    return a<b;
// ๋‚ด๋ฆผ์ฐจ์ˆœ
    return a>b;
}

bool comparep(POINT a, POINT b){
    if(a.x == b.x ) return a.y < b.y;
    else return a.x < b.x;
}

//์ฒ˜์Œ๋ถ€ํ„ฐ n-1๋ฒˆ์งธ๊นŒ์ง€ ์›์†Œ๋ฅผ compareํ•จ์ˆ˜์˜ ์ •์˜๋Œ€๋กœ ์ •๋ ฌ
//ํ€ต์ •๋ ฌ ๊ธฐ๋ฐ˜์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.
//std::sort(์ •๋ ฌํ•  ์ž๋ฃŒ์˜ ์‹œ์ž‘ ์ฃผ์†Œ, ์ •๋ ฌํ•  ์ž๋ฃŒ์˜ ๋งˆ์ง€๋ง‰ ์ฃผ์†Œ,[๋น„๊ตํ•จ์ˆ˜ ์ฃผ์†Œ])
std::sort(S,S+n,compare);
def quick_sort(array):

    if len(array) <= 1:
        return

    pivot = array[0]
    temp = array[1:]

    left = [i for i in temp if i < pivot]
    right = [i for i in temp if i > pivot]

    return quick_sort(left) + [pivot] + quick_sort(right)
  • ์‹œ๊ฐ„ ๋ณต์žก๋„

    • ํ‰๊ท ์  : O(nlog(n))

    • ์ตœ์•…์˜ ๊ฒฝ์šฐ : O(N^2)

๋ฐ์ดํ„ฐ ์ˆ˜

N^2(์„ ํƒ์ •๋ ฌ, ์‚ฝ์ž… ์ •๋ ฌ)

NlogN(ํ€ต ์ •๋ ฌ)

1,000

์•ฝ 1,000,000

์•ฝ 10,000

1,000,000

์•ฝ 1,000,000,000,000

์•ฝ 20,000,000

๋‹ค๋งŒ ํ€ต์ •๋ ฌ์€ ํ‰๊ท ์ ์œผ๋กœ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(NlogN)์ด์ง€๋งŒ ์ตœ์•…์˜ ๊ฒฝ์šฐ(์ด๋ฏธ ์ •๋ ฌ๋˜์–ด ์žˆ๋Š” ๊ฒฝ์šฐ) O(N^2)์ธ ๊ฒƒ์„ ์ฃผ์˜ํ•ด์•ผํ•œ๋‹ค.

ํž™ ์ •๋ ฌ(heap sort)

  1. n๊ฐœ์˜ ๋…ธ๋“œ์— ๋Œ€ํ•œ ์™„์ „์ด์ง„ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•œ๋‹ค. ์ด๋•Œ ๋ฃจํŠธ ๋…ธ๋“œ๋ถ€ํ„ฐ ๋ถ€๋…ธ๋“œ, ์™ผ์ชฝ ์ž๋…ธ๋“œ, ์˜ค๋ฅธ์ชฝ ์ž๋…ธ๋“œ ์ˆœ์œผ๋กœ ๊ตฌ์„ฑํ•œ๋‹ค.

  2. ์ตœ๋Œ€ ํž™์„ ๊ตฌ์„ฑํ•œ๋‹ค.

  3. ํ•œ๋ฒˆ์— ํ•˜๋‚˜์”ฉ ์š”์†Œ๋ฅผ ํž™์—์„œ ์‚ญ์ œํ•˜๋ฉด์„œ ์ €์žฅํ•œ๋‹ค.

ํž™ ์ •๋ ฌ์ด ์ตœ๋Œ€๋กœ ์œ ์šฉํ•œ ๊ฒฝ์šฐ๋Š” ์ „์ฒด ์ž๋ฃŒ๊ฐ€ ์•„๋‹Œ ๊ฐ€์žฅ ํฐ ๊ฐ’ ๋ช‡๊ฐœ๋งŒ ํ•„์š”ํ•  ๋•Œ์ด๋‹ค.

๊ตฌํ˜„

  • ํž™๊ตฌํ˜„์€ ํž™(heap)์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค.

void heap_sort(int arr[], int n){
    int i;
    Heap heap;
    init(&heap);

    for(i=0;i<n;i++){
        insert_max(&heap, arr[i]);
    }
    for(i=n-1;i>=0;i--){
        arr[i]=delete_max(&heap);
    }
}
  • ๋ณต์žก๋„

    • ํž™ ์‚ญ์ œ ์‹œ๊ฐ„ O(logn)n = *O(nlogn)

๊ณ„์ˆ˜ ์ •๋ ฌ(Count Sort)

๊ณ„์ˆ˜ ์ •๋ ฌ์€ ํŠน์ •ํ•œ ์กฐ๊ฑด์ด ๋ถ€ํ•ฉํ•  ๋•Œ๋งŒ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ ๋งค์šฐ ๋น ๋ฅธ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

๋ชจ๋“  ๋ฐ์ดํ„ฐ๊ฐ€ ์–‘์˜ ์ •์ˆ˜์ธ ์ƒํ™ฉ์„ ๊ฐ€์ •ํ•ด๋ณผ ๊ฒƒ์ด๋‹ค. ๋ฐ์ดํ„ฐ์˜ ๊ฐœ์ˆ˜๊ฐ€ N, ๋ฐ์ดํ„ฐ ์ค‘ ์ตœ๋Œ€๊ฐ’์ด K์ผ ๋•Œ, ๊ณ„์ˆ˜ ์ •๋ ฌ์€ ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ ์ˆ˜ํ–‰์‹œ๊ฐ„ O(N+K)๋ฅผ ๋ณด์žฅํ•œ๋‹ค.

๊ณ„์ˆ˜ ์ •๋ ฌ์€ ๋ฐ์ดํ„ฐ์˜ ํฌ๊ธฐ ๋ฒ”์œ„๊ฐ€ ์ œํ•œ๋˜์–ด ์ •์ˆ˜ ํ˜•ํƒœ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์„ ๋•Œ๋งŒ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค. ๋งŒ์•ฝ ๋ฐ์ดํ„ฐ์˜ ๊ฐ’์ด ๋ฌดํ•œํ•œ ๋ฒ”์œ„๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ์‹ค์ˆ˜ํ˜• ๋ฐ์ดํ„ฐ๊ฐ€ ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ์—๋Š” ๊ณ„์ˆ˜ ์ •๋ ฌ์€ ์‚ฌ์šฉํ•˜๊ธฐ ์–ด๋ ต๋‹ค. ์ผ๋ฐ˜์ ์œผ๋กœ ๊ฐ€์žฅ ํฐ ๋ฐ์ดํ„ฐ์™€ ๊ฐ€์žฅ ์ž‘์€ ๋ฐ์ดํ„ฐ์˜ ์ฐจ์ด๊ฐ€ 1,000,000์„ ๋„˜์ง€ ์•Š์„ ๋•Œ ํšจ๊ณผ์ ์œผ๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

์ •๋ ฌ (12) - ๊ณ„์ˆ˜ ์ •๋ ฌ (Counting Sort)

๊ณ„์ˆ˜ ์ •๋ ฌ์€ ์œ„์™€ ๋ชจ๋“  ๋ฒ”์œ„๋ฅผ ๋‹ด์„ ์ˆ˜ ์žˆ๋Š” ํฌ๊ธฐ์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์„ ์–ธํ•ด์•ผํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํฌ๊ธฐ์— ์ œํ•œ์ด ์žˆ๋‹ค.

def count_sort(array):
    count = [0] * (max(array)+1)

    for i in array:
        count[i]+=1

    for j in range(len(count)):
        for x in range(count[j]):
            print(j, end=' ')
  • ์‹œ๊ฐ„ ๋ณต์žก๋„ : O(N+K), ์ตœ๋Œ€๊ฐ’ ํฌ๊ธฐ K, ๋ฐ์ดํ„ฐ์ˆ˜ N

ํŒŒ์ด์ฌ 3.7 ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋น„๊ต

๋ฐ์ดํ„ฐ ์ˆ˜(N)

์„ ํƒ ์ •๋ ฌ

ํ€ต ์ •๋ ฌ

๊ธฐ๋ณธ ์ •๋ ฌ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ

100

0.0123

0.00156

0.00000753

1000

0.354

0.00343

0.0000365

10000

15.475

0.0312

0.000248

์„ ํƒ ์ •๋ ฌ์€ ๊ธฐ๋ณธ ์ •๋ ฌ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ํฌํ•จํ•ด ๋‹ค๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๋น„๊ตํ–ˆ์„ ๋•Œ ๋งค์šฐ ๋น„ํšจ์œจ ์ ์ด์ง€๋งŒ, ํŠน์ •ํ•œ ๋ฆฌ์ŠคํŠธ์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ์„๋•Œ๋Š” ์œ ์šฉํ•˜๊ฒŒ ์‚ฌ์šฉ๋œ๋‹ค.

sorted()

ํŒŒ์ด์ฌ ๊ธฐ๋ณธ ์ •๋ ฌ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ์—์„œ ์ œ๊ณตํ•˜๋Š” sorted()๋Š” ํ€ต์ •๋ ฌ ๊ณผ ๋™์ž‘ ๋ฐฉ์‹์ด ๋น„์Šทํ•œ ๋ณ‘ํ•ฉ ์ •๋ ฌ์„ ๊ธฐ๋ฐ˜(๋ณ‘ํ•ฉ ์ •๋ ฌ + ์‚ฝ์ž…์ •๋ ฌ)์œผ๋กœ ๋งŒ๋“ค์–ด์กŒ๋‹ค. ๋ณ‘ํ•ฉ ์ •๋ ฌ์€ ํ€ต์ •๋ ฌ๋ณด๋‹ค ์ผ๋ฐ˜์ ์œผ๋กœ ๋А๋ฆฌ์ง€๋งŒ, ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ O(NlogN) ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๋ณด์žฅํ•œ๋‹ค.

๋ฆฌ์ŠคํŠธ, ๋”•์…”๋„ˆ๋ฆฌ ์ž๋ฃŒํ˜•์„ ๋ฐ›์•„์„œ ์ •๋ ฌ๋œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
result = sorted(arr)
print(result)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(arr) # [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

์ •๋ ฌ์‹œ์— Key ๋งค๊ฐœ๋ณ€์ˆ˜๋ฅผ ์ž…๋ ฅ๋ฐ›์•„ ์ •๋ ฌํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ, key๊ฐ’์œผ๋กœ๋Š” ์ •๋ ฌ ๊ธฐ์ค€์˜ ํ•˜๋‚˜์˜ ํ•จ์ˆ˜๊ฐ€ ์ž…๋ ฅ๋œ๋‹ค.

arr = [('ํŽ˜์ด์ปค', 26), ('ํ…Œ๋””', 25), ('์ผ€๋ฆฌ์•„', 20)]

def setting(data):
    return data[1]

print(sorted(arr, key=setting)) # [('์ผ€๋ฆฌ์•„', 20), ('ํ…Œ๋””', 25), ('ํŽ˜์ด์ปค', 26)]

sort()

๋ฆฌ์ŠคํŠธ ๋ณ€์ˆ˜๊ฐ€ ํ•˜๋‚˜ ์žˆ์„ ๋•Œ ๋‚ด๋ถ€ ์›์†Œ๋ฅผ ๋ฐ”๋กœ ์ •๋ ฌํ•  ์ˆ˜๋„ ์žˆ๋‹ค. sort() ๋ฅผ ์ด์šฉํ•˜๋ฉด ๋ณ„๋„์˜ ์ •๋ ฌ๋œ ๋ฆฌ์ŠคํŠธ๊ฐ€ ๋ฐ˜ํ™˜๋˜์ง€ ์•Š๊ณ  ๋‚ด๋ถ€ ์›์†Œ๊ฐ€ ๋ฐ”๋กœ ์ •๋ ฌ๋œ๋‹ค.

arr.sort()
print(arr) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [('ํŽ˜์ด์ปค', 26), ('ํ…Œ๋””', 25), ('์ผ€๋ฆฌ์•„', 20)]

def setting(data):
    return data[1]
arr.sort(key=setting)
print(arr) # [('์ผ€๋ฆฌ์•„', 20), ('ํ…Œ๋””', 25), ('ํŽ˜์ด์ปค', 26)]

์ •๋ ฌ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋Š” ํ•ญ์ƒ ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ ์‹œ๊ฐ„๋ณต์žก๋„ O(NlogN)์„ ๋ณด์žฅํ•œ๋‹ค.

Last updated

Was this helpful?