정렬 알고리즘 - 퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위츠를 바꾸는 방법

시간 복잡도는 O(NlogN)이며 최악의 경우 O(N^2)

 

 

 

 

 

 

 

답안 예시

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)

 

작성한 답안

numList = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
max_num, min_num = numList[0], numList[0]

def swift(start, end):
    pivot = start-1
    max_index, min_index = 0, 0
    
    if pivot >= end:
        return
        
    while True:
        # 피벗기준 오른쪽으로 큰 데이터 찾기
        for i in range(start, end+1):
            max_index = i
            
            if numList[pivot] < numList[i]:
                max_num = numList[i]
                break
                
        # 피벗기준 왼쪽으로 작은 데이터 찾기
        for j in range(end, start-2, -1):
            min_index = j
            
            if numList[pivot] > numList[j]:
                min_num = numList[j]
                break
                
        # 위치가 엇갈리는 경우 피벗과 작은 데이터의 위치를 서로 변경
        if max_index >= min_index:
            numList[pivot], numList[min_index] = numList[min_index], numList[pivot]
            break
            
        else:
            if pivot == min_index:
                continue
                
            else:
                numList[max_index], numList[min_index] = numList[min_index], numList[max_index]
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    swift(start, min_index-1)
    swift(min_index+2, end)
    
swift(1, len(numList)-1)

print(numList)

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

 

출처 : https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5