🍀 Knowledge/알고리즘
[알고리즘] 정렬(퀵 소트) 알고리즘 (2)
잘쓰면 정말 효율적인 퀵 소트 퀵소트의 시간 복잡도는 O(nlogn)이다. 또한 퀵 소트에 대해 제대로 이해만 한다면, 더욱더 빠르게 답을 구하는 것도 가능하다. 퀵 소트의 전반적인 과정에 대해 이해해보자. 1. 피벗을 하나 선택한다. 이 때, 피벗의 부분 배열의 가장 왼쪽을 선택하냐, 중간을 선택하냐, 제일 오른쪽을 선택하냐에 따라서 효율이 다를 수 있다. 2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값과 작은 값을 찾는다. 헷갈린다면, 정렬이라고 생각해보자. 왼쪽에는 작은 값들부터 오른쪽에는 큰 값까지 있어야 한다. 그럴려면, 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾아 바꾸어 줄 필요가 있다. 3. 양쪽에서 찾은 값을 서로 바꾸어 준다. 4. 왼쪽과 오른쪽에서 탐색..
