algorithm
जल्दी से सुलझाएं

टिप्पणियों

क्विकॉर्ट बेसिक्स

क्विकॉर्ट एक छँटाई एल्गोरिथ्म है जो एक तत्व ("पिवट") को चुनता है और दो विभाजन बनाने वाले एरे को फिर से व्यवस्थित करता है जैसे कि पिवट से कम सभी तत्व इसके पहले आते हैं और सभी तत्व अधिक से अधिक आते हैं। एल्गोरिथ्म तब विभाजन के लिए पुनरावर्ती रूप से लागू किया जाता है जब तक कि सूची को क्रमबद्ध नहीं किया जाता है।

1. लोमुटो विभाजन योजना तंत्र:

यह योजना एक धुरी चुनती है जो आम तौर पर सरणी में अंतिम तत्व है। एल्गोरिथ्म सूचकांक को धुरी को चर में रखने के लिए अनुक्रमणिका रखता है और हर बार जब वह धुरी से कम या उसके बराबर एक तत्व पाता है, तो यह सूचकांक बढ़ जाता है और उस तत्व को धुरी से पहले रखा जाएगा।

partition(A, low, high) is
pivot := A[high]
i := low
for j := low to high – 1 do
    if A[j] ≤ pivot then
        swap A[i] with A[j]
        i := i + 1
swap A[i] with A[high]
return i

त्वरित सॉर्ट तंत्र:

quicksort(A, low, high) is
if low < high then
    p := partition(A, low, high)
    quicksort(A, low, p – 1)
    quicksort(A, p + 1, high)

त्वरित प्रकार का उदाहरण:

2. होरे विभाजन योजना:

यह दो सूचकांकों का उपयोग करता है जो कि विभाजन के अंत में शुरू होते हैं, फिर एक दूसरे की ओर बढ़ते हैं, जब तक कि वे एक व्युत्क्रम का पता नहीं लगाते हैं: तत्वों की एक जोड़ी, धुरी से एक बड़ा या बराबर, एक कम या बराबर, जो गलत में हैं एक दूसरे के सापेक्ष आदेश। उल्टे तत्वों की अदला-बदली की जाती है। जब सूचकांक मिलते हैं, तो एल्गोरिथ्म बंद हो जाता है और अंतिम सूचकांक लौटाता है। होरे की योजना लोमुटो की विभाजन योजना की तुलना में अधिक कुशल है क्योंकि यह औसतन तीन गुना कम स्वैप करती है, और यह सभी मूल्यों के बराबर होने पर भी कुशल विभाजन बनाती है।

quicksort(A, lo, hi) is
if lo < hi then
    p := partition(A, lo, hi)
    quicksort(A, lo, p)
    quicksort(A, p + 1, hi)

विभाजन:

partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
    do:
        i := i + 1
    while A[i] < pivot do
    
    do:
        j := j - 1
    while A[j] > pivot do
    
    if i >= j then
        return j
    
    swap A[i] with A[j]

C # कार्यान्वयन

public class QuickSort
{
    private static int Partition(int[] input, int low, int high)
    {
        var pivot = input[high];
        var i = low - 1;
        for (var j = low; j <= high - 1; j++)
        {
            if (input[j] <= pivot)
            {
                i++;
                var temp = input[i];
                input[i] = input[j];
                input[j] = temp;
            }
        }
        var tmp = input[i + 1];
        input[i + 1] = input[high];
        input[high] = tmp;
        return (i + 1);
    }

    private static void SortQuick(int[] input, int low, int high)
    {
        while (true)
        {
            if (low < high)
            {
                var pi = Partition(input, low, high);
                SortQuick(input, low, pi - 1);
                low = pi + 1;
                continue;
            }
            break;
        }
    }

    public static int[] Main(int[] input)
    {
        SortQuick(input, 0, input.Length - 1);
        return input;
    }
}

हास्केल कार्यान्वयन

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = quickSort [ y | y <- xs, y <= x ] 
                   ++ [x] 
                   ++ quickSort [ z | z <- xs, z > x ]

लोमुटो विभाजन जावा कार्यान्वयन

public class Solution {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] ar = new int[n];
    for(int i=0; i<n; i++)
      ar[i] = sc.nextInt();
     quickSort(ar, 0, ar.length-1);   
}

public static void quickSort(int[] ar, int low, int high)
 {
    if(low<high)
    {
        int p = partition(ar, low, high);
        quickSort(ar, 0 , p-1);
        quickSort(ar, p+1, high);
    }    
 }   
public static int partition(int[] ar, int l, int r)
 {
    int pivot = ar[r];
    int i =l;
    for(int j=l; j<r; j++)
     {
        if(ar[j] <= pivot)
         {
            int t = ar[j];
            ar[j] = ar[i];
            ar[i] = t;
            i++;
        }   
    } 
    int t = ar[i];
    ar[i] = ar[r];
    ar[r] = t;
 
    return i;
} 

पाइथन में क्विकॉर्ट

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) / 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

print quicksort([3,6,8,10,1,2,1])

प्रिंट्स "[1, 1, 2, 3, 6, 8, 10]"