प्रवेग अल्गोरिदम सर्वात महत्वाचे वर्गीकरण अल्गोरिदम आहे. फ्यूजन सॉर्टिंग प्रमाणे, क्विकॉर्ट देखील वापरते विभाजित-विजय म्हणूनच, जावामध्ये रिकर्सन वापरून वेगवान अल्गोरिदम लागू करणे सोपे आहे, परंतु क्विकॉर्टची डुप्लिकेट आवृत्ती लिहिणे थोडे अधिक कठीण आहे. म्हणूनच आता मुलाखतकार तुम्हाला पुनरावृत्तीशिवाय क्विकसॉर्ट चालवण्यास सांगत आहेत. मुलाखत क्विकॉर्ट अल्गोरिदम वापरून जावामध्ये अॅरेची व्यवस्था करण्यासाठी प्रोग्राम लिहिण्यासारख्या प्रोग्रामसह सुरू होईल, shown तुम्हाला दाखवल्याप्रमाणे क्विकसॉर्टची पुनरावृत्ती अंमलबजावणी आढळेल येथे:. पाठपुरावा म्हणून, मुलाखत घेणारा आता तुम्हाला Iteration वापरून समान अल्गोरिदम एन्कोड करण्यास सांगेल.

जर तुम्हाला आठवत असेल तर, बॅकट्रॅकिंगशिवाय बायनरी ट्री समस्या सोडवताना, उदाहरणार्थ, बॅकट्रॅकिंग न करता प्री-ऑर्डर लॉगिंग (येथे:) return परत न करता प्रक्रिया पार करा (येथे:), आम्ही वापरले: स्टॅक: पुनरावृत्ती पुनर्स्थित करा. जावामध्ये पुनरावृत्ती प्रोग्राम लिहिण्यासाठी आपण येथे समान तंत्र वापरू शकता. स्टॅक प्रत्यक्षात पुनरावृत्तीची नक्कल करते.

प्रोग्रामिंग / एन्क्रिप्शन मुलाखतीला जाण्यापूर्वी, सर्व उपलब्ध ज्ञान वापरण्यासाठी डेटा स्ट्रक्चर և अल्गोरिदममध्ये शक्य तितका सराव करणे पूर्णपणे आवश्यक आहे. आपण डेटा स्ट्रक्चर आणि अल्गोरिदम वरील सर्वसमावेशक कोर्समध्ये सामील होऊ शकता, जसे की: डेटा स्ट्रक्चर्स – अल्गोरिदम. जावा वापरून डीप डायव्ह: उडेमी वर तुमच्या समजूतदारपणाची पोकळी भरून काढण्यासाठी.

पुनरावृत्ती क्विक्सॉर्ट अल्गोरिदम:

मी माझ्या अभियांत्रिकी वर्गांमध्ये गतीबद्दल शिकलो, त्या वेळी मला समजलेल्या काही अल्गोरिदमपैकी एक. हे विभाजन -विजय अल्गोरिदम असल्याने, आपण अक्ष -विभाजन अॅरे निवडा. विलीनीकरण क्रमवारीच्या विपरीत, जे विभाजन आणि जिंकण्यासाठी एक अल्गोरिदम आहे, जेथे संयुक्त पायर्यांवर सर्वात महत्वाचे काम केले जाते. वेगवान, खरे काम वेगळे होण्याच्या पायरीवर घडते, एकत्र करण्याची पायरी काहीही करत नाही.

बीटीडब्ल्यू, अल्गोरिदमचे कार्य समान राहील, आपण पुनरावृत्ती समाधान वापरता किंवा पुनरावृत्ती समाधान. वारंवार समाधान झाल्यास आम्ही वापरू स्टॅक: त्याऐवजी पुनरावृत्ती:.

मध्यस्थीच्या तयारीची प्रक्रिया सुरू करण्यासाठी आपण काही पावले उचलू शकता.

  • श्रेणी (0 … n) स्टॅकवर ढकलून द्या
  • दिलेल्या वस्तुमानाला अक्षाने विभाजित करा
  • शीर्ष आयटम घाला.
  • जर श्रेणीमध्ये एकापेक्षा जास्त घटक असतील तर विभाजने दाबा (अनुक्रमणिका श्रेणी)
  • ढीग रिक्त होईपर्यंत वरील 3 चरणांचे अनुसरण करा

आपणास असे आढळेल की पुनरावृत्ती अल्गोरिदम लिहिणे सोपे असले तरी ते त्यांच्या पुनरावृत्तीपेक्षा नेहमी मंद असतात. तेव्हा जेव्हा मुलाखतकार तुम्हाला वेळ अवघडपणाची पद्धत निवडण्यास सांगतो जिथे मेमरी चिंता नाही, तेव्हा तुम्ही कोणता पर्याय निवडाल?

ठीक आहे, “पुनरावृत्ती” पुनरावृत्ती गती हे O (N log N) միջին O (n ^ 2) चे सरासरी प्रकरण आहे, परंतु पुनरावृत्ती आवृत्ती लहान आणि स्पष्ट आहे. पुनरावृत्ती जलद आहे – आपल्याला कॉलबॅक सेटचे अनुकरण करते.

