문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류:정렬]] [[파일:Quick Sort.gif|섬네일|가운데]] == 개요 == 퀵 소트란 나열된 수에서 적당한 값(축)을 기준으로 이보다 작거나 같은 값을 왼쪽에, 크거나 같은 값을 오른쪽에 오도록 재배열하는 것이다. 이렇게 만들어진 왼쪽, 오른쪽 부분수열에 대해 같은 과정을 반복하면 퀵정렬이 완성된다. [[합병 정렬]]은 부분수열이 항상 같은 크기로 선정되지만, 퀵 소트는 그렇지 않다. == 알고리즘 == #피벗을 적당히 구한다. #피벗의 오른쪽에는 피벗보다 큰 값을, 왼쪽에는 피벗과 같거나 작은 값을 넣는다. #오른쪽 원쪽 부분수열의 길이가 1 또는 0 이 될따까지 위 작업을 반복한다. 이떄 피벗의 오른쪽에 피벗보다 큰 값을 넣고 왼쪽에는 피벗과 작은 값을 넣는 알고리즘은 다음과 같다. #오른쪽으로 검사하면서 축보다 크거나 같은 값이 있는 위치(i)를 찾는다. #왼쪽으로 검사하면서 축보다 작거나 같은 값이 있는 위치(j)를 찾는다. #i >= j 이면 찾기를 종료하고 왼쪽 끝 항과 j항을 교환한다. 교환후 다음 피벗을 구하려 간다. #i항과 j항을 교환한다. 교환후 2로 다시 돌아간다. == 시간 복잡도 == === 최악의 경우 === 피벗이 극단적인 값을 대표하는 경우 깊이 n 에 비교 n 모두 곱하여 n^2 이다. === 평균의 경우 === 깊이 logN 비교 N 곱하여 NlogN 이다. 이때 퀵 소트는 평균적인 경우 [[합병 정렬]]보다도 빠르게 정렬한다고 알려져 있다. == 최적화 == # 축 선택을 중앙값으로 한다. # 부분수열의 길이가 특정 길이보다 짧아지면, 삽입법을 이용한다. # 재귀 호출을 제거하고 반복 형태로 프로그램을 변경한다. Quick sort 문서로 돌아갑니다.