23강 퀵 정렬

작은 데이터의 위치를 서로

정열 알고리즘중 하나라고 볼수 있구요

모두 퀵정렬 혹은 병합정렬의

알고리즘을 사용하고 있는데요

그 퀵정렬의 대해서

퀵정렬은 정렬을 수행하는 과정에서 기준데이터 즉 피벗값을

퀵정렬은

피벗으로 설정해서 정렬을 수행하는데요

현재 피벗의 값은 5입니다

작은 데이터를 고릅니다 그래서 이와같이

큰 값인 7

이 5보다 작은 값인 4가

9와 2가 선택됩니다

이 9와 2또한 서로 위치를 바꿔줍니다 그럼 이처럼 다시한번 이어서

이 왼쪽에서부터 찾아서 6을 고를수 있구요

이 1을 고를수있습니다

다만 이때는

위치가 서로 엇갈렸을때는

이 피벗값을 왼쪽에

다시한번 퀵정렬을 수행해주고

오른쪽에 데이터데 대해서도 마찬가지로 퀵정렬을 수행해 줍니다

퀵정렬이 수행되는 과정은 재귀적으로 수행되구요 수행될때마다

정열을 수행하게 되면

오른쪽에서 부터는 피벗보다 작은걸

서로 바꾸어 주는 방식으로 동작하겠죠

이렇게 오른쪽 데이터 묶음에 대해서도 마찬가지로 다시 이렇게 퀵정렬이 수행 되는걸 확인할 수 있습니다

퀵정렬은 왜 빠르게

생각해 볼수 있습니다

한번 파티션

절반에 가깝게 분할 시킬수 있다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있습니다

피벗값을 분할을 이루어진다고 봐야겠지만

데이터를 절반씩 묶어서

데이터의 범위가 절반씩

전체의 높이를 확인했을때 log N이라고 볼수 있습니다

밑이 2인 log N이라고 표현 할수가 있겠네요

데이터의 개수는 N이고

NlogN 에 비례하는 만큼 발생할 것을 기대할수 있습니다

퀵 정렬의 시간복잡도에

NlogN 시간 복잡도

증명 과정은 생략했습니다

담음은 퀵정렬의 특징이라고 한다면 최악의 경우 N제곱의 시간복잡도를 가질수 있음

즉 분할이 한쪽으로 편향될 경우 n제곱의 시간복잡도를 가지게 됨

평균적으로는 NlogN 시간 복잡도임

피벗으로

어떻게 될까요?

퀵 솔트를 수행하게 되면 이 첫번째 원소인 0을

다시 이 1을 피벗값으로 설정해서 퀵정렬을 수행하게되고

정리

최악의 경우 분할이 수행되는 횟수가 N과 비례하고

분할을 하기위해서 매번 선형탐생을 수행해야해서 전체 시간복잡도가 N 제곱이 되는 것임

선형탐색을 수행해야 되기 때문에

퀵정렬은 이렇게 단순하게 구현을 했을때

NlogN을 보장 할수 있는

피벗으로

퀵정렬을 n제곱이 나올수 있다느점 감안해 주시고요

NlogN 을 항상 보장한다는 점까지

정리

다양한 프로그래밍 언어에서 표준 정렬 라이브러리를 제공할때 이 퀵정렬 기반으로 라이브러리가 작성 되어 있으면 최악의 경우에도 NlogN을 보장 할수 있는 형태로 구현 가능함

자 그래서 이러한 퀵정렬을 파이썬으로 구현한건 다음과 같습니다

현재 정렬을 위한 데이터의 범위의 오직 하나의 데이터만 포함되어 있다면

즉 원소가 1개의 경우에는 종료할 수 있도록 만들어 주고요

정렬하고자 하는 데이터가

피벗 값으로 설정합니다

첫번째 원소를 제외하고 오른쪽 원소중에서

가장 오른쪽을 right로 설정하는걸 확인할 수 있습니다

가리키고 있는 그 인덱스 보다 이 right 가리키고 있는

즉 left는 항상 오른쪽으로 가고 right은 항상 왼쪽으로 가기때문에

이과정 자체를 선형 탐색이라고 볼 수 있겠죠

left 와 right 값을 확인해서

이후에는 이 right변수가 가리키는

때문에 이 array[right]과 array[pivot]의 위치를서로 바꿔주면 됩니다

작은데이터와 큰데이터의 위치를

정렬을 수행해서 퀵솔트를

균형있게 분할이 이루어져서

수 있습니다

퀵 쏠트

레프트 롸이트 값을

이어서 롸이트은 오른쪽에서

재귀적으로 호출 하는걸

로 설정한 뒤에

피벗보다 큰데이터

피벗의 위치를

데이터와 큰데이터의 위치를 바꿔주는걸 확인할 수 있습니다

호출 하는 것을

퀵정렬을

리스트 슬라이싱 과 리스트 컴프레션

퀵정렬의 로직을 활용해서

원소로

피벗을 제외한

피벗보다 값이 큰 이 오른쪽 위치에

퀵정렬을 수행한

수행한

이 전체 리스트는

분할을