선택 정렬 알고리즘

• 데이터를 처음부터 끝가지 훑어 가면서 가장 작은 값을 찾은 후

  그 값을 첫 번째 데이터와 자리를 바꾸고

  그 다음 두 번째로 작은 데이터를 찾아

  두 번째의 데이터와 자리를 바꾸는 방법으로 구현되는 알고리즘

  

선택 정렬 알고리즘 구현

import random
import time




def selected_sort(random_list):
    compare_count = 0
    exchange_count = 0
    start = time.time()
    
    # 인덱스 순회를 위함 
    # 리스트의 0번 인덱스부터 마지막 인덱스까지
    for sel in range(len(random_list) -1):
        # 가장 작은 value를 첫번째 인덱스로 가정하고 순회하기 위함
        min = random_list[sel]
        minindex = sel
        
        # find min value
        # 다음 인덱스부터 끝 인덱스까지 순회하기 위함
        for step in range(sel+1, len(random_list) ):
            compare_count += 1 # 비교횟수
            # 최소값보다 작다면 
            if min > random_list[step]:
                exchange_count += 1 # 교환 횟수
                # 최소값 갱신
                min = random_list[step]
                # 최소값 인덱스 갱신
                minindex = step
        # swap
        random_list[minindex] = random_list[sel]
        random_list[sel] = min
    
    end = time.time() - start
    print(f"데이터의 크기 : {len(random_list)}")
    print(f"비교 횟수: {compare_count}")
    print(f'교환 횟수: {exchange_count}')
    print(f"{end}")
    
if __name__ == "__main__":
    list = []
    for i in range(100):
        list.append(random.randint(1, 100))
    print("< Before Sort >")
    print(list)
    selected_sort(list) 
    print("< After Sort >")
    print(list)

시간의 효율성

• O(N^2)의 실행 시간

코드의 효율성

• 반복문을 2번 사용하여 O(N^2)의 성능이 되므로 그다지 좋은 알고리즘이라 보기 어려움