selection sort

¼±Åà Á¤·ÄÀº ÃÖ¼Ò°ªÀ» ã¾Æ¼­ ¸Ç ¾ÕÀÇ °ª°ú ±³Ã¼ ÇÏ´Â ¹æ½ÄÀÌ´Ù.

1. ¸®½ºÆ®¿¡¼­ ÃÖ¼Ò °ªÀ» ã´Â´Ù.
2. ÃÖ¼Ò °ªÀ» ¸Ç ¾ÕÀÇ °ª°ú ±³Ã¼ÇÑ´Ù.
3. ±× ´ÙÀ½ À§Ä¡ºÎÅÍ ¹Ýº¹ÀûÀ¸·Î ½ÇÇàÇÑ´Ù. ( N-1¹ø ¹Ýº¹ ½ÇÇàÇÑ´Ù)

¹è¿­¿¡ 5,  4, 3, 2, 1ÀÌ ÀÖÀ»¶§ ¼±Åà Á¤·Ä ¼ø¼­´Â ´ÙÀ½°ú °°´Ù.

Step-1: 1 4 3 2 5   array[0] array[4] ---> 1, 5 ±³Ã¼
Step-2: 1 2 3 4 5   array[1] array[3] ---> 2, 4 ±³Ã¼
Step-3: 1 2 3 4 5
Step-4: 1 2 3 4 5  

¼±ÅÃÁ¤·ÄÀÇ º¹Àâµµ

(N-1) + (N-2) + ... + 2 + 1 = (N-1) * N/2 = N(N-1) / 2

C ÄÚµå


void swap(int *a, int *b)
{
    int temp;

    temp = *a;
    *a = *b;
    *b = temp;
}

void SelectionSort(int arr[], int count)
{
    for (int n = 0; n < count - 1; n++)
    {
        int min = n;
        for (int m = n + 1; m < count; m++)
        {
            if (arr[m] < arr[min])
                min = m;
        }

        if (min != n)
            swap(&arr[min], &arr[n]);
    }
}

Python ÄÚµå


def selectionSort(alist):
    for passnum in range(len(alist)-1):
        min = passnum
        for i in range(passnum + 1 , len( alist )):
            if alist[i]<alist[min]:
                min = i
               
        if min != passnum:
            alist[min], alist[passnum] = alist[passnum], alist[min]
               
alist = [5, 4, 3, 2, 1]
selectionSort(alist)
print(alist)

ÆÄÀ̽ã - range ¹®¹ý:
range(½ÃÀÛ, ³¡, Áõ°¡°ª)
range(½ÃÀÛ, ³¡)
range(³¡)

³¡Àº Æ÷ÇÔÇÏÁö ¾Ê´Â´Ù. range(10)Àº 0ºÎÅÍ 9±îÁö Á¤¼öÀÌ´Ù.

ÆÄÀ̽ã - µÎº¯¼öÀÇ °ªÀ» ¹Ù²Ù´Â ¹æ¹ý:
a, b = b, a
alist[i], alist[i+1] = alist[i+1], alist[i]

ÆÄÀ̽ã - ¹®ÀÚ¿­, ¸®½ºÆ®(¹è¿­) °³¼ö ±¸Çϱâ
len(array)

¼Ò½º : SelectionSort.cpp    SelectionSort.py

C ÄÚµå ÂüÁ¶)
http://proneer.tistory.com/entry/Sort-¼±ÅÃ-Á¤·ÄSelection-Sort

Python ÄÚµå ÂüÁ¶)
http://www.geekviewpoint.com/python/sorting/selectionsort
http://interactivepython.org/courselib/static/pythonds/SortSearch/TheSelectionSort.html