[알고리즘] 단순 삽입 정렬(straight insertion sort)

단순 삽입 정렬 (straight insertion sort)

• 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
• 단순 선택 정렬과 비슷해 보이지만 다르다
  • 단순 선택 정렬은 값이 가장 작은 원소를 선택한다.
  • 단순 삽입 정렬은 값이 가장 작은 원소가 아니라 선택된 해당 원소가 있어야할 알맞은 위치를 왼쪽 원소와 비교하며 찾아 삽입한다.
• 장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나는 상태에서는 속도가 아주 빠르다.
• 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다."알맞은 위치에 삽입" 과정
• 선택된 해당 원소가 작은 원소를 만날 때까지 이웃한 왼쪽 원소를 하나씩 대입하는 작업을 반복한다.
• 멈춘 위치에 해당 원소 대입종료 조건

1. 정렬된 배열의 왼쪽 끝에 도달한 경우
2. tmp보다 작거나 키 값이 같은 원소 a[j-1]을 발견한 경우 
3. a = [1,4,6,7,3,9,8] for i in range(1,len(a)): j=i tmp=a[i] while j > 0 and a[j-1] > tmp: a[j] = a[j-1] j -= 1 a[j] = tmp print(a)

이진 삽입 정렬

단순 삽입 정렬은 배열 원소가 많아지면 원소 삽입에 필요한 비교,교환 비용이 커진다. 이를 위해 [[이진 검색법]]을 사용하여 삽입 정렬을 하면 이미 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사하므로 비용을 줄일 수 있다.

a=[6,4,3,7,1,9,8]
for i in range(1,len(a)):
    # 이진 검색법
    key = a[i]
    pl = 0  # 검색 범위의 맨 앞 원소 인덱스
    pr = i-1 # 검색 범위의 맨 끝 원소 인덱스

    while True:
        pc = (pl+pr)//2 # 가운데 원소 값
        if a[pc] == key: # 검색 성공!
            break
        elif a[pc] < key:
            pl = pc + 1
        else:
            pr = pc -1 
        if pl > pr:
            break
    pd = pc + 1 if pl <= pr else pr + 1 # 삽입해야 할 위치의 인덱스

    for j in range(i, pd, -1):
        a[j] = a[j-1]
    a[pd] = key
print(a)

파이썬 표준 라이브러리 bisect 모듈 insort() 함수

import bisect
a=[6,4,3,7,1,9,8]
for i in range(1,len(a)):
    bisect.insort(a,a.pop(i),0,i)
print(a)