선택정렬 -스터디-

선택정렬이란?

리스트(배열)안에 난잡하게 정렬되어있는 수들을 오름차순(1->2->3->...) 시킨것이다.
그런데 어떻게 정렬시켰는지가 중요한데, 버블정렬처럼 현재 선택된 수와 그 다음수를 비교해서 변경하는것과는 약간 다르게
선택된 인덱스에 있는 값과 리스트 전체의 값들을 한번씩 비교해가며 한번 순회할때마다 최소값을 찾아서
처음 선택된 인덱스와 바꿔주는 것을 선택정렬이라한다.

공부 방법

노트에 직접 적어가며 리스트의 내용이 선택정렬로 정리 되는 과정을 하나하나 직접 그려가며 말로 나열 하며 이해함.

• [5, 4, 3, 2, 1] 이라는 리스트가 있다.
• 해당 정렬 기법은 처음 선택된 idx와 해당 idx를 제외한 전체 리스트의 idx의 값을 비교하여최소값을 찾아서 선택된 idx와 최소값으로 선택된 idx를 swap해야한다.
• 처음 리스트를 돌때 선택된 idx와 다음 idx의 값이 필요하기 때문에 현재 리스트의 길이가 5이지만 -1을 해서 4까지만 돌게 한다.
• 일단, 목적은 최소값을 찾아야하기 때문에 처음 선택된 idx의 값을 최소값으로 넣어둔다.
  • why? 선택된 idx가 최소값이 될 수도 있기때문에
• 처음 선택된 idx를 기준으로 리스트를 한번 순회해야하기 때문에 for문을 한번 더 사용한다.
  • 두번째 순회에서 for문의 길이는 일단 처음 선택된 idx는 건들면 안되기 때문에 idx + 1을 해준다. 그리고 리스트의 길이 만큼만 크기를 잡아준다.
    • 건들면 안되는 이유 : 같은 idx의 값을 비교해봤자 같은 값이기 때문에 시간 낭비일 뿐이다.
• 이제 처음 선택된 idx의 값이랑 두번째 for문을 통해서 나온 리스트의 값들이랑 비교를 하며 최소값을 가진 idx를 찾아낸다.
• 최소값을 찾았으면 따로 변수에 할당 시켜준다.
• 두번째 for문을 다 돌았으면 마지막으로 결정된 최소값과 처음 선택된 idx를 바꿔준다.

이런식으로 적었다 지웠다 하며 최종적으로 정리된 내용을 가지고 코드를 짜면 쉽게 코딩을 할 수 있다.

생각한 내용 적어보기

처음 내용 정리 후 코딩한 내용

def solution(s_sort):
    for i in range(len(s_sort) - 1):
        min_idx = i
        for j in range(i, len(s_sort) - 1):  # 잘못된 부분
            if s_sort[min_idx] > s_sort[j]:
                min_idx = j
        s_sort[min_idx], s_sort[i] = s_sort[i], s_sort[min_idx]
    return s_sort


if __name__ == "__main__":
    s_sort = [5, 2, 3, 4, 1]
    print(solution(s_sort))

처음 내용 정리했을때 나름 쉽게 정리가 되길래 이번껀 쉽겠다! 라고 생각 하고 함수를 호출했는데, 나오는 값은 원하는 결과가 아니었다.
그래서 디버깅을 돌려봣더니, 두번째 for문에서 길이를 잘 못 주고 있어서 그런 결과가 나온것이다.

노트에 정리만 했지 막상 코드를 입력할땐 생각을 잘 안하고 작성한것 같다. 이 부분에 있어선 반성하고 있다.

위 코드에서 두번째 for문을 보면 i에서 len(s_sort)-1 까지 돈다고 설정 해놨는데,

이대로 해석해본다면 i가 0이고 len(s_sort)-1이 4로 idx가 0, 1, 2, 3까지만 돌게 될것이다.

i는 어짜피 처음 선택된 idx값이라 돌 필요 없고 그 이후는 3까지만 순회함으로써 마지막 값은 전혀 건들이지 못하게 된다.

문제를 알고 다시 수정한 코드

def solution(s_sort):
    for i in range(len(s_sort) - 1):
        min_idx = i
        for j in range(i + 1, len(s_sort)):
            if s_sort[min_idx] > s_sort[j]:
                min_idx = j
        s_sort[min_idx], s_sort[i] = s_sort[i], s_sort[min_idx]
    return s_sort


if __name__ == "__main__":
    s_sort = [5, 2, 3, 4, 1]
    print(solution(s_sort))

내가 바란대로 정상적이게 나온다.