Java의 빠른 정렬-java지도 시간-php.cn

Java의 빠른 정렬

王林

풀어 주다： 2024-08-30 15:32:02

원래의

915명이 탐색했습니다.

다음 문서인 Java의 빠른 정렬에서는 Java의 빠른 정렬 알고리즘에 대한 개요를 제공합니다. Quick Sort 알고리즘은 병합 정렬 알고리즘과 유사하고 효율적인 정렬 알고리즘 중 하나입니다. 이는 실시간 정렬 목적으로 널리 사용되는 알고리즘 중 하나입니다. 이 알고리즘의 최악의 시간 복잡도는 O(n^2), 평균의 시간 복잡도는 O(n log n), 최선의 시간 복잡도는 O(n log n)입니다.

O(n log n)인 경우 공간 복잡도입니다. 여기서 n은 입력 크기입니다. 정렬 프로세스에는 입력 분할, 재귀 반복 및 각 재귀에 대한 중추 요소 표시가 포함됩니다. 이 알고리즘의 정렬 유형에는 반복적인 방식으로 인접한 요소를 비교하는 작업이 포함됩니다.

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

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

Java에서 빠른 정렬은 어떻게 작동하나요?

빠른 정렬 알고리즘은 효율적으로 설계되고 따르는 일련의 단계로 의사 코드를 형성하여 Java에서 구현할 수 있습니다.

퀵 정렬 알고리즘이 작동하는 주요 원리는 분할 정복 접근 방식을 기반으로 하며 효율적인 정렬 알고리즘이기도 합니다.
입력 배열은 하위 배열로 나누어지며, 중심 요소인 피벗 요소를 기준으로 나누어집니다. 피벗 요소 양쪽에 있는 하위 배열은 실제로 정렬이 발생하는 주요 영역입니다.
중앙 피벗 요소는 배열을 두 개의 파티션으로 나누는 기준이 되며, 배열 요소의 왼쪽 절반은 피벗 요소보다 작고, 오른쪽 절반은 피벗 요소보다 큽니다.
피벗 요소를 고려하기 전에는 배열 요소 중 어느 것이든 될 수 있습니다. 이는 일반적으로 이해의 편의를 위해 중간 또는 첫 번째 또는 마지막으로 간주됩니다. 피벗 요소는 배열 요소 중 임의의 요소일 수 있습니다.
이 예에서는 배열의 마지막 요소가 피벗 요소로 간주되며, 여기서 하위 배열의 분할은 배열의 오른쪽 끝에서 시작됩니다.
마지막으로 피벗 요소는 정렬 프로세스가 완료된 후 실제 정렬 위치에 있게 됩니다. 여기서 정렬의 주요 프로세스는 정렬 알고리즘의 파티션 논리에 있습니다.
알고리즘의 효율성은 하위 배열의 크기와 균형 방식에 따라 달라집니다. 하위 배열의 불균형이 심할수록 시간 복잡도가 높아져 최악의 복잡도가 발생합니다.
특정 시작, 끝 또는 중간 인덱스를 피벗 요소로 선택하는 대신 무작위 방식으로 피벗 요소를 선택하면 대부분의 경우 최고의 시간 복잡도가 발생합니다.

Java에서 빠른 정렬을 구현하는 예

QuickSort 알고리즘은 아래와 같이 Java 프로그래밍 언어를 사용하여 구현되었으며, 코드 아래에 출력 코드가 표시되어 있습니다.

코드는 처음에 배열, 초기 인덱스 및 최종 인덱스, 즉 배열 길이를 인수로 사용하여 QuickSortAlgo() 메서드를 사용하여 입력을 받습니다.
quickSortAlgo() 메서드를 호출한 후 초기 인덱스가 최종 인덱스보다 작은지 확인한 후 arrayPartition() 메서드를 호출하여 피벗 요소 값을 가져옵니다.
파티션 요소에는 피벗 요소를 중심으로 요소 값을 기준으로 작은 요소와 큰 요소를 배열하는 논리가 포함되어 있습니다.
파티션 메서드 실행 후 피벗 요소 인덱스를 가져온 후 모든 하위 배열이 분할되고 완전히 정렬될 때까지 QuickSortAlgo() 메서드가 자체적으로 반복적으로 호출됩니다.
파티션 로직에서 마지막 요소는 피벗 요소로 할당되고 첫 번째 요소는 피벗 요소와 비교됩니다. 즉, 마지막 요소는 요소가 더 작은지 더 큰지에 따라 교체됩니다.
이 재귀 프로세스는 배열의 모든 요소가 분할되고 정렬될 때까지 발생하며 최종 결과는 결합된 정렬 배열입니다.
요소가 피벗 요소보다 작거나 같은 경우에만 for 루프 반복 내에서 요소가 교체됩니다.
반복 프로세스가 완료되면 마지막 요소가 교체됩니다. 즉, 피벗 요소 값이 왼쪽으로 이동하여 새 파티션이 만들어지고 동일한 프로세스가 재귀 형식으로 반복되어 일련의 결과가 발생합니다. 주어진 배열 요소로부터 하위 배열을 형성하여 다양한 가능한 파티션에 대한 작업을 정렬합니다.
아래 코드는 모든 IDE에서 실행 가능하며, main()에서 배열 값을 변경하여 출력을 확인할 수 있습니다. main 메소드는 콘솔에 출력을 가져오는 목적으로만 사용됩니다. 자바 코딩 표준의 일부로 아래에서 메인 메소드를 제거하고 객체를 생성할 수 있으며, 아래 메소드를 비정적으로 만들어 호출할 수 있다.

Java에서 빠른 정렬 알고리즘의 코드 구현

다음은 코드 구현입니다.

코드:

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm {
public static void main(String[] args) {
int[] array = { 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 };
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) {
System.out.print(ar + " ");
}
}
public static int arrayPartition(int[] array, int start, int end) {
int pivot = array[end];
int i = (start - 1);
for (int ele = start; ele < end; ele++) {
if (array[ele] <= pivot) {
i++;
int swap = array[i];
array[i] = array[ele];
array[ele] = swap;
}
}
// Swapping the elements
int swap = array[i + 1];
array[i + 1] = array[end];
array[end] = swap;
return i + 1;
}
public static void quickSortAlgo(int[] arrayTobeSorted, int start, int end) {
if (start < end) {
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
}
}
}

로그인 후 복사

출력:

Java의 빠른 정렬