고급정렬2. 퀵정렬(Quick Sort) 완벽 마스터하기

1. 퀵정렬(Quick Sort)의 기본 개념

2. 예시를 통한 퀵정렬의 이해 

3. 퀵정렬 구현하기

 

 

1. 퀵정렬(Quick Sort)의 기본 개념

 

(1) 퀵정렬의 기본 개념

퀵정렬은 하나의 기준점(pivot)을 정해서, 이보다 작은 것은 왼쪽으로 담고, 큰 것을 오른쪽으로 담는 함수입니다. 

 

이 정렬이 재미있는 이유는 재귀함수를 통해서 구현한다는 점과 향후 학습할 이진트리함수나 다른 내용에서도 이해하는데 도움이 된다는 거에요. 이거는 나중에 다루기로 하겠습니다. 

 

2. 예시를 통한 퀵정렬의 이해 

 

(1) 예시 - [3, 9, 4, 2]

 

예시 데이터는 [3, 9, 4, 2]로 해보도록 하겠습니다. 

 

기준점은 3으로 잡고, 이제 순차적으로 [9, 4, 2]를 비교해보죠. 

 

첫 번째. 9의 경우 3보다 크기 때문에 오른쪽으로 이동 -> 왼쪽: 없음 / pivot: 3 /오른쪽: 9

두 번째. 4의 경우 3보다 크기 때문에 오른쪽으로 이동 -> 왼쪽: 없음 / pivot: 3 /오른쪽: 4, 9

세 번째. 2의 경우 2보다 작기 때문에 왼쪽으로 이동 -> -> 왼쪽: 2 / pivot: 3 /오른쪽: 4, 9

 

결론적으로 데이터는 [ 2, 3, 4, 9 ]로 호출이 되겠죠. 

 

(2) 원리의 이해

 

사실 왼쪽과 오른쪽에 이미 인자가 있으면, 그 왼쪽 오른쪽 안에서도 다시 재정렬이 이루어져야 합니다. 

 

예시에서 두 번째 4를 비교할 때, 이미 오른쪽에 9라는 인자가 있었습니다. 그러면 알고리즘상 그냥 넣을 수 없고, 반드시 오른쪽 내 데이터에서도 또 정렬이 이루어져야 합니다. 

 

그래서 재귀함수를 통해서 왼쪽과 오른쪽에도 퀵소트 함수를 포함시켜줄 것입니다. 

 

 

3. 퀵정렬 구현하기

 

def quick_sort(data):
    
    if len(data) <= 1:
        return data
    
    
    left, right = list(), list()
    pivot = data[0]
    
    for i in range(1, len(data)):
        if data[i] > pivot: 
            right.append(data[i])
        else:
            left.append(data[i])
            
    return quick_sort(left) + [pivot] + quick_sort(right)
    
    

 

(1) 부연설명 - 재귀함수의 끝

if len(data) <= 1:

        return data

코드에 부연 설명을 하자면, 재귀함수가 있으면 항상 그 함수가 끊어질 조건이나 타이밍을 설정해야 합니다. 

퀵정렬의 개념 상 마지막까지 쪼개진 다면 더 이상 데이터를 나눌 필요가 없습니다. 그래서 데이터의 길이가 1일 때는 더 이상 나누지 말고, 이제 정렬된 것을 합쳐야 합니다. 

 

(2) 부연설명 - 왼쪽과 오른쪽에 담을 때도 정렬해서 담아야

 

    return quick_sort(left) + [pivot] + quick_sort(right)

 

왼쪽 오른쪽 데이터를 합칠 때 그냥 합치는게 아니라 quick_sort(  )를 통해서 정렬한 것을 볼 수 있습니다. 

 

여기까지가 퀵정렬이었습니다. 읽어보시고 궁금하신 점은 언제나 항상 댓글을 통해 물어봐주세요~!