덕's IT Story

퀵정렬(Quick Sort)는 평균적으로 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우(Worst-Case) Θ(n^2)의 시간복잡도를 가져 Θ(nlogn)의 시간복잡도를 가지는 병합정렬, 힙정렬보다 성능이 안좋아보일 수 있으나 평균적인 성능은 어떤 정렬에도 뒤떨어지지 않는다. 퀵정렬(Quick Sort)는 배열의 한 원소를 기준(피봇, pivot)으로 삼아 피봇보다 작은 수들은 피봇의 앞으로, 피봇보다 큰 수들은 피봇의 뒤로 보낸다. 정렬되지 않은 피봇의 좌우는 재귀적으로 문제를 해결하여 배열 전체가 정렬이 되도록 한다. 예를 들어 설명하면 다음과 같다. 이 예는 배열의 젤 뒷원소를 피봇으로 삼아 퀵정렬(Quick Sort)를 수행하는 경우이다. 피봇인 15보다 작은 수들..