빠른 선택 알고리즘
빠른 선택 순서가 지정되지 않은 목록에서 k번째로 작은 요소를 찾는 선택 알고리즘입니다. 이는 다음과 관련이 있습니다. 빠른 정렬 정렬 알고리즘.
예:
Input: arr[] = {7, 10, 4, 3, 20, 15} k = 3 Output: 7 Input: arr[] = {7, 10, 4, 3, 20, 15} k = 4 Output: 10 알고리즘은 QuickSort와 유사합니다. 차이점은 양쪽에 대해 반복되는 대신(피벗을 찾은 후) k번째로 작은 요소를 포함하는 부분에 대해서만 반복된다는 것입니다. 논리는 간단합니다. 분할된 요소의 인덱스가 k보다 크면 왼쪽 부분에 대해 반복됩니다. index가 k와 동일하면 k번째로 작은 요소를 찾아서 반환합니다. index가 k보다 작으면 오른쪽 부분에 대해 반복됩니다. 이렇게 하면 예상되는 복잡성이 O(n log n)에서 O(n)으로 감소하며 최악의 경우는 O(n^2)입니다.
function quickSelect(list, left, right, k) if left = right return list[left] Select a pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex return list[k] else if k C++14 // CPP program for implementation of QuickSelect #include using namespace std; // Standard partition process of QuickSort(). // It considers the last element as pivot // and moves all smaller element to left of // it and greater elements to right int partition(int arr[], int l, int r) { int x = arr[r], i = l; for (int j = l; j <= r - 1; j++) { if (arr[j] <= x) { swap(arr[i], arr[j]); i++; } } swap(arr[i], arr[r]); return i; } // This function returns k'th smallest // element in arr[l..r] using QuickSort // based method. ASSUMPTION: ALL ELEMENTS // IN ARR[] ARE DISTINCT int kthSmallest(int arr[], int l, int r, int k) { // If k is smaller than number of // elements in array if (k>0 && k <= r - l + 1) { // Partition the array around last // element and get position of pivot // element in sorted array int index = partition(arr, l, r); // If position is same as k if (index - l == k - 1) return arr[index]; // If position is more, recur // for left subarray if (index - l>k - 1) kthSmallest(arr, l, index - 1, k)를 반환합니다. // 그렇지 않으면 오른쪽 하위 배열에 대해 반복 return kthSmallest(arr, index + 1, r, k - index + l - 1); } // k가 배열의 요소 수보다 크면 // INT_MAX를 반환합니다. } // 위 메소드를 테스트하기 위한 드라이버 프로그램 int main() { int arr[] = { 10, 4, 5, 8, 6, 11, 26 }; int n = sizeof(arr) / sizeof(arr[0]); 정수 k = 3; 시합 < < 'K-th smallest element is ' < < kthSmallest(arr, 0, n - 1, k); return 0; } Java // Java program of Quick Select import java.util.Arrays; class GFG { // partition function similar to quick sort // Considers last element as pivot and adds // elements with less value to the left and // high value to the right and also changes // the pivot position to its respective position // in the final array. public static int partition(int[] arr, int low, int high) { int pivot = arr[high], pivotloc = low; for (int i = low; i <= high; i++) { // inserting elements of less value // to the left of the pivot location if (arr[i] int temp = arr[i]; arr[i] = arr[pivotloc]; arr[pivotloc] = temp; pivotloc++; } } // swapping pivot to the final pivot location int temp = arr[high]; arr[high] = arr[pivotloc]; arr[pivotloc] = temp; return pivotloc; } // finds the kth position (of the sorted array) // in a given unsorted array i.e this function // can be used to find both kth largest and // kth smallest element in the array. // ASSUMPTION: all elements in arr[] are distinct public static int kthSmallest(int[] arr, int low, int high, int k) { // find the partition int partition = partition(arr, low, high); // if partition value is equal to the kth position, // return value at k. if (partition == k - 1) return arr[partition]; // if partition value is less than kth position, // search right side of the array. else if (partition 1) return kthSmallest(arr, partition + 1, high, k); // if partition value is more than kth position, // search left side of the array. else return kthSmallest(arr, low, partition - 1, k); } // Driver Code public static void main(String[] args) { int[] array = new int[] { 10, 4, 5, 8, 6, 11, 26 }; int[] arraycopy = new int[] { 10, 4, 5, 8, 6, 11, 26 }; int kPosition = 3; int length = array.length; if (kPosition>length) { System.out.println('범위를 벗어난 인덱스'); } else { // k번째로 작은 값 찾기 System.out.println( '배열에서 K번째로 작은 요소 : ' + kthSmallest(arraycopy, 0, length - 1, kPosition)); } } } // 이 코드는 Saiteja Pamulapati가 제공한 것입니다. Python3 # Quick Select의 Python3 프로그램 # QuickSort()의 표준 파티션 프로세스. # 마지막 요소를 피벗으로 간주하고 # 작은 요소는 모두 왼쪽으로 이동하고 # 큰 요소는 오른쪽으로 이동합니다. def partition(arr, l, r): x = arr[r] i = l for j in range(l, r): arr[j]인 경우 <= x: arr[i], arr[j] = arr[j], arr[i] i += 1 arr[i], arr[r] = arr[r], arr[i] return i # finds the kth position (of the sorted array) # in a given unsorted array i.e this function # can be used to find both kth largest and # kth smallest element in the array. # ASSUMPTION: all elements in arr[] are distinct def kthSmallest(arr, l, r, k): # if k is smaller than number of # elements in array if (k>0과 k <= r - l + 1): # Partition the array around last # element and get position of pivot # element in sorted array index = partition(arr, l, r) # if position is same as k if (index - l == k - 1): return arr[index] # If position is more, recur # for left subarray if (index - l>k - 1): return kthSmallest(arr, l, index - 1, k) # 그렇지 않으면 오른쪽 하위 배열에 대해 반복 return kthSmallest(arr, index + 1, r, k - index + l - 1) print('Index out of bound') # 드라이버 코드 arr = [ 10, 4, 5, 8, 6, 11, 26 ] n = len(arr) k = 3 print('K번째로 작은 요소는 ', end = ' ') print(kthSmallest(arr, 0, n - 1, k)) # 이 코드는 Muskan Kalra가 기여했습니다. C# // 시스템을 사용한 빠른 선택의 C# 프로그램; class GFG { // 퀵 정렬과 유사한 분할 함수 // 마지막 요소를 피벗으로 간주하고 // 왼쪽에 값이 작은 요소를 추가하고 오른쪽에 높은 값을 가진 요소를 추가하고 // 피벗 위치를 해당 위치로 변경합니다. / / 읽기 전용 배열에 있습니다. static int partitions(int []arr,int low, int high) { int 피벗 = arr[high],ivoloc = low, temp; for (int i = 낮음; i <= high; i++) { // inserting elements of less value // to the left of the pivot location if(arr[i] { temp = arr[i]; arr[i] = arr[pivotloc]; arr[pivotloc] = temp; pivotloc++; } } // swapping pivot to the readonly pivot location temp = arr[high]; arr[high] = arr[pivotloc]; arr[pivotloc] = temp; return pivotloc; } // finds the kth position (of the sorted array) // in a given unsorted array i.e this function // can be used to find both kth largest and // kth smallest element in the array. // ASSUMPTION: all elements in []arr are distinct static int kthSmallest(int[] arr, int low, int high, int k) { // find the partition int partition = partitions(arr,low,high); // if partition value is equal to the kth position, // return value at k. if(partition == k) return arr[partition]; // if partition value is less than kth position, // search right side of the array. else if(partition return kthSmallest(arr, partition + 1, high, k ); // if partition value is more than kth position, // search left side of the array. else return kthSmallest(arr, low, partition - 1, k ); } // Driver Code public static void Main(String[] args) { int[] array = {10, 4, 5, 8, 6, 11, 26}; int[] arraycopy = {10, 4, 5, 8, 6, 11, 26}; int kPosition = 3; int length = array.Length; if(kPosition>length) { Console.WriteLine('범위를 벗어난 인덱스'); } else { // k번째로 작은 값 찾기 Console.WriteLine('배열에서 K번째로 작은 요소: ' + kthSmallest(arraycopy, 0, length - 1, kPosition - 1)); } } } // 이 코드는 29AjayKumar에서 제공했습니다. Javascript // Quick Select의 Javascript 프로그램 // 빠른 정렬과 유사한 파티션 기능 // 마지막 요소를 피벗으로 간주하고 // 값이 작은 요소를 왼쪽 및 // 높은 값에 추가합니다. 오른쪽으로 이동하고 // 피벗 위치를 // 최종 배열의 해당 위치로 변경합니다. function _partition(arr, low, high) { let 피벗 = arr[high], 피벗loc = 낮음; for (i = 낮음; 나는 <= high; i++) { // inserting elements of less value // to the left of the pivot location if (arr[i] { let temp = arr[i]; arr[i] = arr[pivotloc]; arr[pivotloc] = temp; pivotloc++; } } // swapping pivot to the final pivot location let temp = arr[high]; arr[high] = arr[pivotloc]; arr[pivotloc] = temp; return pivotloc; } // finds the kth position (of the sorted array) // in a given unsorted array i.e this function // can be used to find both kth largest and // kth smallest element in the array. // ASSUMPTION: all elements in arr[] are distinct function kthSmallest(arr, low, high, k) { // find the partition let partition = _partition(arr, low, high); // if partition value is equal to the kth position, // return value at k. if (partition == k - 1) return arr[partition]; // if partition value is less than kth position, // search right side of the array. else if (partition return kthSmallest(arr, partition + 1, high, k); // if partition value is more than kth position, // search left side of the array. else return kthSmallest(arr, low, partition - 1, k); } // Driver Code let array = [ 10, 4, 5, 8, 6, 11, 26]; let arraycopy = [10, 4, 5, 8, 6, 11, 26 ]; let kPosition = 3; let length = array.length; if (kPosition>length) { document.write('범위를 벗어난 인덱스 '); } else { // k번째로 작은 값 찾기 document.write( '배열에서 K번째로 작은 요소 : ' + kthSmallest(arraycopy, 0, length - 1, kPosition)+' '); } // 이 코드는 rag2127에서 제공한 것입니다. 출력: K번째로 작은 요소는 6개입니다. 중요 사항: 퀵 정렬과 마찬가지로 실제로는 빠르지만 최악의 경우 성능이 좋지 않습니다. 파티션 프로세스는 QuickSort와 동일하며 재귀 코드만 다릅니다. 최악의 경우 O(n)에서 k번째로 작은 요소를 찾는 알고리즘이 있지만 QuickSelect가 평균적으로 더 나은 성능을 발휘합니다. 관련 C++ 함수 : C++의 std::nth_element
