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

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

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

// C++ implementation of randomized quickSelect 
#include<iostream> 
#include<climits> 
#include<cstdlib> 
using namespace std; 
  
int randomPartition(int arr[], int l, int r); 
  
// This function returns k'th smallest element in arr[l..r] using 
// QuickSort based method. ASSUMPTION: 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 a random element and 
        // get position of pivot element in sorted array 
        int pos = randomPartition(arr, l, r); 
  
        // If position is same as k 
        if (pos-l == k-1) 
            return arr[pos]; 
        if (pos-l > k-1)  // If position is more, recur for left subarray 
            return kthSmallest(arr, l, pos-1, k); 
  
        // Else recur for right subarray 
        return kthSmallest(arr, pos+1, r, k-pos+l-1); 
    } 
  
    // If k is more than the number of elements in the array 
    return INT_MAX; 
} 
  
void swap(int *a, int *b) 
{ 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 
  
// 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. This function is used by randomPartition() 
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; 
} 
  
// Picks a random pivot element between l and r and partitions 
// arr[l..r] around the randomly picked element using partition() 
int randomPartition(int arr[], int l, int r) 
{ 
    int n = r-l+1; 
    int pivot = rand() % n; 
    swap(&arr[l + pivot], &arr[r]); 
    return partition(arr, l, r); 
} 
  
// Driver program to test above methods 
int main() 
{ 
    int arr[] = {12, 3, 5, 7, 4, 19, 26}; 
    int n = sizeof(arr)/sizeof(arr[0]), k = 3; 
    cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k); 
    return 0; 
}

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

// Java program to find k'th smallest element in expected 
// linear time 
class KthSmallst 
{ 
    // 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 a random element and 
            // get position of pivot element in sorted array 
            int pos = randomPartition(arr, l, r); 
  
            // If position is same as k 
            if (pos-l == k-1) 
                return arr[pos]; 
  
            // If position is more, recur for left subarray 
            if (pos-l > k-1) 
                return kthSmallest(arr, l, pos-1, k); 
  
            // Else recur for right subarray 
            return kthSmallest(arr, pos+1, r, k-pos+l-1); 
        } 
  
        // If k is more than number of elements in array 
        return Integer.MAX_VALUE; 
    } 
  
    // Utility method to swap arr[i] and arr[j] 
    void swap(int arr[], int i, int j) 
    { 
        int temp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp; 
    } 
  
    // 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. This function 
    // is used by randomPartition() 
    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, j); 
                i++; 
            } 
        } 
        swap(arr, i, r); 
        return i; 
    } 
  
    // Picks a random pivot element between l and r and  
    // partitions arr[l..r] arount the randomly picked  
    // element using partition() 
    int randomPartition(int arr[], int l, int r) 
    { 
        int n = r-l+1; 
        int pivot = (int)(Math.random()) * (n-1); 
        swap(arr, l + pivot, r); 
        return partition(arr, l, r); 
    } 
  
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        KthSmallst ob = new KthSmallst(); 
        int arr[] = {12, 3, 5, 7, 4, 19, 26}; 
        int n = arr.length,k = 3; 
        System.out.println("K'th smallest element is "+ 
                           ob.kthSmallest(arr, 0, n-1, k)); 
    } 
} 
/*This code is contributed by Rajat Mishra*/

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

# Python3 implementation of randomized  
# quickSelect  
import random 
  
# This function returns k'th smallest  
# element in arr[l..r] using QuickSort 
# based method. ASSUMPTION: ELEMENTS 
# IN ARR[] ARE DISTINCT  
def kthSmallest(arr, l, r, k): 
      
    # If k is smaller than number of 
    # elements in array  
    if (k > 0 and k <= r - l + 1): 
          
        # Partition the array around a random  
        # element and get position of pivot  
        # element in sorted array  
        pos = randomPartition(arr, l, r)  
  
        # If position is same as k  
        if (pos - l == k - 1):  
            return arr[pos]  
        if (pos - l > k - 1): # If position is more,  
                            # recur for left subarray  
            return kthSmallest(arr, l, pos - 1, k)  
  
        # Else recur for right subarray  
        return kthSmallest(arr, pos + 1, r,  
                           k - pos + l - 1) 
  
    # If k is more than the number of  
    # elements in the array  
    return 999999999999
  
def swap(arr, a, b): 
    temp = arr[a] 
    arr[a] = arr[b] 
    arr[b] = temp 
  
# 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. This function 
# is used by randomPartition()  
def partition(arr, l, r): 
    x = arr[r] 
    i = l 
    for j in range(l, r): 
        if (arr[j] <= x): 
            swap(arr, i, j)  
            i += 1
    swap(arr, i, r)  
    return i 
  
# Picks a random pivot element between l and r  
# and partitions arr[l..r] around the randomly 
# picked element using partition()  
def randomPartition(arr, l, r): 
    n = r - l + 1
    pivot = int(random.random() % n)  
    swap(arr, l + pivot, r)  
    return partition(arr, l, r) 
  
