Java에서 Quicksort 알고리즘 구현

1. 개요

이 자습서에서는 Java 구현에 중점을두고 QuickSort 알고리즘을 자세히 살펴 봅니다.

또한 장단점에 대해 논의한 다음 시간 복잡성을 분석 할 것입니다.

2. QuickSort 알고리즘

Quicksort는 분할 및 정복 원칙을 활용하는 정렬 알고리즘입니다. 평균 O (n log n) 복잡도를 가지며 특히 빅 데이터 볼륨에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다.

Quicksort는 안정적인 알고리즘이 아니라는 점을 기억하는 것이 중요합니다. 안정적인 정렬 알고리즘은 동일한 값을 가진 요소가 정렬 된 출력에서 ​​입력 목록에 나타나는 것과 동일한 순서로 나타나는 알고리즘입니다.

입력 목록은 피벗이라는 요소에 의해 두 개의 하위 목록으로 나뉩니다. 피벗보다 작은 요소가있는 하위 목록과 피벗보다 큰 요소가있는 다른 하위 목록. 이 프로세스는 각 하위 목록에 대해 반복됩니다.

마지막으로, 정렬 된 모든 하위 목록이 병합되어 최종 출력을 형성합니다.

2.1. 알고리즘 단계

  1. 목록에서 피벗이라는 요소를 선택합니다. 목록을 두 개의 하위 목록으로 나누는 데 사용합니다.
  2. 피벗 주위의 모든 요소를 ​​재정렬합니다. 값이 작은 요소는 그 앞에 배치되고 그 뒤에있는 피벗보다 큰 요소는 모두 배치됩니다. 이 단계 후에 피벗은 최종 위치에 있습니다. 이것은 중요한 파티션 단계입니다.
  3. 위의 단계를 피벗의 왼쪽과 오른쪽에있는 두 하위 목록에 반복적으로 적용합니다.

보시다시피 quicksort는 모든 분할 및 정복 접근 방식과 마찬가지로 당연히 재귀 알고리즘입니다.

이 알고리즘을 더 잘 이해하기 위해 간단한 예를 들어 보겠습니다.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. 단순화를 위해 피벗으로 5를 선택한다고 가정 해 보겠습니다.
  2. 먼저 배열의 첫 번째 위치에 5 미만의 모든 요소를 ​​배치합니다 : {3, 4, 5, 6, 5, 9}
  3. 그런 다음 왼쪽 하위 배열 {3,4}에 대해 반복하여 3을 피벗으로 사용합니다.
  4. 3 개 미만의 요소가 없습니다.
  5. 피벗 오른쪽에있는 하위 배열 (예 : {4})에 빠른 정렬을 적용합니다.
  6. 이 하위 배열은 하나의 정렬 된 요소로만 구성됩니다.
  7. 최종 정렬 된 어레이를 얻을 때까지 원래 어레이의 오른쪽 부분 인 {6, 5, 9}을 계속합니다.

2.2. 최적의 피벗 선택

QuickSort의 중요한 점은 최상의 피벗을 선택하는 것입니다. 물론 중간 요소는 목록을 두 개의 동일한 하위 목록으로 나누기 때문에 가장 좋습니다.

그러나 정렬되지 않은 목록에서 중간 요소를 찾는 것은 어렵고 시간이 많이 걸리기 때문에 첫 번째 요소, 마지막 요소, 중간 값 또는 기타 임의 요소를 피벗으로 사용합니다.

3. 자바 구현

첫 번째 메소드는 정렬 할 배열, 첫 번째 및 마지막 인덱스를 매개 변수로 취하는 quickSort () 입니다. 먼저 인덱스를 확인하고 정렬 할 요소가 아직있는 경우에만 계속합니다.

정렬 된 피벗의 인덱스를 가져 와서 quickSort () 메서드 와 동일한 매개 변수를 사용 하지만 다른 인덱스를 사용하여 partition () 메서드 를 재귀 적으로 호출하는 데 사용합니다 .

public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }

partition () 메서드를 계속해 보겠습니다 . 단순화를 위해이 함수는 마지막 요소를 피벗으로 사용합니다. 그런 다음 각 요소를 확인하고 값이 더 작은 경우 피벗 전에 교체합니다.

분할이 끝나면 피벗보다 작은 모든 요소가 왼쪽에 있고 피벗보다 큰 모든 요소가 오른쪽에 있습니다. 피벗은 최종 정렬 위치에 있으며 함수는 다음 위치를 반환합니다.

private int partition(int arr[], int begin, int end) { int pivot = arr[end]; int i = (begin-1); for (int j = begin; j < end; j++) { if (arr[j] <= pivot) { i++; int swapTemp = arr[i]; arr[i] = arr[j]; arr[j] = swapTemp; } } int swapTemp = arr[i+1]; arr[i+1] = arr[end]; arr[end] = swapTemp; return i+1; }

4. 알고리즘 분석

4.1. 시간 복잡성

최상의 경우 알고리즘은 목록을 두 개의 동일한 크기의 하위 목록으로 나눕니다. 따라서 전체 n 크기 목록 의 첫 번째 반복에는 O (n)이 필요합니다 . n / 2 요소를 사용하여 나머지 두 개의 하위 목록을 정렬하려면 각각 2 * O (n / 2)가 필요 합니다. 결과적으로 QuickSort 알고리즘은 O (n log n) 의 복잡성을 갖습니다 .

최악의 경우 알고리즘은 각 반복에서 하나의 요소 만 선택하므로 O (n) + O (n-1) +… + O (1) , 이는 O (n2)와 같습니다 .

평균적으로 QuickSort는 복잡성 이 O (n log n) 이므로 빅 데이터 볼륨에 적합합니다.

4.2. QuickSort 대 MergeSort

MergeSort보다 QuickSort를 선택해야하는 경우에 대해 논의하겠습니다.

Quicksort와 Mergesort는 모두 평균 시간 복잡도가 O (n log n) 이지만, Quicksort는 O (log (n)) 공간 복잡도 가 있으므로 선호되는 알고리즘 입니다. 반면 Mergesort에는 O (n) 추가 스토리지가 필요하므로 어레이 비용이 상당히 많이 듭니다.

Quicksort는 작업을 위해 다른 인덱스에 액세스해야하지만 연속 블록이 없기 때문에이 액세스는 연결된 목록에서 직접 가능하지 않습니다. 따라서 요소에 액세스하려면 연결 목록의 처음부터 각 노드를 반복해야합니다. 또한 Mergesort는 LinkedList에 대한 추가 공간없이 구현됩니다 .

이러한 경우 일반적으로 Quicksort 및 Mergesort에 대한 오버 헤드 증가가 선호됩니다.

5. 결론

Quicksort는 대부분의 경우에 매우 유용한 우아한 정렬 알고리즘입니다.

일반적으로 평균 시간 복잡도가 O (n log n) 인 "in-place"알고리즘 입니다.

언급해야 할 또 다른 흥미로운 점은 Java의 Arrays.sort () 메서드가 기본 배열을 정렬하기 위해 Quicksort를 사용 한다는 것 입니다. 구현은 두 개의 피벗을 사용하고 간단한 솔루션보다 훨씬 더 나은 성능을 제공하므로 프로덕션 코드의 경우 일반적으로 라이브러리 메서드를 사용하는 것이 좋습니다.

항상 그렇듯이이 알고리즘의 구현 코드는 GitHub 저장소에서 찾을 수 있습니다.