2024년 10월 30일 TIL

오늘은 퀵 정렬의 동작 방식에 대해 학습했다.

 

 

정렬되지 않은 숫자(요소)에서 pivot이라는 기준을 정하고

 

pivot 보다 왼쪽에는 작은 숫자가, 오른쪽에는 큰 숫자가 있게 만드는 방식이었다.

 

6 5 3 1 8 7 2 4

 

라는 숫자가 순서대로 존재할 때

 

ex) pivot = 3일 경우

 

pivot 보다 작은 숫자 = 1, 2가 존재하고,

pivot 보다 큰 숫자 = 4, 5, 6, 7, 8가 존재합니다.

 

그 결과,

 

6 5 3 1 8 7 2 4

에서 

 

6은 3보다 크고, 2는 3보다 작으므로 서로의 위치를 바꾸게 됩니다. 마찬가지로,

5는 3보다 크고, 1은 3보다 작으므로 위치를 바꿔 최종적으로

 

2 1 3 5 8 7 6 4

 

가 되게 숫자를 정렬해줍니다. pivot 3을 기준으로 왼쪽(작은 수들의 모임)에서 새로운 pivot을 결정해주고,

오른쪽(큰 수들의 모임)에서도 새로운 pivot을 결정해줘 다시 위와 같은 과정을 거쳐 pivot의 왼쪽에는 작은 수가 오른쪽에는 큰 수가 오게 정렬해줍니다.(재귀 함수나 반복문을 사용해야 한다)

 

그 결과 : 1 2 3 4 5 6 7 8 

 

로 숫자가 정렬될 것 입니다.

 

 

퀵 정렬을 사용하는 이유는 일반적인 정렬 방법인 버블, 삽입, 선택 정렬의 경우

 

버블 정렬 시간 복잡도 : O(n^2)

 

선택정렬 시간 복잡도 : O(n^2)

삽입 정렬 시간 복잡도 : O(n) ~O(n^2)

 

시간 복잡도가 O(n^2)이 걸리지만,

 

퀵 정렬의 시간 복잡도는

으로 위의 정렬 방법보다 빠르게 정렬을 수행할 수 있어 유용하게 사용 됩니다.