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