정렬 알고리즘 중 가장 빠른것

퀵 정렬(quicksort)

 

평균적인 상황에서 최고의 성능을 나타낸다.
컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이다.
원소 하나를 기준(pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은 것, 큰 것으로 나눈 뒤
나누어진 각각의 피벗에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다. 이렇게 피벗을 잡고 이보다 작은 원소들을 왼쪽으로
보다 큰 원소들을 오른쪽으로 나누는 것을 partition step 이라 한다.