퀵 정렬

퀵 정렬

퀵 정렬은 가장 많이 사용되는 알고리즘이다.

퀵 정렬에서는 피벗이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준을 피벗이라고 한다.

퀵 정렬을 사용할 때는 피벗을 미리 명시해야 한다.

피벗을 정하는 방식은 여러 가지가 있는데 호어 분할을 이용해 설명한다.

 

리스트에서 첫 번째 데이터를 피벗으로 정한다.

그 후 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.

다 찾으면 데이터를 서로 교환한다.

이런 과정을 반복하며 정렬을 한다.

피벗은 5로 정한다. 그 후 왼쪽에서 5보다 큰 값, 오른쪽에서 5보다 작은 값을 찾는다.

왼쪽에서는 7, 오른쪽에서는 4가 선택됐다.

그 후 자리를 바꾼다.

5 4 9 0 3 1 6 2 7 8로 정렬이 되었다.

 

이 과정을 반복하여 첫 번째 정렬을 마쳤다.

이제 5를 기준으로 왼쪽에서 다시 정렬해주고 오른쪽에서도 다시 위와 같은 정렬 과정을 반복하여 정렬을 마친다.

 

 

널리 사용되고 있는 직관적인 퀵 정렬 코드

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left <= right):
        # 피벗보다 큰 데이터를 찾을 때까지 반복 
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

파이썬의 장점을 살린 퀵 정렬 코드

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array

    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

 

 

퀵 정렬의 시간 복잡도

평균 시간 복잡도는 O(NlogN)이다.

앞에서 했던 삽입 정렬, 선택 정렬보다 굉장히 빠르다.

 

 

계수 정렬

특정한 조건이 부합될 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용이 가능하다.

일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1000000을 넘지 않을 때 효과적으로 사용 가능하다.

 

 

배열에 있는 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

 

 

계수 정렬 코드

 

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

 

계수 정렬 시간 복잡도

데이터의 개수 N  데이터 중 최댓값의 크기 K 이면

시간 복잡도는 O(N+K)이다.