[Algorithm] Selection Sort(선택 정렬)

AnHyunDong·2022년 7월 11일
0

Algorithm

목록 보기
1/2

Introduce

  • 본 코드는 Python으로 짜져있습니다.
  • 기준은 오름차순을 기준으로 하고 있습니다.
  • 우측상단의 흰색배경에서 보는 것을 추천드립니다.

개념

  • 가장 작은 value의 index 선택하여 맨 앞 index와 변경
  • 다음 index와 가장 작은 value를 가진 index와 변경
  • 무한 반복

Code

  • 구현 1
lst = [92, 88, 12, 76, 14, 79, 5, 72, 3]
# 선택 정렬
def selection(lst):
    for i in range(0, len(lst)):
        minIdx = i
        for j in range(i, len(lst)):
            if lst[minIdx] > lst[j]:
                minIdx = j    # 최소값 찾기

        # swap
        tmp = lst[i]
        lst [i] = lst[minIdx]
        lst[minIdx] = tmp

        print(i+1, "회차")
        print(lst)

selection(lst)

  • 구현 2
    • swap 사용
lst = [92, 88, 12, 76, 14, 79, 5, 72, 3]
# 선택 정렬
def selection(lst):
    for i in range(len(lst)-1):
        minIdx = i
        for j in range(i-1, len(lst)):
            if lst[minIdx] > lst[j]:
                minIdx = j    # 최소값 찾기
        
        # swap
        lst[i], lst[minIdx] = lst[minIdx], lst[i]

        print(i+1, "회차")
        print(lst)
        
selection(lst)

결과

  • 장점

    • 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적기에, 교환이 많이 이루어져야 하는 상태에서 효율적으로 사용될 수 있으며, 이에 가장 적합한 자료상태는 역순 정렬이다. 즉, 내림차순이 정렬되어 있는 자료를 오름차순으로 재졍렬할 때 적합
  • 단점

    • 정렬을 위한 비교 횟수가 많으며, 이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬할 때 최악의 처리 속도를 보임
  • 정렬 알고리즘 시간복잡도

profile
사진은 남아 추억이 메모는 남아 스펙이 된다

0개의 댓글