# Driver Code 
if __name__ == '__main__': 
  
    arr = [12, 3, 5, 7, 4, 19, 26]  
    n = len(arr) 
    k = 3
    print("K'th smallest element is",  
           kthSmallest(arr, 0, n - 1, k)) 
  
# This code is contributed by PranchalK 

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

// C# program to find k'th smallest  
// element in expected linear time  
using System; 
  
class GFG  
{  
// 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 a  
        // random element and get position  
        // of pivot element in sorted array  
        int pos = randomPartition(arr, l, r);  
  
        // If position is same as k  
        if (pos-l == k - 1)  
            return arr[pos];  
  
        // If position is more, recur  
        // for left subarray  
        if (pos - l > k - 1)  
            return kthSmallest(arr, l, pos - 1, k);  
  
        // Else recur for right subarray  
        return kthSmallest(arr, pos + 1, r,  
                           k - pos + l - 1);  
    }  
  
    // If k is more than number of  
    // elements in array  
    return int.MaxValue;  
}  
  
// Utility method to swap arr[i] and arr[j]  
void swap(int []arr, int i, int j)  
{  
    int temp = arr[i];  
    arr[i] = arr[j];  
    arr[j] = temp;  
}  
  
// 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. This function  
// is used by randomPartition()  
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, j);  
            i++;  
        }  
    }  
    swap(arr, i, r);  
    return i;  
}  
  
// Picks a random pivot element between  
// l and r and partitions arr[l..r]  
// around the randomly picked element 
// using partition()  
int randomPartition(int []arr, int l, int r)  
{  
    int n = r - l + 1;  
    Random rnd = new Random(); 
    int rand = rnd.Next(0, 1); 
    int pivot = (int)(rand * (n - 1));  
    swap(arr, l + pivot, r);  
    return partition(arr, l, r);  
}  
  
// Driver Code 
public static void Main()  
{  
    GFG ob = new GFG();  
    int []arr = {12, 3, 5, 7, 4, 19, 26};  
    int n = arr.Length,k = 3;  
    Console.Write("K'th smallest element is "+  
            ob.kthSmallest(arr, 0, n - 1, k));  
}  
}  
  
// This code is contributed by 29AjayKumar 

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

<?php 
// C# program to find k'th smallest  
// element in expected linear time  
  
// This function returns k'th smallest   
// element in arr[l..r] using QuickSort based method. 
// ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCT  
function 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 a random element and  
        // get position of pivot element in sorted array  
        $pos = randomPartition($arr, $l, $r);  
  
        // If position is same as k  
        if ($pos-$l == $k-1)  
            return $arr[$pos];  
              
        // If position is more, recur for left subarray  
        if ($pos-$l > $k-1) 
            return kthSmallest($arr, $l, $pos-1, $k);  
  
        // Else recur for right subarray  
        return kthSmallest($arr, $pos+1, $r, 
                            $k-$pos+$l-1);  
    }  
  
    // If k is more than the number of elements in the array  
    return PHP_INT_MAX;  
}  
  
function swap($a, $b)  
{  
    $temp = $a;  
    $a = $b;  
    $b = $temp;  
}  
  
// 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. 
// This function is used by randomPartition()  
function partition($arr, $l, $r)  
{  
    $x = $arr[$r]; 
    $i = $l;  
    for ($j = $l; $j <= $r - 1; $j++)  
    {  
        if ($arr[$j] <= $x)  
        {  
            list($arr[$i], $arr[$j])=array($arr[$j],$arr[$i]); 
            //swap(&arr[i], &arr[j]);  
            $i++;  
        }  
    }  
    list($arr[$i], $arr[$r])=array($arr[$r],$arr[$i]); 
    //swap(&arr[i], &arr[r]);  
    return $i;  
}  
  
// Picks a random pivot element between 
//  l and r and partitions arr[l..r] around  
// the randomly picked element using partition()  
function randomPartition($arr, $l, $r)  
{  
    $n = $r-$l+1;  
    $pivot = rand() % $n;  
      
    list($arr[$l + $pivot], $arr[$r]) =  
            array($arr[$r],$arr[$l + $pivot] ); 
      
    //swap(&arr[l + pivot], &arr[r]);  
    return partition($arr, $l, $r);  
}  
  
// Driver program to test above methods  
    $arr = array(12, 3, 5, 7, 4, 19, 260);  
    $n = sizeof($arr)/sizeof($arr[0]); 
    $k = 3;  
    echo "K'th smallest element is " , 
            kthSmallest($arr, 0, $n-1, $k);  
      
  
// This code is contributed by ajit.

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

K'th smallest element is 5

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

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

• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• آموزش ساختمان داده‌ها با C و ++C (همراه با حل نمونه سوالات کنکور ارشد)
• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• ساختمان داده (Data Structure) — راهنمای جامع و کاربردی
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
• مرتب‌سازی درجی (Insertion Sort) — به زبان ساده
• معرفی تکنیک‌های مرتب‌سازی (Sorting Techniques) — ساختار داده و الگوریتم ها

^^