정렬 알고리즘 간단 정리

선택 정렬(selection sort) O($n^2$)

가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나감

 

삽입정렬(insertion sort) O($n^2$)

두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬

역정렬된 경우 최악

#삽입정렬1
def insertion_sort1(A) :
    n = len(A)
    for i in range(1, n):
        key = A[i]
        j = i-1
        while j>=0 and A[j] > key:
            A[j+1] = A[j]
            j-=1
        A[j+1] = key

#삽입정렬2 - 더 오래걸림
def insertion_sort2(a):
    for i in range(1, len(a)): # i 현재 원소의 인덱스
        for j in range(i, 0, -1): 
            if a[j-1]>a[j]:
                a[j], a[j-1] = a[j-1], a[j] # 현재 원소와 직전 원소와 교환

버블정렬(bubble sort) O($n^2$)

인접한 2개의 레코드를 비교하여 순서대로 서로 교환 – 비교-교환 과정을 리스트의 전체에 수행(스캔)

• 한번의 스캔이 완료되면 리스트의 오른쪽 끝에 가장 큰 레코드
• 끝으로 이동한 레코드를 제외하고 다시 스캔 반복

쉘정렬(shell sort) 최악: O($n^2$) 평균:O($n^{1.5}$)

삽입 정렬에 전처리 과정 추가

1) 리스트를 일정 간격(gap)의 부분 리스트로 나눔 – 나뉘어진 각각의 부분 리스트를 삽입정렬 함

2) 간격을 줄임 – 부분 리스트의 수는 더 작아지고, 각 부분 리스트는 더 커짐 (간격이 1인 경우는 삽입 정렬과 동일)

퀵정렬(quick sort) 최악: O($n^2$) 최선:O(nlogn)

분할 정복법 사용

각각의 부분리스트를 다시 퀵정렬

Original: 5,3,8,4,9,1,6,2,7
step1: 1,3,2,4,5,9,6,8,7
step2: 1,3,2,4,5,7,6,8,9
step3: 1,2,3,4,5,6,7,8,9
정렬 완료

 

힙정렬(Heap sort) O(nlogn)

제자리정렬, 상향식 힙트리 생성

1) 리스트를 최대힙으로 만듦

2) 최대힙을 정렬된 리스트로 만듦

최대힙 리스트 만들기!

 

루트와 힙의 마지막 노드 교환

힙 크기 1 감소

downheap 연산 수행