[PYTHON] 파이썬_정렬 (선택정렬, 삽입정렬)

 

안녕하세요

겉바속촉입니다

!^^!

 

 

!!파이썬 시작하기!!

 

 

 

 

이번에는

정렬 

선택정렬, 삽입정렬에 대해서

알아보도록 하겠습니다

 

 

 

 

 

---

 

 

 

정렬

 

 

지난번에 배웠던 이진 검색은

사실 정렬 되어있다는 전제 하에 가능했던 것인데요:)

 

 

2021/01/07 - [IT 일기 (상반기)/PYTHON] - [PYTHON] 파이썬_이진검색, 검색시간비교

[PYTHON] 파이썬_이진검색, 검색시간비교

 

이번에는 선택 정렬에 대해서 알아볼게요

 

 

 

 

선택정렬

 

• 알 수 없는 영역에서 가장 작은 항목을 찾고, 그 항목을 인덱스 i로 옮기는 방식
• 즉, 가장 작은 값을 0번으로 0번 값을 가장 작은 값의 인덱스로 옮기는 것
• 또 그 다음 범위에서 가장 작은 값 찾고 1번 값으로 보내고 1번 값이 그 자리로 가는 것
• 이렇게 차례차례 옮겨가면서 정렬해나감!!

 

 

 

다음과 같은 코드를 작성해주세요:)

 

# L[b: ] 내에서 가장 작은 값의 인덱스를 반환
def find_min(L: list, b: int) -> int:

    smallest = b                   #가장 작은 값의 인덱스에 b할당
    i = b + 1                      #인덱스가 이동해나가는 중
    while i != len(L):             #인덱스가 리스트 도는 동안
        if L[i] < L[smallest]:     #값이 가장 작다고 한 값보다 작다면
            smallest = i
        i = i + 1

    return smallest    

#그럼 이제 바꿔치기해야하는 것 만들기 (선택정렬)
def selection_sort(L: list) -> None:
    i = 0
    while i != len(L):
        smallest = find_min(L, i)                   #리스트에서 가장 작은 값을 찾아 그것의 인덱스 i를 할당
        L[i], L[smallest] = L[smallest], L[i]       #그럼 현재 위치의 값과 가장 작은 값을 cross
        i = i + 1                                   #그리고 다시 index 증가시킴
    

L = [ 3, 4, 6, -1, 2, 5]
print(L)
selection_sort(L)
print(L)

 

결과!!

제대로 정렬된 게 보이시죠?

 

 

 

 

 

 

 

삽입정렬

 

• 정렬된 부분과 정렬되지 않은 부분 존재
• 정렬되지 않은 부분에서 가장 작은 값을 찾고 정렬된 부분에 넣어주기
• 정렬된 부분이 더 늘어남

 

 

 

다음과 같은 코드를 작성해주세요:)

 

# 기 정렬된 영역에 L[:b+1] 내 올바른 위치에 L[b]값을 삽입하는 것
def insert(L: list, b: int) -> None:
    i = b
    while i != 0 and L[i-1] >= L[b]:                   #리스트의 뒤에서부터 가는 중(0이 아닐때까지 돈다)
        i = i - 1

    value = L[b]
    del L[b]
    L.insert(i, value)

def insertion_sort(L: list) -> None:
    i = 0

    while i != len(L):
        insert(L, i)
        i = i + 1


L = [ 3, 4, 6, -1, 2, 5] 
print(L)
insertion_sort(L)
print(L)

 

 

결과를 보니 선택정렬한 결과랑 동일하게 나오네요:)

 

 

 

 

 

 

성능 비교

 

시간 측정하는 함수 만들어주세요:)

 

import time, random

def built_in(L: list) -> None:
    L.sort()

def print_times(L: list) -> None:
    print(len(L), end='\t')
    for func in (selection_sort, insertion_sort, built_in):
        if func in (selection_sort, insertion_sort) and len(L) > 10000:
            continue
        L_copy = L[:]
        t1 = time.perf_counter()
        func(L_copy)
        t2 = time.perf_counter()
        print("{0:7.1f}".format((t2 - t1) * 1000.0), end = '\t')
    
    print()


for list_size in [ 10, 1000, 2000, 3000, 4000, 5000, 10000 ]:
    L = list(range(list_size))
    random.shuffle(L)
    print_times(L)

 

built in을 만든 이유는

해당 list라는 객체에 sort라는 메소드를 제공해주는 데

그것도 시간을 측정해보는 거에요:)

 

 

첫번째 열은 리스트의 크기

두번째 열은 선택정렬

세번째 열은 삽입정렬

마지막 열은 내장되어 있는 sort 메서드

 

 

삽입정렬이 선택정렬보다는 속도가 빠르고

내장된 sort 메서드가 가장 빠르네요!!!!