انتخاب kامین عنصر کوچک در آرایه نامرتب — به زبان ساده

1// C++ implementation of randomized quickSelect 
2#include<iostream> 
3#include<climits> 
4#include<cstdlib> 
5using namespace std; 
6  
7int randomPartition(int arr[], int l, int r); 
8  
9// This function returns k'th smallest element in arr[l..r] using 
10// QuickSort based method. ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCT 
11int kthSmallest(int arr[], int l, int r, int k) 
12{ 
13    // If k is smaller than number of elements in array 
14    if (k > 0 && k <= r - l + 1) 
15    { 
16        // Partition the array around a random element and 
17        // get position of pivot element in sorted array 
18        int pos = randomPartition(arr, l, r); 
19  
20        // If position is same as k 
21        if (pos-l == k-1) 
22            return arr[pos]; 
23        if (pos-l > k-1)  // If position is more, recur for left subarray 
24            return kthSmallest(arr, l, pos-1, k); 
25  
26        // Else recur for right subarray 
27        return kthSmallest(arr, pos+1, r, k-pos+l-1); 
28    } 
29  
30    // If k is more than the number of elements in the array 
31    return INT_MAX; 
32} 
33  
34void swap(int *a, int *b) 
35{ 
36    int temp = *a; 
37    *a = *b; 
38    *b = temp; 
39} 
40  
41// Standard partition process of QuickSort().  It considers the last 
42// element as pivot and moves all smaller element to left of it and 
43// greater elements to right. This function is used by randomPartition() 
44int partition(int arr[], int l, int r) 
45{ 
46    int x = arr[r], i = l; 
47    for (int j = l; j <= r - 1; j++) 
48    { 
49        if (arr[j] <= x) 
50        { 
51            swap(&arr[i], &arr[j]); 
52            i++; 
53        } 
54    } 
55    swap(&arr[i], &arr[r]); 
56    return i; 
57} 
58  
59// Picks a random pivot element between l and r and partitions 
60// arr[l..r] around the randomly picked element using partition() 
61int randomPartition(int arr[], int l, int r) 
62{ 
63    int n = r-l+1; 
64    int pivot = rand() % n; 
65    swap(&arr[l + pivot], &arr[r]); 
66    return partition(arr, l, r); 
67} 
68  
69// Driver program to test above methods 
70int main() 
71{ 
72    int arr[] = {12, 3, 5, 7, 4, 19, 26}; 
73    int n = sizeof(arr)/sizeof(arr[0]), k = 3; 
74    cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k); 
75    return 0; 
76}

1// Java program to find k'th smallest element in expected 
2// linear time 
3class KthSmallst 
4{ 
5    // This function returns k'th smallest element in arr[l..r] 
6    // using QuickSort based method.  ASSUMPTION: ALL ELEMENTS 
7    // IN ARR[] ARE DISTINCT 
8    int kthSmallest(int arr[], int l, int r, int k) 
9    { 
10        // If k is smaller than number of elements in array 
11        if (k > 0 && k <= r - l + 1) 
12        { 
13            // Partition the array around a random element and 
14            // get position of pivot element in sorted array 
15            int pos = randomPartition(arr, l, r); 
16  
17            // If position is same as k 
18            if (pos-l == k-1) 
19                return arr[pos]; 
20  
21            // If position is more, recur for left subarray 
22            if (pos-l > k-1) 
23                return kthSmallest(arr, l, pos-1, k); 
24  
25            // Else recur for right subarray 
26            return kthSmallest(arr, pos+1, r, k-pos+l-1); 
27        } 
28  
29        // If k is more than number of elements in array 
30        return Integer.MAX_VALUE; 
31    } 
32  
33    // Utility method to swap arr[i] and arr[j] 
34    void swap(int arr[], int i, int j) 
35    { 
36        int temp = arr[i]; 
37        arr[i] = arr[j]; 
38        arr[j] = temp; 
39    } 
40  
41    // Standard partition process of QuickSort().  It considers 
42    // the last element as pivot and moves all smaller element  
43    // to left of it and greater elements to right. This function 
44    // is used by randomPartition() 
45    int partition(int arr[], int l, int r) 
46    { 
47        int x = arr[r], i = l; 
48        for (int j = l; j <= r - 1; j++) 
49        { 
50            if (arr[j] <= x) 
51            { 
52                swap(arr, i, j); 
53                i++; 
54            } 
55        } 
56        swap(arr, i, r); 
57        return i; 
58    } 
59  
60    // Picks a random pivot element between l and r and  
61    // partitions arr[l..r] arount the randomly picked  
62    // element using partition() 
63    int randomPartition(int arr[], int l, int r) 
64    { 
65        int n = r-l+1; 
66        int pivot = (int)(Math.random()) * (n-1); 
67        swap(arr, l + pivot, r); 
68        return partition(arr, l, r); 
69    } 
70  
71    // Driver method to test above 
72    public static void main(String args[]) 
73    { 
74        KthSmallst ob = new KthSmallst(); 
75        int arr[] = {12, 3, 5, 7, 4, 19, 26}; 
76        int n = arr.length,k = 3; 
77        System.out.println("K'th smallest element is "+ 
78                           ob.kthSmallest(arr, 0, n-1, k)); 
79    } 
80} 
81/*This code is contributed by Rajat Mishra*/

