[6일차] 04 정렬 : 04-3 삽입 정렬, 04-4 퀵 정렬

삽입 정렬

파이썬 구현

for i in range(1, len(array)):
    for j in range(i, 0, -1): 
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

 

삽입 정렬이랑 버블 정렬이랑 코드가 비슷한듯

#버블 정렬 코드
for i in range(N-1, 0, -1):
    flag = True #swap이 발생했는지 확인

    for j in range(i):
        if A[j] > A[j+1]:
            A[j], A[j+1] = A[j+1], A[j]
            flag = False   

    if flag:  #swap이 한 번도 발생하지 않았으므로 종료
        break

버블 정렬은 정렬되지 않은 영역에서 계속 swap이 발생하는거고,

삽입 정렬은 정렬되지 않은 영역에서 하나를 뽑아서 정렬된 영역으로 삽입하는 거라 swap이 더 적게 발생한다.

 

 

퀵 정렬

파이썬 구현

def quick_sort(arr, start, end):
    if start >= end: return # 원소가 1개인 경우
    pivot = start
    i, j = start + 1, end
    
    while i <= j:
        while i <= end and arr[i] <= arr[pivot]:
            i += 1
        while j > start and arr[j] >= arr[pivot]:
            j -= 1
        if i > j: # 엇갈린 경우
            arr[j], arr[pivot] = arr[pivot], arr[j]
        else: # 엇갈리지 않은 경우
            arr[j], arr[i] = arr[i], arr[j]
    quick_sort(arr, start, j - 1)
    quick_sort(arr, j + 1, end)