DataStructure in Python[Selection Sort]

출처 : http://onestep.tistory.com/43

       : http://stackoverflow.com/questions/14836228/is-there-a-standardized-method-to-swap-two-variables-in-python

선택정렬

: 정렬 알고리즘 중에 가장 간단한 알고리즘이라고 한다. 최소값을 가장 앞쪽으로 가져오는 작업을 반복하는 형식으로 정렬한다.

자체내장된 파이썬의 sort() 함수

sortList = []
 
for i in range(21):
    sortList.append(random.randint(1,100))
    selectList.append(random.randint(1,100))
    print i,'번째 :\t','*'*sortList[i]
 
# 간단하게 sort()를 사용한 경우
sortList.sort()
print '\n ===========================================정렬후======================================='
for i in range(len(sortList)):
    print i,'번째 :\t','*'*sortList[i]

결과

 
0 번째 :     **************
1 번째 :     ***************************************
2 번째 :     ************
3 번째 :     ************************************************************************************************
4 번째 :     *********************************
5 번째 :     ***************************************************
6 번째 :     ************
7 번째 :     *********************************
8 번째 :     *********************************
9 번째 :     *******************************************************
10 번째 :    *****************************
11 번째 :    ********************
12 번째 :    *******************************************************************
13 번째 :    ***
14 번째 :    ****************************************************************************************
15 번째 :    **************************************
16 번째 :    ******************************************************
17 번째 :    ****************************************************
18 번째 :    ***************************************************************************
19 번째 :    **************************************
20 번째 :    *******
 
 ===========================================정렬후=======================================
0 번째 :     ***
1 번째 :     *******
2 번째 :     ************
3 번째 :     ************
4 번째 :     **************
5 번째 :     ********************
6 번째 :     *****************************
7 번째 :     *********************************
8 번째 :     *********************************
9 번째 :     *********************************
10 번째 :    **************************************
11 번째 :    **************************************
12 번째 :    ***************************************
13 번째 :    ***************************************************
14 번째 :    ****************************************************
15 번째 :    ******************************************************
16 번째 :    *******************************************************
17 번째 :    *******************************************************************
18 번째 :    ***************************************************************************
19 번째 :    ****************************************************************************************
20 번째 :    ************************************************************************************************

Selection Sort 를 이용

밑의 소스는 값을 swap하는 방식에서 출처에서의 소스와 조금 차이가 난다.

파이썬에서는 임시 값 없이 두값을 서로 교체 할수 있다. 그래서 좀더 간편한 Tuple Swap을 사용했다.

XOR

x = x ^ y
y = y ^ x
x = x ^ y

Temporary variable

w = x
x = y
y = w
del w

Tuple swap

x, y = y, x

def selected_sort(random_list):
    # -1을 해주는 이유는 밑의 for 문에서 보면 이해할수 있다.
    for sel in range(len(random_list)-1):
        # min = random_list[sel]
        minindex = sel
 
        # find min value
        for step in range(sel+1, len(random_list)):
            if random_list[minindex] > random_list[step]:
                minindex = step
 
            # 정렬 과정 출력 - 상세 버전
            for k in range(len(random_list)):
                if k == step or k == sel:
                   print "[{}]".format(random_list[k]),
                else:
                   print '',random_list[k],'',
            print '','\t\t',minindex
 
 
        # swap
        print '\n이전값',random_list[sel],'<-->','이후값',random_list[minindex]
        print '===========================\n\n'
        # tuple swap
        random_list[minindex],random_list[sel] = random_list[sel],random_list[minindex]
 
 
def Main():
    for i in range(len(selectList)):
        print i,'번째 :\t','*'*selectList[i]
    print ''
    selected_sort(selectList)
    print '\n ===========================================셀렉트정렬후======================================='
    for i in range(len(selectList)):
        print i,'번째 :\t','*'*selectList[i]
 
 
 
print "==="*10,"셀렉트 정렬 전","==="*10
Main()

사실 소스만 보고는 좀 이해가 안되어서 좀 출력을 시켜봤다.

