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

۶۶۳ بازدید
آخرین به‌روزرسانی: ۱۹ تیر ۱۴۰۲
زمان مطالعه: ۸ دقیقه
انتخاب kامین عنصر کوچک در آرایه نامرتب — به زبان ساده

در این مطلب، روش نوشتن برنامه‌ای که kامین عنصر کوچک در آرایه نامرتب را پیدا کند، مورد بررسی قرار گرفته است. از همین روش می‌توان برای پیدا کردن kامین عنصر بزرگ در آرایه نامرتب نیز استفاده کرد. فرض می‌شود که یک آرایه و یک عدد K داده شده است. k کوچک‌تر از اندازه آرایه است. اکنون نیاز است که kاُمین عنصر کوچک‌تر در آرایه داده شده پیدا شود. همچنین، گفته شده که همه عناصر آرایه محدود هستند. شایان ذکر است، پیاده‌سازی روش آموزش داده شده در این مطلب، در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پی‌اچ‌پی» (PHP) انجام شده است. مثال زیر در این راستا قابل توجه است.

997696
Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 4
Output: 10

روشی که در این مطلب مورد بررسی قرار گرفته، افزونه‌ای از روش «انتخاب سریع» (QuickSelect) است. ایده این روش آن است که به طور تصادفی یک عنصر محوری (Pivot) انتخاب شود. برای پیاده‌سازی پارتیشن تصادفی شده، از تابع تصادفی rand()‎ برای تولید اندیس بین i و r، تعویض یک عنصر با اندیس تصادفی تولید شده با آخرین عنصر و در نهایت، فراخوانی فرایند تقسیم استاندارد که از آخرین عنصر به عنوان محور بهره می‌برد، استفاده شده است.

در ادامه، یک پیاده‌سازی از «انتخاب سریع تصادفی» (Randomized QuickSelect) در زبان‌های برنامه‌نویسی گوناگون ارائه شده است.

برنامه انتخاب kامین عنصر کوچک در آرایه نامرتب در ++C

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}

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

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*/

برنامه انتخاب kامین عنصر کوچک در آرایه نامرتب در پایتون ۳

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 

برنامه انتخاب kامین عنصر کوچک در آرایه نامرتب در #C

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 

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

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.

خروجی قطعه کد بالا به صورت زیر است.

K'th smallest element is 5

پیچیدگی زمانی روش ارائه شده در بالا همچنان از درجه O(n2)‎ است. در بدترین حالت، تابع تصادفی همواره یک عنصر گوشه‌ای را انتخاب می‌کند. پیچیدگی زمانی مورد انتظار از QuickSelect از درجه (O(n است.

فرض بر این است که در تحلیل‌ها، «مولد اعداد تصادفی» (Random Number Generator) دارای احتمال یکسانی برای تولید اعداد در رنج ورودی است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۴ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *