비디오: Lec 4 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005 2024
자바에서 가장 일반적으로 사용되는 정렬 기법이 실제로 어떻게 작동하는지 살펴 보겠습니다. 이 기법은 Quicksort, 라고하며 재귀를 매우 독창적으로 사용합니다.
우리 중 대부분은 퀵 소트 (Quicksort) 작업과 같은 정렬 알고리즘이 단순히 지적인 운동 일 뿐이라는 것을 알아 냈습니다. Java API에는 이미 정렬이 내장되어 있습니다.
Quicksort 기술은 재귀를 사용하여 값 배열을 정렬합니다. 기본 단계는 다음과 같습니다.
-
배열의 값 범위 내에있는 임의의 값을 선택합니다.
이 값은 피벗 포인트 입니다. 피벗 점을 선택하는 가장 일반적인 방법은 배열에서 첫 번째 값을 선택하는 것입니다. 사람들은보다 정교한 방법으로 피벗 포인트를 선택하여 더 빠른 정렬을 할 수있는 박사 학위를 취득했습니다. 배열의 첫 번째 요소를 사용하십시오.
-
피벗 점보다 작은 모든 값이 배열의 왼쪽에 있고 피벗 점보다 크거나 같은 모든 값이 배열의 오른쪽에 있도록 배열의 값을 다시 정렬합니다. 정렬.
피벗 값 은 배열의 왼쪽과 오른쪽 사이의 경계를 나타냅니다. 아마 죽은 센터가 아니 겠지만 그건 중요하지 않습니다. 이 단계를 파티셔닝이라고하며 배열의 왼쪽과 오른쪽은 파티션입니다.
-
이제 배열의 두 섹션을 별도의 배열로 처리하고 해당 섹션에 대해 1 단계부터 다시 시작하십시오.
이것은 알고리즘의 재귀 부분입니다.
38 17 58 22 69 31 88 28 86 12
여기서 피벗 포인트는 38이며 파티셔닝 단계의 작업은 배열을 다음과 같이 다시 배열하는 것입니다. < 17 12 22 28 31 38 88 69 86 58
값이 여전히 잘못되었음을 알 수 있습니다. 그러나 배열은 값 38로 나누어 져 있습니다. 38 미만의 모든 값은 38의 왼쪽에 있고 38보다 큰 모든 값은 38의 오른쪽에 있습니다.
이제는 값 38로 두 개의 파티션으로 배열하고 각면에 대해 프로세스를 반복하십시오. 피벗 값 자체는 왼쪽 분할 영역과 함께 있으므로 왼쪽 분할 영역은 다음과 같습니다.
17 12 22 28 31 38
이번에는 분할 단계에서 17을 피벗 점으로 선택하고 다음과 같이 요소를 재정렬합니다. > 12 17 22 28 31 38
보시다시피 배열의이 부분이 지금 정렬됩니다.불행하게도 Quicksort는이 시점에서이를 인식하지 못합니다. 따라서 재귀가 좀 더 필요합니다. 하지만 이것이 기본 프로세스입니다.
