quicksort java algorithm
이 자습서에서는 Java의 Quicksort 알고리즘, 그 그림, 코드 예제의 도움으로 Java의 QuickSort 구현에 대해 설명합니다.
Quicksort 정렬 기술은 소프트웨어 응용 프로그램에서 널리 사용됩니다. Quicksort는 병합 정렬과 같은 분할 및 정복 전략을 사용합니다.
Quicksort 알고리즘에서는 'pivot'이라는 특수 요소가 먼저 선택되고 문제의 배열 또는 목록이 두 개의 하위 집합으로 분할됩니다. 분할 된 서브 세트는 크기가 같을 수도 있고 같지 않을 수도 있습니다.
분할은 피벗 요소보다 작은 모든 요소가 피벗의 왼쪽을 향하고 피벗보다 큰 요소가 피벗의 오른쪽에 있도록 구성됩니다. Quicksort 루틴은 두 개의 하위 목록을 재귀 적으로 정렬합니다. Quicksort는 더 큰 배열이나 목록의 경우에도 효율적으로 작동합니다.
학습 내용 :
Quicksort 파티션 Java
파티셔닝은 Quicksort 기술의 핵심 프로세스입니다. 그렇다면 분할이란 무엇입니까?
배열 A가 주어지면 x보다 작은 모든 요소가 x 이전에 있고 x보다 큰 모든 요소가 x 이후에 있도록 pivot라는 값 x를 선택합니다.
피벗 값은 다음 중 하나 일 수 있습니다.
- 배열의 첫 번째 요소
- 배열의 마지막 요소
- 배열의 중간 요소
- 배열의 임의의 요소
이 피벗 값은 배열을 분할하여 배열의 적절한 위치에 배치됩니다. 따라서 '파티셔닝'프로세스의 출력은 적절한 위치의 피벗 값과 왼쪽에서 피벗보다 작은 요소와 오른쪽에서 피벗보다 큰 요소입니다.
파티셔닝 프로세스를 설명하는 다음 다이어그램을 고려하십시오.
위의 다이어그램은 배열의 마지막 요소를 피벗으로 반복적으로 선택하여 배열을 분할하는 프로세스를 보여줍니다. 각 레벨에서 피벗을 올바른 위치에 배치하여 배열을 두 개의 하위 배열로 분할합니다.
다음으로 파티션 루틴을 포함하는 퀵 정렬 기법에 대한 알고리즘과 의사 코드를 나열합니다.
Quicksort 알고리즘 자바
빠른 정렬에 대한 일반적인 알고리즘은 다음과 같습니다.
quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low 다음은 퀵 정렬 기법에 대한 의사 코드입니다.
빠른 정렬을위한 의사 코드
다음은 빠른 정렬 정렬 기술을위한 의사 코드입니다. Quicksort 및 파티셔닝 루틴을위한 의사 코드를 제공했습니다.
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low 삽화
Quicksort 알고리즘의 그림을 보겠습니다. 다음 배열을 예로 들어 보겠습니다. 여기에서 마지막 요소를 피벗으로 선택했습니다.
그림과 같이 첫 번째 요소는 낮음으로 레이블이 지정되고 마지막 요소는 높음으로 표시됩니다.
위의 그림에서 알 수 있듯이 배열의 마지막 요소와 첫 번째 요소를 각각 가리키는 high와 low의 두 개의 포인터가 있습니다. 퀵 정렬이 진행됨에 따라이 두 포인터가 모두 이동합니다.
낮은 포인터가 가리키는 요소가 피벗 요소보다 커지고 높은 포인터가 가리키는 요소가 피벗 요소보다 작을 때, 우리는 낮은 포인터와 높은 포인터가 가리키는 요소를 교환하고 각 포인터는 1 위치만큼 전진합니다.
위의 단계는 두 포인터가 배열에서 서로 교차 할 때까지 수행됩니다. 교차하면 피벗 요소가 배열에서 적절한 위치를 얻습니다. 이 시점에서 배열이 분할되고 이제 각 하위 배열에 빠른 정렬 알고리즘을 재귀 적으로 적용하여 각 하위 배열을 독립적으로 정렬 할 수 있습니다.
Java에서 Quicksort 구현
QuickSort 기술은 재귀 또는 반복을 사용하여 Java로 구현할 수 있습니다. 이 섹션에서는이 두 가지 기술을 모두 살펴 보겠습니다.
재귀 빠른 정렬
위에서 설명한 퀵 정렬의 기본 기술은 배열 정렬을 위해 재귀를 사용한다는 것을 알고 있습니다. 배열을 분할 한 후 재귀 적 퀵 정렬에서 퀵 정렬 루틴은 하위 배열을 정렬하기 위해 재귀 적으로 호출됩니다.
아래 구현은 재귀를 사용하는 빠른 정렬 기술을 보여줍니다.
import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j 산출:
원래 배열 : (4, -1, 6, 8, 0, 5, -3)
정렬 된 배열 : (-3, -1, 0, 4, 5, 6, 8)
반복적 빠른 정렬
반복적 인 퀵 정렬에서는 재귀 및 정렬 파티션을 사용하는 대신 보조 스택을 사용하여 중간 매개 변수를 배치합니다.
다음 Java 프로그램은 반복적 인 빠른 정렬을 구현합니다.
import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1 산출:
원래 배열 : (3, 2, 6, -1, 9, 1, -6, 10, 5)
정렬 된 배열 : (-6, -1, 1, 2, 3, 6, 9, 10, 5)
자주 묻는 질문
Q # 1) Quicksort는 어떻게 작동합니까?
대답: Quicksort는 분할을 사용하고 전략을 정복합니다. Quicksort는 먼저 선택한 피벗 요소를 중심으로 배열을 분할하고 재귀 적으로 정렬되는 하위 배열을 생성합니다.
Q # 2) Quicksort의 시간 복잡성은 무엇입니까?
대답: 평균 빠른 정렬의 시간 복잡도는 O (nlogn)입니다. 최악의 경우 선택 정렬과 동일한 O (n ^ 2)입니다.
Q # 3) Quicksort는 어디에 사용됩니까?
대답: Quicksort는 주로 재귀 애플리케이션에서 사용됩니다. Quicksort는 C 라이브러리의 일부입니다. 또한 기본 제공 정렬을 사용하는 거의 프로그래밍 언어는 빠른 정렬을 구현합니다.
Q # 4) Quicksort의 장점은 무엇입니까?
대답:
- Quicksort는 효율적인 알고리즘이며 방대한 요소 목록도 쉽게 정렬 할 수 있습니다.
- 내부 정렬이므로 추가 공간이나 메모리가 필요하지 않습니다.
- 널리 사용되며 모든 길이의 데이터 세트를 정렬하는 효율적인 방법을 제공합니다.
Q # 5) Quicksort가 병합 정렬보다 나은 이유는 무엇입니까?
대답: 퀵 정렬이 병합 정렬보다 나은 주된 이유는 퀵 정렬이 내부 정렬 방법이며 추가 메모리 공간이 필요하지 않기 때문입니다. 병합 정렬에는 중간 정렬을위한 추가 메모리가 필요합니다.
결론
Quicksort는 주로 O (nlogn) 시간에 방대한 데이터 세트를 정렬하는 효율성 때문에 최상의 정렬 알고리즘으로 간주됩니다.
Quicksort는 또한 내부 정렬이며 추가 메모리 공간이 필요하지 않습니다. 이 튜토리얼에서 우리는 quicksort의 재귀적이고 반복적 인 구현을 보았습니다.
예를 들어 유닉스에서 잘라 내기 명령
다가오는 자습서에서는 Java의 정렬 방법을 계속 진행합니다.
=> 여기에서 Java Beginners Guide를 살펴보십시오.
추천 도서
