[Algorithm] 퀵 정렬 - Quick Sort (Python)

📌 퀵 정렬

퀵 정렬은 다른 정렬 알고리즘에 비해 아주 준수한 수행 시간을 보이기 때문에 가장 많이 사용하는 정렬 알고리즘 중 하나이다. 병합 정렬과 마찬가지로 분할 정복과 재귀 알고리즘을 이용한다.

unstable 하며 알고리즘이 호출될 때마다 새로운 리스트를 생성하며 리턴하기 때문에 기본적으로는 not-in-place 정렬이기도 하다. 다만, 배열의 인덱스를 활용하여 주어진 배열 내에서만 원소를 이동시킨다면 효율적인 메모리 활용이 가능하기 때문에 in-place 정렬이라고 할 수 있다.

아이디어

1. 배열 내 원소 중 하나를 pivot(축)으로 설정한다.
2. 나머지 원소를 pivot과 비교하며 pivot보다 작은 경우에는 pivot의 앞쪽에, 큰 경우에는 뒤쪽에 위치시킨다.
3. pivot을 기준으로 양쪽에 위치한 각각의 리스트 내에서 위의 과정을 반복한다.

복잡도 분석

• 기본적으로는 원소의 개수만큼 새로운 리스트를 생성하기 때문에 O(N)의 공간 복잡도를 갖는다. 하지만, 주어진 배열 내에서 원소가 이동하는 in-place sorting 방식으로 구현할 경우, O(1)의 공간 복잡도를 가진 코드 구현이 가능하다.
  
  
• 퀵 정렬의 시간 복잡도는 선택된 pivot의 값에 따라 달라질 수 있다. pivot을 기준으로 동일한 수의 값들이 적절하게 분할된다면 병합 정렬과 마찬가지로 O(NlogN)의 시간 복잡도를 갖는다. 하지만, 분할된 값들이 한 쪽으로 치우치게 된다면 결국 모든 값에 대하여 비교가 필요하므로 O(N^2) 만큼의 시간이 소모된다.
• 상용 코드에서는 적절한 pivot을 채택하기 위한 다양한 전략을 활용하고 있기 때문에, 일반적으로는 O(NlogN)의 시간 복잡도를 보인다.
  
  

특징

✍

• 일반적으로 프로그래밍 언어에서 제공하는 내장 정렬 함수는 대부분 퀵 정렬을 기본으로 한다.
• 원소의 개수가 적어질수록 적절하지 못한 pivot을 선택할 가능성이 높아지므로, 원소의 개수에 따라 다른 정렬을 혼합해서 사용하는 경우가 많다.

👍 장점

• 평균 실행시간이 굉장히 빠르다.

👎 단점

• pivot을 어떻게 설정하느냐에 따라 성능 차이가 극명하게 갈린다.
• 안정성이 좋지 않다.

구현

def quick_sort(arr, first, last):
	if first >= last:
		return

	mid = partition(arr, first, last)

	quick_sort(arr, first, mid-1)
	quick_sort(arr, mid, last)

	return arr

def partition(arr, first, last):
	pivot = arr[(first + last) // 2]

	while first <= last:
		while arr[first] < pivot:
			first += 1
		
		while arr[last] > pivot:
			last -= 1
		
		if first <= last:
			arr[first], arr[last] = arr[last], arr[first]
			first, last = first + 1, last - 1
		
	return first

--

참고 사이트

🙇🏻‍♂️ https://www.daleseo.com/sort-quick/