[Python] 단순 선택/삽입 정렬 & 이진 삽입 정렬

1> 단순 선택 정렬 O(n^2)

: 말그대로 가장 작은 애 부터 선택해서 순서에 맞는 위치로 옮기며 작업 반복

def select_sort(List):
    n=len(List)
    for i in range(n-1
                  ):
        min=i
        for j in range(i,n):
            if List[min] > List[j]:
                min=j
        List[i],List[min]=List[min],List[i]
        
    return List

List=list(map(int,input().split()))
print(*select_sort(List))          

 

2> 단순 삽입 정렬 O(n^2)

: 노드를 하나씩 선택해서 알맞은 위치에 삽입함

def insert_sort(List):
    k=0
    n=len(List)
    for i in range(1,n):
        k=i
        for j in range(i-1,-1,-1):
            if List[k] < List[j]:
                List[k],List[j]=List[j],List[k]
                k=j
                
        
    return List
List=list(map(int,input().split()))
print(*insert_sort(List))    

* 단순 삽입 정렬은 원소 수가 많아지면, 필요한 비교,교환 비용이 커짐

 

+) 단순 정렬(버블/선택/삽입 정렬) 모두 O(n^2)로 프로그램 효율이 좋지 않음!

-> 개선해보자!

 

3> 이진 삽입 정렬

(삽입 정렬을 개선)

-비교에 O(nlogn) & 삽입에 O(n)으로 개선됨

 

: 이진 검색법을 이용하여 이미 정렬을 마친 배열을 제외하고,

원소를 삽입해야 할 위치를 검사하므로 비용을 줄일 수 있다!

 

bisect이라는 이진 탐색 모듈을 사용하여 쉽게 구현할 수 있다.

 

import bisect

def binary_sort(List):
    for i in range(1,len(List)):
        bisect.insort(List,List.pop(i),0,i)
        
    return List
    
List=list(map(int,input().split()))
print(*binary_sort(List))