1# Python3 implementation of randomized  
2# quickSelect  
3import random 
4  
5# This function returns k'th smallest  
6# element in arr[l..r] using QuickSort 
7# based method. ASSUMPTION: ELEMENTS 
8# IN ARR[] ARE DISTINCT  
9def kthSmallest(arr, l, r, k): 
10      
11    # If k is smaller than number of 
12    # elements in array  
13    if (k > 0 and k <= r - l + 1): 
14          
15        # Partition the array around a random  
16        # element and get position of pivot  
17        # element in sorted array  
18        pos = randomPartition(arr, l, r)  
19  
20        # If position is same as k  
21        if (pos - l == k - 1):  
22            return arr[pos]  
23        if (pos - l > k - 1): # If position is more,  
24                            # recur for left subarray  
25            return kthSmallest(arr, l, pos - 1, k)  
26  
27        # Else recur for right subarray  
28        return kthSmallest(arr, pos + 1, r,  
29                           k - pos + l - 1) 
30  
31    # If k is more than the number of  
32    # elements in the array  
33    return 999999999999
34  
35def swap(arr, a, b): 
36    temp = arr[a] 
37    arr[a] = arr[b] 
38    arr[b] = temp 
39  
40# Standard partition process of QuickSort().  
41# It considers the last element as pivot and 
42# moves all smaller element to left of it and  
43# greater elements to right. This function 
44# is used by randomPartition()  
45def partition(arr, l, r): 
46    x = arr[r] 
47    i = l 
48    for j in range(l, r): 
49        if (arr[j] <= x): 
50            swap(arr, i, j)  
51            i += 1
52    swap(arr, i, r)  
53    return i 
54  
55# Picks a random pivot element between l and r  
56# and partitions arr[l..r] around the randomly 
57# picked element using partition()  
58def randomPartition(arr, l, r): 
59    n = r - l + 1
60    pivot = int(random.random() % n)  
61    swap(arr, l + pivot, r)  
62    return partition(arr, l, r) 
63  
64# Driver Code 
65if __name__ == '__main__': 
66  
67    arr = [12, 3, 5, 7, 4, 19, 26]  
68    n = len(arr) 
69    k = 3
70    print("K'th smallest element is",  
71           kthSmallest(arr, 0, n - 1, k)) 
72  
73# This code is contributed by PranchalK 