बीटीडब्ल्यू, आपल्याला याबद्दल अधिक जाणून घ्यायचे असल्यास पुनरावृत्तीचा पिरामिडशी काय संबंध आहे? आणि O (n log n) वेळेवर quicksort सरासरी का चालते? मी वाचण्याची सूचना करतो ग्रोकिंग अल्गोरिदम, दुर्मिळ अल्गोरिदमचे पुस्तक जे वास्तविक जगातील उदाहरणांसह समजणे सोपे आहे. मी नुकतीच या पुस्तकाची एक प्रत विकत घेतली – जरी मला ते सर्व अल्गोरिदम माहित आहेत, तरी ते माझ्यासाठी खूप वाचनीय आहे – मला एक नवीन दृष्टीकोन मिळाला. म्हणून जर तुम्ही अल्गोरिदमसह संघर्ष करत असाल तर हे पुस्तक तुम्ही आता वाचायला हवे.

पुनरावृत्तीशिवाय जावा मध्ये QuickSort चे उदाहरण.

आमच्या जावा प्रोग्रामचा हा एक नमुना आहे की क्विकसॉर्टने लूप և स्टॅक वापरून पुनरावृत्ती न करता चालवावे. याला पुनरावृत्ती वेगवान अल्गोरिदम म्हणून देखील ओळखले जाते.

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

/**
 * Java Program to implement Iterative QuickSort Algorithm, without recursion.
 *
 * @author WINDOWS 8
 */
public class Sorting {

    public static void main(String args[]) {

        int[] unsorted = {34, 32, 43, 12, 11, 32, 22, 21, 32};
        System.out.println("Unsorted array : " + Arrays.toString(unsorted));

        iterativeQsort(unsorted);
        System.out.println("Sorted array : " + Arrays.toString(unsorted));
    }


    /*
     * iterative implementation of quicksort sorting algorithm.
     */
    public static void iterativeQsort(int[] numbers) {
        Stack stack = new Stack();
        stack.push(0);
        stack.push(numbers.length);

        while (!stack.isEmpty()) {
            int end = stack.pop();
            int start = stack.pop();
            if (end - start < 2) {
                continue;
            }
            int p = start + ((end - start) / 2);
            p = partition(numbers, p, start, end);

            stack.push(p + 1);
            stack.push(end);

            stack.push(start);
            stack.push(p);

        }
    }

    /*
     * Utility method to partition the array into smaller array, and
     * comparing numbers to rearrange them as per quicksort algorithm.
     */
    private static int partition(int[] input, int position, int start, int end) {
        int l = start;
        int h = end - 2;
        int piv = input[position];
        swap(input, position, end - 1);

        while (l < h) {
            if (input[l] < piv) {
                l++;
            } else if (input[h] >= piv) {
                h--;
            } else {
                swap(input, l, h);
            }
        }
        int idx = h;
        if (input[h] < piv) {
            idx++;
        }
        swap(input, end - 1, idx);
        return idx;
    }

    /**
     * Utility method to swap two numbers in given array
     *
     * @param arr - array on which swap will happen
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

Output:
Unsorted array : [34, 32, 43, 12, 11, 32, 22, 21, 32]
Sorted array : [11, 12, 21, 22, 32, 32, 32, 34, 43]


एवढे पुनरावृत्तीशिवाय जावामध्ये क्विकॉर्ट कसे लागू करावे. फक्त लक्षात ठेवा की जेव्हा तुम्ही फास्ट प्रोग्राम कार्यान्वित करण्यासाठी लूप և स्टॅक वापरता, तेव्हा ते डुप्लिकेट अंमलबजावणी म्हणून ओळखले जाते; जेव्हा तुम्ही स्वतः पद्धतीला कॉल करता, तेव्हा ते पुनरावृत्ती अंमलबजावणी म्हणून ओळखले जाते.

क्विकॉर्ट पुनरावृत्ती समाधान लिहिणे आणि समजणे सोपे आहे, परंतु पुनरावृत्ती समाधान बरेच जलद आहे. सर्वात वाईट परिस्थितीत, वेळेची गुंतागुंत हे सरासरी प्रकरण O (N log N) ագույն O (n ^ 2) आहे.

बीटीडब्ल्यू, जर तुम्हाला वेगवेगळ्या वर्गीकरण अल्गोरिदमची वेळ जटिलता लक्षात ठेवायची असेल किंवा पुनरावलोकन करायचे असेल तर दिवस वेगवान, जा बहिणट, स्थापना क्रमवारी, रूट वर्गीकरण, सोलणे वर्गीकरण, किंवा बबल वर्गीकरण, येथे एक सुंदर स्लाइड आहे जी तुम्ही प्रिंट करू शकता և वापरू शकता.

वेळ -जागेची सतत गुंतागुंत

जर तुम्हाला प्रवेग किंवा इतर वर्गीकरण अल्गोरिदम बद्दल अधिक जाणून घ्यायचे असेल तर मी प्रयत्न केलेले आणि चाचणी केलेले सुचवतो किंवा वाचतो अल्गोरिदमची ओळख थॉमस एच. कॉर्मन द्वारे, जे मी – इतर अनेक प्रोग्रामरनी डेटा स्ट्रक्चरच्या मूलभूत गोष्टी शिकण्यासाठी वाचले आहेत – अल्गोरिदम.

वैकल्पिकरित्या, आपण एक नवीन परंतु अधिक मनोरंजक पुस्तक निवडू शकता ग्रोकिंग अल्गोरिदम आदित्य बरगावा यांनी, जे अनेक वास्तविक जगातील उदाहरणे आणि आकृत्यासह अल्गोरिदम स्पष्ट करतात. आपण नवशिक्या असल्यास, मी ग्रोकिंग अल्गोरिदम वर जाण्याची शिफारस करतो.