유사하다 병합 정렬 알고리즘 중 Quick Sort 알고리즘은 Divide and Conquer 알고리즘입니다. 처음에는 요소를 피벗 요소로 선택하고 선택한 피벗 주위에 지정된 배열을 분할합니다. 서로 다른 방식으로 피벗을 선택하는 다양한 버전의 QuickSort가 있습니다.
- 항상 첫 번째 요소를 피벗으로 선택하세요(아래 구현됨).
- 항상 마지막 요소를 피벗으로 선택하세요.
- 임의의 요소를 피벗으로 선택합니다.
- 중앙값을 피벗으로 선택합니다.
QuickSort의 핵심 프로세스는 partition() 프로세스입니다. partition() 함수의 목적은 배열과 배열의 요소 x를 피벗으로 수신하고 x를 정렬된 배열의 올바른 위치에 놓은 다음 모든 작은 요소(x보다 작은)를 x 앞에 놓고 다음을 넣는 것입니다. x 이후의 모든 더 큰 요소(x보다 큼). 이 모든 작업은 선형 시간, 즉 Big O(n)으로 수행되어야 합니다.
재귀 QuickSort 기능을 위한 의사 코드:
/* low -->시작 인덱스, high --> 끝 인덱스 */ QuickSort(arr[], low, high) { if (low 방법-1 : CPP // 빠른 정렬 알고리즘의 C++ 구현. #include using 네임스페이스 std; int partition(int arr[], int start, int end) { int 피벗 = arr[start]; int count = 0 for (int i = start + 1; i<= end; i++) { if (arr[i] <= pivot) count++; } // Giving pivot element its correct position int pivotIndex = start + count; swap(arr[pivotIndex], arr[start]); // Sorting left and right parts of the pivot element int i = start, j = end; while (i pivotIndex) { while (arr[i] <= pivot) { i++; } while (arr[j]>피벗) { j--; } if (iivotIndex) { swap(arr[i++], arr[j--]); } } 피벗 인덱스를 반환합니다; } void QuickSort(int arr[], int start, int end) { // 기본 사례 if (start>= end) return; // 배열 분할 int p = partition(arr, start, end); // 왼쪽 부분 정렬하기 QuickSort(arr, start, p - 1); // 오른쪽 부분 정렬하기 QuickSort(arr, p + 1, end); } int main() { int arr[] = { 9, 3, 4, 2, 1, 8 }; int n = 6; QuickSort(arr, 0, n - 1); for (int i = 0; 나는 계산합니다<< arr[i] << ' '; } return 0; } Output 1 2 3 4 8 9 Method-2 : This method’s space complexity is O(n). As we will take an extra array in partition function like in merge function of merge sort . Algorithm explanation and steps of partition function: Make a new array of size equal to given array. push all the smaller elements than pivotElement to the new array. Push pivotElement to new array now. finally, push all the greater elements than pivotElement to the new array. Now, copy the new array to the original array. Store the index of the pivotElement from the original array. Return this index. After this, all the elements in the original array are in the order : smaller than pivotElement ->ivotElement ->ivotElement보다 큽니다. 시간 복잡도: θ(nlogn). 공간 복잡도 : O(n). C++ // Manish Sharma가 추가함 #include using 네임스페이스 std; int partition(int* arr, int start, int end) { // 마지막 요소를ivotElement로 가정 int index = 0,ivotElement = arr[end],ivovIndex; int* temp = new int[end - start + 1]; // 현재 파티션 범위와 크기가 같은 배열 만들기... for (int i = start; i<= end; i++) // pushing all the elements in temp which are smaller than pivotElement { if(arr[i] { temp[index] = arr[i]; index++; } } temp[index] = pivotElement; // pushing pivotElement in temp index++; for (int i = start; i // pushing all the elements in temp which are greater than pivotElement { if(arr[i]>피봇엘리먼트) { 임시[인덱스] = arr[i]; 인덱스++; } } // 현재 임시 배열의 모든 요소는 순서가 있습니다. // 가장 왼쪽 요소는ivovElement보다 작고 가장 오른쪽 요소는ivotElement보다 큽니다. index = 0; for (int i = 시작; i<= end; i++) // copying all the elements to original array i.e arr { if(arr[i] == pivotElement) { // for getting pivot index in the original array. // we need the pivotIndex value in the original and not in the temp array pivotIndex = i; } arr[i] = temp[index]; index++; } return pivotIndex; // returning pivotIndex } void quickSort(int* arr, int start, int end) { if(start { int partitionIndex = partition(arr, start, end); // for getting partition quickSort(arr, start, partitionIndex - 1); // sorting left side array quickSort(arr, partitionIndex + 1, end); // sorting right side array } return; } int main() { int size = 9; int arr[size] = {5, 12, 7, 1, 13, 2 ,23, 11, 18}; cout << 'Unsorted array : '; for (int i = 0; i { cout << arr[i] << ' '; } printf('
'); quickSort(arr, 0, size - 1); cout << 'Sorted array : '; for (int i = 0; i { cout << arr[i] << ' '; } return 0; } Output Unsorted array : 5 12 7 1 13 2 23 11 18 Sorted array : 1 2 5 7 11 12 13 18 23 Please refer complete article on QuickSort for more details!>