त्वरित सॉर्ट एल्गोरिथ्म

त्वरित सॉर्ट सबसे प्रसिद्ध सॉर्टिंग एल्गोरिदम में से एक है, क्योंकि इसे मानक लाइब्रेरी के अंदर कई प्रोग्रामिंग भाषाओं में कार्यान्वित किया जाता है। इस एल्गोरिदम का इतना उपयोग क्यों किया जाता है??
अपनी गति के कारण, त्वरित सॉर्ट एल्गोरिदम सबसे तेज़ सॉर्टिंग एल्गोरिदम में से एक है, जिसकी समय जटिलता O(n * log n) है, जहां n सरणी का आकार है और लॉग लघुगणक आधार 2 है।

यह कैसे काम करता है?

त्वरित सॉर्ट एल्गोरिदम को समझने के लिए आवश्यक मुख्य अवधारणा, फूट डालो और जीतो की रणनीति है।
फूट डालो और जीतो की रणनीति एक प्रसिद्ध सैन्य शब्द है, जिसका अर्थ यह होता है कि एक बड़े राष्ट्र को जीतने के लिए आपको पहले उस राष्ट्र को बनाना होगा, जो अक्सर आंतरिक संघर्ष या गृह युद्ध से विभाजित होता है, और फिर आप जाते हैं और पूरे राष्ट्र पर हमला करते हैं जबकि वे ऐसा करते हैं। व्यस्त।
ठीक है, लेकिन यह अवधारणा कंप्यूटर विज्ञान में कैसे परिवर्तित होती है? एल्गोरिदम में फूट डालो और जीतो का मतलब है कि वह छोटी समस्याओं को हल करके एक समस्या का समाधान करता है, यह गणितीय प्रेरण की अवधारणा के समान है, जिसमें, हम f(1) स्थापित करते हैं, फिर हम f(n) स्थापित करते हैं और फिर, हम दिखाते हैं कि f(n - 1) काम करता है, ऐसा करके, हम एक अवधारणा को प्रमाणित कर सकते हैं।
बांटो और जीतो की समस्याएँ भी उसी तरह काम करती हैं, पहले हम सबसे सरल समस्या को हल करते हैं, जिसे अक्सर बेस केस कहा जाता है, फिर, हम पुनरावर्ती केस तैयार करते हैं, और अंत में, हम समस्या बनाते हैं, जो सबसे सरल समस्याओं में टूट जाती है, क्योंकि जिन्हें हम हल करना जानते हैं।

एल्गोरिथ्म

मैं सी में एक कार्यान्वयन दिखाऊंगा, और फिर मैं पंक्ति दर पंक्ति समझाऊंगा कि यह कैसे काम करता है, क्योंकि यह एक काफी जटिल विचार है।

#include 
#include 
#include 

void _quick_sort(uint32_t *arr, size_t low, size_t high);
void quick_sort(uint32_t *arr, size_t size);

int32_t main(void)
{
    uint32_t list[] = {1, 4, 5, 10, 2, 9, 17, 100, 4, 2, 1000};

    // 11 is the number of elements list has
    // this is really usefull, because whenever we pass an array to a function, it decays as a pointer
    // due to this, if the function is in another translation layer it won't be able to know, so it can do the 
    // sizeof(list) / sizeof(list[1]) trick
    quick_sort(list, 11);

    for (size_t i = 0; i  i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] = high)
    {
        return;
    }

    // The pivot index is the index of the pivot element after partitioning,
    // so it means that the list is weakly sorted around the pivot,
    // (i.e. all elements to the left of the pivot are less than the pivot)
    // and all elements to the right are greater then
    size_t pivot_index = partition(arr, low, high);

    // Here we have a cool implementation detail
    // since pivot_index is a size_t, it is unsigned
    // and if we subtract 1 from an unsigned 0,
    // we get undefined behavior
    // This would happen, if the last element should be the first
    // in this case, no sorting is necessary, since there is nothing
    // before it
    if (pivot_index > 0)
    {
        // Sorting the left hand window
        // they have the bounds, [low, pivot_index - 1]
        // the -1 is so it is inclusive
        // because we now know the pivot is in the right spot
        _quick_sort(arr, low, pivot_index - 1);
    }

    // Same thing with before, now, we are sorting the right side of the window
    _quick_sort(arr, pivot_index   1, high);
}

इसलिए एल्गोरिदम का मुख्य विचार सरल है, सरणी विभाजन को सूची को दो भागों में तोड़ें, एक जिसमें सभी तत्व धुरी से छोटे हैं और एक जिसमें सभी तत्व धुरी से बड़े हैं।
और फिर, इस एल्गोरिदम को भागों पर पुनरावर्ती रूप से लागू करें, जब तक कि भाग में कोई तत्व न हो, इस मामले में, हम यह सुनिश्चित कर सकते हैं कि यह ठीक से क्रमबद्ध है।

त्वरित सॉर्ट एल्गोरिदम में एक धुरी चुनने पर एक महत्वपूर्ण बारीकियां है, अगर हम खराब धुरी चुनते हैं, तो हम एक भयानक जटिलता के साथ समाप्त होने जा रहे हैं, क्योंकि हर बार जब हम सरणी को दो सरणी में विभाजित करते हैं, तो हम छोटे के साथ समाप्त होते हैं सरणियाँ, इस मामले में, हमारे पास n पुनरावर्ती कॉल होने वाली हैं और हमें n तत्वों पर चलना होगा, इसलिए त्वरित सॉर्ट में O(n*n) की सबसे खराब स्थिति होती है, जो भयानक है, इसलिए हमें सावधान रहना होगा जब एक धुरी चुनना, एक अच्छा तरीका एक यादृच्छिक संख्या चुनना है, ऐसा करने से, हमें पूरा यकीन है कि हमें मध्य मामला मिलेगा, जो ओ (एन * लॉग एन) है, लॉग एन औसत मामले में, हम विभाजित हो जाएंगे सरणी को दो सारणियों में बाँट दिया गया है जिसमें प्रारंभिक सारणी के आधे तत्व हैं, और चूँकि हमें सभी तत्वों से गुजरना है, इसलिए n का एक कारक है।