🧪선택정렬 알고리즘 연습

선택 정렬 알고리즘 구현을 list for문을 통해서 list길이를 사용하지 않고 원소를 가지고 구현하려했다. 아래 코드를 살펴보자

arr = [7, 5, 9, 0, 1, 6, 2, 4, 8]

for i in arr:  # 비교값

    min = i

    for ii in arr:

        if min > ii:

            print(i)

            min = ii

    # switch를 하기 위해선 index를 이용해야한다

    # for ii in range(1,len(arr)):

        # if min < arr[ii] :

           # print(arr[ii])

           # min = arr[ii]

이렇게 구혔을 때 문제는 각 원소들을 스위치할 수 있는 방법이 없다. (지금의 내가 알고 있는 지식으론 그렇다) 이를 개선하기 위해서는 list의 길이를 for문의 i로 반환 받아서 각 list의 index로 접근하는 방법 밖에 없다. 이를 구현한 코드는 아래와 같다.

arr = [7, 5, 9, 0, 1, 6, 2, 4, 8]

for i in range(len(arr)):

    min = i  # index를 기준으로 값을 비교한다.

    for ii in range(i+1, len(arr)):

        if arr[min] > arr[ii]:

            min = ii

    arr[min], arr[i] = arr[i], arr[min]

print(arr)

우선 변화되는 순서를 알아야한다. 변화되는 순서는 i번째 index를 기준으로 두번째 for문에서 i번 다음 단계부터 모든 요소들을 비교한다. 모든 값들을 비교하는 동안 arr은 아무일이 일어나지 않는다. 다만 min은 현재 리스트에서 가장 작은 값을 찾는다. 그것이 바로 0이 되고 스위치 구문에서 값을 서로 스위치하고 range(i+1,len(arr))에 맞춰서 다음 i번째를 다시 비교한다. 여기서 시작단계가 i+1이기 때문에 스위치된 앞자리 index min부분은 무시하고 리스트를 검토하게 되는 것이다.

  ...

 for ii in range(i+1, len(arr)):

        if arr[min] > arr[ii]:

            min = ii  # 5

        print(ii, arr)

    arr[min], arr[i] = arr[i], arr[min]  # 5, 7

print(arr)

 

1 [7, 5, 9, 0, 1, 6, 2, 4, 8]
2 [7, 5, 9, 0, 1, 6, 2, 4, 8]
3 [7, 5, 9, 0, 1, 6, 2, 4, 8]
4 [7, 5, 9, 0, 1, 6, 2, 4, 8]
5 [7, 5, 9, 0, 1, 6, 2, 4, 8]
6 [7, 5, 9, 0, 1, 6, 2, 4, 8]
7 [7, 5, 9, 0, 1, 6, 2, 4, 8]
8 [7, 5, 9, 0, 1, 6, 2, 4, 8]
2 [0, 5, 9, 7, 1, 6, 2, 4, 8]
3 [0, 5, 9, 7, 1, 6, 2, 4, 8]
4 [0, 5, 9, 7, 1, 6, 2, 4, 8]
5 [0, 5, 9, 7, 1, 6, 2, 4, 8]
6 [0, 5, 9, 7, 1, 6, 2, 4, 8]
7 [0, 5, 9, 7, 1, 6, 2, 4, 8]
8 [0, 5, 9, 7, 1, 6, 2, 4, 8]
3 [0, 1, 9, 7, 5, 6, 2, 4, 8]
4 [0, 1, 9, 7, 5, 6, 2, 4, 8]
5 [0, 1, 9, 7, 5, 6, 2, 4, 8]
6 [0, 1, 9, 7, 5, 6, 2, 4, 8]
7 [0, 1, 9, 7, 5, 6, 2, 4, 8]
8 [0, 1, 9, 7, 5, 6, 2, 4, 8]
4 [0, 1, 2, 7, 5, 6, 9, 4, 8]
5 [0, 1, 2, 7, 5, 6, 9, 4, 8]
6 [0, 1, 2, 7, 5, 6, 9, 4, 8]
7 [0, 1, 2, 7, 5, 6, 9, 4, 8]
8 [0, 1, 2, 7, 5, 6, 9, 4, 8]
5 [0, 1, 2, 4, 5, 6, 9, 7, 8]
6 [0, 1, 2, 4, 5, 6, 9, 7, 8]
7 [0, 1, 2, 4, 5, 6, 9, 7, 8]
8 [0, 1, 2, 4, 5, 6, 9, 7, 8]
6 [0, 1, 2, 4, 5, 6, 9, 7, 8]
7 [0, 1, 2, 4, 5, 6, 9, 7, 8]
8 [0, 1, 2, 4, 5, 6, 9, 7, 8]
7 [0, 1, 2, 4, 5, 6, 9, 7, 8]
8 [0, 1, 2, 4, 5, 6, 9, 7, 8]
8 [0, 1, 2, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 4, 5, 6, 7, 8, 9]

 

구현할때 머리로는 그림이 그려지지만 이를 컴퓨터 기반, 코딩 기반으로 논리적으로 구현하는 부분에 어려움이 있다. 이는 다양한 상황을 접하지 않았기 때문이기에 많은 문제를 풀어보면서 많은 노력을 기울여야 한다 느낀다.