1// C# program to find k'th smallest  
2// element in expected linear time  
3using System; 
4  
5class GFG  
6{  
7// This function returns k'th smallest  
8// element in arr[l..r] using QuickSort  
9// based method. ASSUMPTION: ALL ELEMENTS  
10// IN ARR[] ARE DISTINCT  
11int kthSmallest(int []arr, int l, int r, int k)  
12{  
13    // If k is smaller than number  
14    // of elements in array  
15    if (k > 0 && k <= r - l + 1)  
16    {  
17        // Partition the array around a  
18        // random element and get position  
19        // of pivot element in sorted array  
20        int pos = randomPartition(arr, l, r);  
21  
22        // If position is same as k  
23        if (pos-l == k - 1)  
24            return arr[pos];  
25  
26        // If position is more, recur  
27        // for left subarray  
28        if (pos - l > k - 1)  
29            return kthSmallest(arr, l, pos - 1, k);  
30  
31        // Else recur for right subarray  
32        return kthSmallest(arr, pos + 1, r,  
33                           k - pos + l - 1);  
34    }  
35  
36    // If k is more than number of  
37    // elements in array  
38    return int.MaxValue;  
39}  
40  
41// Utility method to swap arr[i] and arr[j]  
42void swap(int []arr, int i, int j)  
43{  
44    int temp = arr[i];  
45    arr[i] = arr[j];  
46    arr[j] = temp;  
47}  
48  
49// Standard partition process of QuickSort().  
50// It considers the last element as pivot and  
51// moves all smaller element to left of it  
52// and greater elements to right. This function  
53// is used by randomPartition()  
54int partition(int []arr, int l, int r)  
55{  
56    int x = arr[r], i = l;  
57    for (int j = l; j <= r - 1; j++)  
58    {  
59        if (arr[j] <= x)  
60        {  
61            swap(arr, i, j);  
62            i++;  
63        }  
64    }  
65    swap(arr, i, r);  
66    return i;  
67}  
68  
69// Picks a random pivot element between  
70// l and r and partitions arr[l..r]  
71// around the randomly picked element 
72// using partition()  
73int randomPartition(int []arr, int l, int r)  
74{  
75    int n = r - l + 1;  
76    Random rnd = new Random(); 
77    int rand = rnd.Next(0, 1); 
78    int pivot = (int)(rand * (n - 1));  
79    swap(arr, l + pivot, r);  
80    return partition(arr, l, r);  
81}  
82  
83// Driver Code 
84public static void Main()  
85{  
86    GFG ob = new GFG();  
87    int []arr = {12, 3, 5, 7, 4, 19, 26};  
88    int n = arr.Length,k = 3;  
89    Console.Write("K'th smallest element is "+  
90            ob.kthSmallest(arr, 0, n - 1, k));  
91}  
92}  
93  
94// This code is contributed by 29AjayKumar 

1<?php 
2// C# program to find k'th smallest  
3// element in expected linear time  
4  
5// This function returns k'th smallest   
6// element in arr[l..r] using QuickSort based method. 
7// ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCT  
8function kthSmallest($arr, $l, $r, $k)  
9{  
10    // If k is smaller than number of elements in array  
11    if ($k > 0 && $k <= $r - $l + 1)  
12    {  
13        // Partition the array around a random element and  
14        // get position of pivot element in sorted array  
15        $pos = randomPartition($arr, $l, $r);  
16  
17        // If position is same as k  
18        if ($pos-$l == $k-1)  
19            return $arr[$pos];  
20              
21        // If position is more, recur for left subarray  
22        if ($pos-$l > $k-1) 
23            return kthSmallest($arr, $l, $pos-1, $k);  
24  
25        // Else recur for right subarray  
26        return kthSmallest($arr, $pos+1, $r, 
27                            $k-$pos+$l-1);  
28    }  
29  
30    // If k is more than the number of elements in the array  
31    return PHP_INT_MAX;  
32}  
33  
34function swap($a, $b)  
35{  
36    $temp = $a;  
37    $a = $b;  
38    $b = $temp;  
39}  
40  
41// Standard partition process of QuickSort().  
42// It considers the last element as pivot 
43// and moves all smaller element to left   
44// of it and greater elements to right. 
45// This function is used by randomPartition()  
46function partition($arr, $l, $r)  
47{  
48    $x = $arr[$r]; 
49    $i = $l;  
50    for ($j = $l; $j <= $r - 1; $j++)  
51    {  
52        if ($arr[$j] <= $x)  
53        {  
54            list($arr[$i], $arr[$j])=array($arr[$j],$arr[$i]); 
55            //swap(&arr[i], &arr[j]);  
56            $i++;  
57        }  
58    }  
59    list($arr[$i], $arr[$r])=array($arr[$r],$arr[$i]); 
60    //swap(&arr[i], &arr[r]);  
61    return $i;  
62}  
63  
64// Picks a random pivot element between 
65//  l and r and partitions arr[l..r] around  
66// the randomly picked element using partition()  
67function randomPartition($arr, $l, $r)  
68{  
69    $n = $r-$l+1;  
70    $pivot = rand() % $n;  
71      
72    list($arr[$l + $pivot], $arr[$r]) =  
73            array($arr[$r],$arr[$l + $pivot] ); 
74      
75    //swap(&arr[l + pivot], &arr[r]);  
76    return partition($arr, $l, $r);  
77}  
78  
79// Driver program to test above methods  
80    $arr = array(12, 3, 5, 7, 4, 19, 260);  
81    $n = sizeof($arr)/sizeof($arr[0]); 
82    $k = 3;  
83    echo "K'th smallest element is " , 
84            kthSmallest($arr, 0, $n-1, $k);  
85      
86  
87// This code is contributed by ajit.