선택 정렬.

정렬 방법론.

1. 최솟값을 찾아서 0번째 위치와 바꿈.

2. 0번째 위치를 제외한 최솟값을 찾아서 1번째 위치와 바꿈.

3. N번째까지의 위치를 제외한 최솟값을 찾아서 N번째와 바꿈.

4. 끝까지 가면 성공.

특징.

1. 정렬되있는 순서로 들어오던 아니던 실행시간이 비슷하다. 항상 비교하는양이 동일하기 때문.

2. 추가적인 기억장소를 요구하지 않는다.

ex)

N개의 원소에 대해서 N-1번의 비교를 해야 되기 때문에(항상 N-1번 비교) 

비교횟수는 N(N-1)2, 시간 복잡도는 O(n^2)

10000개의 데이터를 랜덤한 데이터, 최고, 최악의 상황으로 가정하고 돌려봤는데 

셋다 비슷비슷할 것이라는 예상과 달리 최악의 상황이 시간이 조금 더 걸렸다.

예상대로라면 다 똑같이 나와야 하는데.. 개인적인 생각으로는 데이터를 교환하는데 너무 자주 바꾸다 보니 I/O처럼 부하가 조금씩 쌓인 결과물이 저게 아닐까 생각해본다.

20000개로 돌렸을때는 더 차이가 심해지는걸 알수있었다.

# -*- encoding: cp949 -*-
import time
import random

N = 5000
def swap(a,i,j):
    a[i],a[j] = a[j],a[i]

def CheckSort(a,n):
    Sorted = True
    for i in range(n):
        if a[i] > a[i+1]:
            Sorted = False
        if not Sorted:
            break
    if Sorted: print '정렬 완료.'
    else: print '정렬 오류 발생.'

def SelectionSort(a,N): #선택 정렬
    for i in range(N):
        min = i
        for j in range(i+1,N+1):
            if a[j] < a[min]: min = j
        swap(a,min,i)

def main():
    a = [random.randint(1,65536) for i in range(0,N+1)] #랜덤한 10000개의 데이터
    start_time = time.time()
    SelectionSort(a,N)
    print '(랜덤)선택 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)

    a = [i for i in range(0,N+1)] #정렬된 10000개의 데이터
    start_time = time.time()
    SelectionSort(a,N)
    print '(최고)선택 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)

    a = [i for i in range(N,-1,-1)] #최악의 경우의 10000개의 데이터
    start_time = time.time()
    SelectionSort(a,N)
    print '(최악)선택 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)

if __name__=='__main__':
    main()