오늘은 퀵 정렬 알고리즘에 대해 알아보았다.
퀵 정렬 알고리즘의 아이디어는 기준(피벗)을 잡은 후 에 오름차순 정렬 기준으로 왼쪽에는 기준보다 작은 값, 오른쪽에는 기준보다 큰값을 배치 시켜 정렬시키는 것이다.
이를 토대로 코드를 구현해보자
붙여 설명하자면 맨 앞의 값을 기준점으로 잡은 후에 왼쪽에서 올라오면서 기준 보다 작은값을 탐색하고, 오른쪽에서 부터 내려오면서 기준값보다 큰 값을 탐색한다.
그리고 각각의 조건에 벗어나는 값들의 위치를 바꾼다. 이 동작을 각각 왼쪽, 오른쪽에서 내려오는 인덱스 값이 엇갈릴때 까지 진행한다.
엇갈리면 그지점의 값과 기준값의 위치(맨 처음)를 바꾼후에 그 바꾼 위치의 오른쪽 왼쪽 각각에 다시 똑같이 실행을 시킨다.
이 알고리즘에 시간복잡도는 반으로 쪼개서 왼쪽과 오른쪽에 각 각 실행 하므로 N에 logN을 곱한 값과 같다.
여기서 logN의 밑은 2이다. 이를 곱하는 이유는 반으로 쪼개서 내려오기 때문에 그 모양이 이진트리와 같다.
따라서 이진트리의 높이는 logN 그리고 각각의 층의 개수는 N으로 동일하기 때문에 시간복잡도는 NlogN이다.
하지만 최악의 경우 : 오름차순으로 정렬해야하는데 정렬해야 하는 배열이 내림차순으로 되어있을 경우에는 계속 끝까지 돌아야 함으로 N^2 이라고 할 수 있다.