Java의 빠른 정렬 알고리즘

파티션 교환 정렬이라고도 알려진 Java의 빠른 정렬은 분할 정복 정렬 알고리즘입니다. 퀵 정렬은 분할 및 정복 특성으로 인해 CPU 캐시를 가장 잘 사용하는 알고리즘의 좋은 예입니다. Quicksort 알고리즘은 특히 큰 목록을 정렬하는 데 가장 많이 사용되는 정렬 알고리즘 중 하나이며 대부분의 프로그래밍 언어에서 이를 구현했습니다. Quicksort 알고리즘은 원본 데이터를 개별적으로 정렬한 다음 병합하여 정렬된 데이터를 생성하는 두 부분으로 나눕니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

빠른 정렬을 사용하여 {8, 6, 3, 4, 9, 2, 1, 7} 배열을 정렬해야 한다고 가정해 보겠습니다.

빠른 정렬 알고리즘 구현 단계

1. 배열에서 피벗이라는 요소를 선택합니다. 일반적으로 중간 요소가 피벗으로 선택됩니다. 4를 피벗으로 삼겠습니다.

2. 피벗보다 작은 요소가 피벗 앞에 오고 피벗보다 큰 요소가 피벗 뒤에 나타나도록 배열을 두 부분으로 다시 정렬합니다. 다음 단계를 따릅니다:

• 가장 왼쪽 요소, 즉 8을 선택합니다. 4가 피벗이고 8이 4보다 크므로 8을 4의 오른쪽으로 이동해야 합니다. 오른쪽에서는 4보다 크므로 7을 남겨두고 8과 교환하기 위해 1을 선택합니다. 따라서 교환 후 배열은 다음과 같습니다: 1,6,3,4,9,2,8,7
• 다음 왼쪽 요소(예: 6)를 선택합니다. 4가 피벗이고 6이 4보다 크므로 6을 4의 오른쪽으로 이동해야 합니다. 오른쪽에서는 4보다 크므로 7,8을 남겨두고 6과 교환하기 위해 2를 선택합니다. 따라서 교환 후 배열은 다음과 같습니다: 1,2,3,4,9,6,8,7
• 이제 피벗 왼쪽에 있는 모든 요소는 피벗보다 작고 피벗 오른쪽에 있는 모든 요소는 피벗보다 크므로 4를 피벗으로 사용하는 작업은 완료되었습니다.

3. 왼쪽 하위 배열(피벗보다 작은 요소가 있는 배열)과 오른쪽 하위 배열(피벗보다 많은 요소가 있는 배열)에 대해 1단계와 2단계를 반복적으로 적용합니다. 배열에 요소가 1개 또는 0개만 포함된 경우 배열은 분류된 것으로 간주됩니다.

빠른 정렬 알고리즘 구현 프로그램

다음은 빠른 정렬 알고리즘을 사용하여 정수 배열을 정렬하는 Java 프로그램입니다.

코드:

import java.lang.*;
import java.util.*;
public class Main {
private int array[];
private int length;
public void sort(int[] inputArrayArr) {
if (inputArrayArr == null || inputArrayArr.length == 0) {
return;
}
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
}
private void performQuickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two subarrays
while (i <= j) {
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
}
private void swapNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String args[]){
Main quickSort = new Main();
int[] inputArray = {8,6,3,4,9,2,1,7};
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
}
}

출력:

빠른 정렬 알고리즘의 장점

퀵 정렬 알고리즘의 장점은 다음과 같습니다.

• 뛰어난 참조 집약성: 참조 집약성은 프로세서가 짧은 시간 동안 동일한 메모리 위치에 반복적으로 액세스할 수 있는 능력입니다. Java의 빠른 정렬은 매우 적은 수의 캐시 누락으로 인해 우수한 참조 위치를 제공하며 이는 최신 아키텍처에서 성능에 매우 중요합니다.
• 빠른 정렬은 병렬 가능합니다. 배열을 더 작은 영역으로 분할하는 초기 단계가 완료되면 모든 개별 하위 배열을 독립적으로 병렬로 정렬할 수 있습니다. 이러한 이유로 퀵 정렬의 성능이 더 좋습니다.

퀵 정렬의 복잡성 분석

Quicksort는 분할 정복 원칙에 따라 작동하는 빠른 꼬리 재귀 알고리즘입니다. 최고, 평균, 최악의 경우에 대한 복잡성 분석은 다음과 같습니다.

• 최고 사례 복잡성: 배열이나 목록에 n개의 요소가 포함된 경우 첫 번째 실행에는 O(n)가 필요합니다. 이제 나머지 두 하위 배열을 정렬하려면 2*O(n/2)가 필요합니다. 이로써 최선의 경우 O(n logn)의 복잡도가 결정됩니다.
• 평균 사례 복잡도: 퀵 정렬의 평균 사례는 O(n log n)입니다.
• 최악의 경우 복잡성: 첫 번째 또는 마지막을 선택하면 거의 정렬되거나 거의 역으로 ​​정렬된 데이터에 대해 최악의 성능이 발생합니다. 퀵 정렬은 최악의 경우 O(n^2)를 수행합니다.

 Java에서는 배열. Sort() 메소드는 빠른 정렬 알고리즘을 사용하여 배열을 정렬합니다.

위 내용은 Java의 빠른 정렬 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!