Kwak Jisub

정리를 미루지 말자!

새싹 AI 프로그래머
화이팅!

2 분 소요

정렬

  • python에 기본 내장된 sort(), sorted()는 Timsort 알고리즘을 사용한다.
    • Timsort는 병합 정렬 및 삽입 정렬에서 파생된 하이브리드 정렬 알고리즘
    • Python 프로그래밍 언어에서 사용하기 위해 2002년 Tim Peters가 발명
    • Timsort는 버전 2.3부터 Python의 표준 정렬 알고리즘
In [1]: 
num = [5, 2, 3, 4, 1]
print(*sorted(num))
Out [1]: 
1 2 3 4 5

1. 시간복잡도 비교

  • 비교 정렬
    \(O(n log n)\)보다 더 나은 성능을 낼 수 없다.
이름 Best Avg Worst
삽입 정렬 \(n\) \(n^2\) \(n^2\)
선택 정렬 \(n^2\) \(n^2\) \(n^2\)
버블 정렬 \(n\) \(n^2\) \(n^2\)
셸 정렬 \(nlogn\) gap에 따라 gap에 따라, \(n^{1.25}\)
팀 정렬 \(n\) \(nlogn\) \(nlogn\)
퀵 정렬 \(nlogn\) \(nlogn\) \(n^2\)
힙 정렬 \(nlogn\) \(nlogn\) \(nlogn\)
병합 정렬 \(nlogn\) \(nlogn\) \(nlogn\)
  • 비교가 아닌 정렬
    항목의 크기 k, 숫자크기 d, 정렬될 수의 범위 r
이름 Best Avg Worst
계수 정렬 \(-\) \(n+r\) \(n+r\)
기수 정렬 \(-\) \(n*\frac{k}{d}\) \(n*\frac{k}{d}\)

2. 시간복잡도 \(n^2\)

삽입 정렬

  • 삽입 정렬(Insertion sort)-안정

    두번째 자료부터 그 전의 자료들과 비교하여 삽입위치를 지정, 자료들을 뒤로 옮기고 지정한 자리에 삽입하여 정렬

    gif

In [2]: 
num = [5, 2, 3, 4, 1]
print('최초\t:', *num)
for i in range(1, len(num)):
    for j in range(i, 0, -1):
        if num[j-1] > num[j]:
            num[j-1], num[j] = num[j], num[j-1]
        print(f'{i},{i-j+1}회전\t:', *num)
print('최종\t:', *num)
Out [2]: 
최초	: 5 2 3 4 1
1,1회전	: 2 5 3 4 1
2,1회전	: 2 3 5 4 1
2,2회전	: 2 3 5 4 1
3,1회전	: 2 3 4 5 1
3,2회전	: 2 3 4 5 1
3,3회전	: 2 3 4 5 1
4,1회전	: 2 3 4 1 5
4,2회전	: 2 3 1 4 5
4,3회전	: 2 1 3 4 5
4,4회전	: 1 2 3 4 5
최종	: 1 2 3 4 5
In [3]: 
# 좀 더 최적화(좌측 정렬된 자리에서 해당 숫자보다 작은 범위는 비교하지 않음)
num = [5, 2, 3, 4, 1]
print('최초\t:', *num)
for i in range(1, len(num)):
    j=i
    while j > 0 and num[j] < num[j-1]:
        num[j], num[j-1] = num[j-1], num[j]
        j -= 1
        print(f'{i},{i-j}회전\t:', *num)
print('최종\t:', *num)
Out [3]: 
최초	: 5 2 3 4 1
1,1회전	: 2 5 3 4 1
2,1회전	: 2 3 5 4 1
3,1회전	: 2 3 4 5 1
4,1회전	: 2 3 4 1 5
4,2회전	: 2 3 1 4 5
4,3회전	: 2 1 3 4 5
4,4회전	: 1 2 3 4 5
최종	: 1 2 3 4 5

선택 정렬

  • 선택 정렬(Selection sort)-불안정
    첫번째 자료를 두번째부터 마지막 자료까지 비교하여 최솟값을 찾아 교체, 두번째부터 그 과정을 반복하여 정렬
    같은 값을 가지는 자료가 있을 경우 상대적인 위치가 변경될 수 있음(불안정)

    gif

In [4]: 
num = [5, 2, 4, 3, 1]
print('최초\t:', *num)
for i in range(len(num)-1):
    min_idx = i
    # 최솟값 찾기
    for j in range(i+1, len(num)):
        if num[j] < num[min_idx]:
            min_idx = j
    if i != min_idx:
        num[i], num[min_idx] = num[min_idx], num[i]
    print(f'{i+1}회전\t:', *num)
print('최종\t:', *num)
Out [4]: 
최초	: 5 2 4 3 1
1회전	: 1 2 4 3 5
2회전	: 1 2 4 3 5
3회전	: 1 2 3 4 5
4회전	: 1 2 3 4 5
최종	: 1 2 3 4 5

버블 정렬

  • 거품 정렬(Bubble sort)-안정
    배열 내에 서로 인접한 두 요소를 계속 비교하며 서로 교환하는 정렬방식
    자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하므로 거의 쓰이지 않음

    gif

In [5]: 
num = [5, 2, 3, 4, 1]
print('최초\t:', *num)
for i in range(len(num)-1, 0, -1):
    for j in range(i):
        if num[j] > num[j+1]:
            num[j], num[j+1] = num[j+1], num[j]
    print(f'{len(num)-i}회전\t:', *num)
print('최종\t:', *num)
Out [5]: 
최초	: 5 2 3 4 1
1회전	: 2 3 4 1 5
2회전	: 2 3 1 4 5
3회전	: 2 1 3 4 5
4회전	: 1 2 3 4 5
최종	: 1 2 3 4 5

쉘 정렬

  • 쉘 정렬(Shell sort)
    삽입정렬을 보완한 알고리즘
    gap만큼 떨어진 요소들을 삽입 정렬
In [6]: 
num = [5, 2, 6, 3, 4, 7, 1]
print('최초\t:', *num)
N = len(num)
gap = N // 2
circle = 0
while gap > 0:
    circle += 1
    for i in range(gap, N):
        tmp = num[i]
        j = i - gap
        while j >= 0 and num[j] > tmp:
            num[j+gap] = num[j]
            j -= gap
        num[j+gap] = tmp
    gap //= 2
    print(f'{circle}회전\t:', *num)
print('최종\t:', *num)
Out [6]: 
최초	: 5 2 6 3 4 7 1
1회전	: 1 2 6 3 4 7 5
2회전	: 1 2 3 4 5 6 7
최종	: 1 2 3 4 5 6 7

Reference

댓글남기기

참고