첫번재 비교만 봐도 대충 이해가 갈 것이다.

 
[32] [75]  92   54   7   99   6   64   28   19   14   79   78   19   66   42   88   60   85   21   61           0
[32]  75  [92]  54   7   99   6   64   28   19   14   79   78   19   66   42   88   60   85   21   61           0
[32]  75   92  [54]  7   99   6   64   28   19   14   79   78   19   66   42   88   60   85   21   61           0
[32]  75   92   54  [7]  99   6   64   28   19   14   79   78   19   66   42   88   60   85   21   61           4
[32]  75   92   54   7  [99]  6   64   28   19   14   79   78   19   66   42   88   60   85   21   61           4
[32]  75   92   54   7   99  [6]  64   28   19   14   79   78   19   66   42   88   60   85   21   61           6
[32]  75   92   54   7   99   6  [64]  28   19   14   79   78   19   66   42   88   60   85   21   61           6
[32]  75   92   54   7   99   6   64  [28]  19   14   79   78   19   66   42   88   60   85   21   61           6
[32]  75   92   54   7   99   6   64   28  [19]  14   79   78   19   66   42   88   60   85   21   61           6
[32]  75   92   54   7   99   6   64   28   19  [14]  79   78   19   66   42   88   60   85   21   61           6
[32]  75   92   54   7   99   6   64   28   19   14  [79]  78   19   66   42   88   60   85   21   61           6
[32]  75   92   54   7   99   6   64   28   19   14   79  [78]  19   66   42   88   60   85   21   61           6
[32]  75   92   54   7   99   6   64   28   19   14   79   78  [19]  66   42   88   60   85   21   61           6
[32]  75   92   54   7   99   6   64   28   19   14   79   78   19  [66]  42   88   60   85   21   61           6
[32]  75   92   54   7   99   6   64   28   19   14   79   78   19   66  [42]  88   60   85   21   61           6
[32]  75   92   54   7   99   6   64   28   19   14   79   78   19   66   42  [88]  60   85   21   61           6
[32]  75   92   54   7   99   6   64   28   19   14   79   78   19   66   42   88  [60]  85   21   61           6
[32]  75   92   54   7   99   6   64   28   19   14   79   78   19   66   42   88   60  [85]  21   61           6
[32]  75   92   54   7   99   6   64   28   19   14   79   78   19   66   42   88   60   85  [21]  61           6
[32]  75   92   54   7   99   6   64   28   19   14   79   78   19   66   42   88   60   85   21  [61]          6
 
이전값 32 <--> 이후값 6
===========================

맨 오른편 숫자는 인덱스 숫자이다.

32가 비교의 대상인데 모든 값들과 비교를 하는 것이 보인다.

하지만 실은 32는 7이라는 숫자까지만 비교를 한다. 그 이후에는 7이 자신보다 작은값이 나타날때 까지 비교를 한다. 그래서 우측의 인덱스 숫자가 바뀐 것이다.

이런식으로 값이 가장 작은 index를 찾으면서 모든 값들을 비교하는 것이다.

비교가 끝나면 32와 가장 작은 값을 교체를 한다.

그 결과 아래와 같이 정렬이 된다.

============================== 셀렉트 정렬 전 ==============================
0 번째 :     ********************************
1 번째 :     ***************************************************************************
2 번째 :     ********************************************************************************************
3 번째 :     ******************************************************
4 번째 :     *******
5 번째 :     ***************************************************************************************************
6 번째 :     ******
7 번째 :     ****************************************************************
8 번째 :     ****************************
9 번째 :     *******************
10 번째 :    **************
11 번째 :    *******************************************************************************
12 번째 :    ******************************************************************************
13 번째 :    *******************
14 번째 :    ******************************************************************
15 번째 :    ******************************************
16 번째 :    ****************************************************************************************
17 번째 :    ************************************************************
18 번째 :    *************************************************************************************
19 번째 :    *********************
20 번째 :    *************************************************************
 
 
 ===========================================셀렉트정렬후=======================================
0 번째 :     ******
1 번째 :     *******
2 번째 :     **************
3 번째 :     *******************
4 번째 :     *******************
5 번째 :     *********************
6 번째 :     ****************************
7 번째 :     ********************************
8 번째 :     ******************************************
9 번째 :     ******************************************************
10 번째 :    ************************************************************
11 번째 :    *************************************************************
12 번째 :    ****************************************************************
13 번째 :    ******************************************************************
14 번째 :    ***************************************************************************
15 번째 :    ******************************************************************************
16 번째 :    *******************************************************************************
17 번째 :    *************************************************************************************
18 번째 :    ****************************************************************************************
19 번째 :    ********************************************************************************************
20 번째 :    ***************************************************************************************************

선택 정렬은 이중 루프이기 때문에 O(N^2)의 성능을 가진다고 한다.