[Algorithm] 퀵 정렬(quick sort)
퀵 정렬- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 동작- 호어 분할 방식 -> 리스트에서 첫번째 데이터를 pivot(기준)으로 정한다. -> 왼쪽에서부터 피벗보다 큰 데이터를, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. -> 큰 데이터와 작은 데이터의 위치를 서로 교환- 분할된 두 개의 배열에 대해 재귀적으로 이 과정을 반복- 한번 진행될 때마다 최소한 하나의 피벗은 최종적으로 위치가 정해진다- 퀵 정렬의 시간복잡도 : O(NlogN) -> 삽입 정렬과 달리 데이터가 거의 정렬되어 있는 최악의 경우 시간복잡도가 O(N^2) 이다예시array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]def quick_sort(array,..
2024. 4. 4.
