알고리즘 퀵 정렬(quick sort)란? 파이썬으로 구현까지

퀵 정렬(quick sort)에 대해서 많이 들어보셨을 겁니다.

정렬에는 삽입 정렬(insertion sort), 선택 정렬(selection sort) 등이 있는데요. 퀵 정렬은 이러한 정렬 알고리즘보다

훨씬 빠른 속도로 정렬을 해주는 알고리즘입니다.

퀵 정렬은 분할 정복(divide and conquer) 방법을 사용하는 알고리즘 중 하나입니다

 

분할 정복

문제를 작은 2개로 분리하고 각각 해결한 다음 이를 합쳐서 원래의 문제를 해결하는 방법입니다.

보통 재귀 호출 등으로 사용하게 됩니다

 

퀵 정렬 과정

퀵 정렬을 위와 같은 과정을 통해 정렬이 진행됩니다.

1. 리스트 안에 한 요소를 선택합니다. 이를 pivot(피벗)이라고 합니다.

2. pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분리시킵니다.

3. 작은 값 중에서 또 다른 pivot을 구하고, 큰 값 중에서 또 다른 pivot을 구합니다.

4. 각각에서 또 pivot을 기준으로 작은 값은 왼쪽, 큰 값을 오른쪽으로 진행합니다.

5. 이 과정을 반복해서 list의 변동이 없으면 정렬이 끝납니다.

 

이 과정이 divide and conquer 과정입니다. pivot을 기준으로 각각 문제를 해결하고 취합하면

문제가 해결되죠. 즉, 여기서 문제는 정렬이므로 정렬이 해결되는 것입니다

 

그럼 이것을 어떻게 구현할까요?

간단하게 python을 활용해서 구현해보죠!

파이썬 코드는 아래와 같습니다

정말 심플합니다.

def quick_sort 함수를 만듭니다. 그리고 인자로 list를 입력받습니다.

만약, list의 길이가 1보다 작거나 같으면 list를 return 시켜줍니다

그리고 피벗은 임의로 가운데 값으로 합니다.

반복문을 돌면서 pivot 기준 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시켜줍니다. 만약 숫자가 같다면 같은 배열에 넣어주고요!

이제 divde 해야겠죠. quick_sort 함수를 다시 호출하면서 작은 값들의 리스트를 넘겨줍니다.

그리고 큰 값들의 리스트도 마찬가지구요!

최종적으로 이 배열들이 합쳐져서 나오게 됩니다