반응형 퀵 정렬1 [Java][알고리즘][정렬] Quick Sort / 퀵 정렬 퀵 정렬 가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우는 O(N^2) 이지만 실제로 수행해보면 합병 정렬보다 더 좋은 성능을 낸다. pivot을 기준으로 pivot보다 작은 원소들은 pivot의 왼쪽, 큰 원소들은 오른쪽에 위치 시켜 분할 한 후, 새롭게 pivot을 만들어 재귀적으로 정렬하는 알고리즘이다. 위 예시를 보면서 이해해보도록 하자. 일반적으로는 맨 왼쪽 원소를 pivot으로 정한다. pivot을 중간값으로 잘 정하는게 퀵 정렬에서의 성능을 좌우한다. 이를 위해 3개의 원소를 정해서 중간값을 pivot으로 하는 Median of Three나 9개의 원소를 뽑아 3개씩 나눠 각 중간값을 구하고 다시 그 3개 중에서 중간값을 정해 pivot으로 정하기도 하지만.. 맨 왼쪽으로 그냥 하도록 하자.. 2019. 6. 19. 이전 1 다음 반응형
