जावा क्विक्सोर्ट क्यों मूल्य/कहां बदलते हैं?

Question

मैं अभी जावा में स्कूल सीख रहा हूं और हमारे नवीनतम विषय जावा में सॉर्ट एल्गोरिदम हैं। जिसे मैं समझने की कोशिश कर रहा हूं वह क्विकॉर्ट है।

यह समझने के लिए कि एल्गोरिदम एक सरणी में संख्याओं को कैसे प्रकार करता है, मैंने ग्रहण डीबगर विंडो में चरण के लिए अपने कोड चरण से गुज़रने का फैसला किया।

अब एक कदम था जिसे मैं सैकड़ों बार महसूस करने के बाद भी समझ नहीं पाया।

मेरे प्रारंभिक सरणी [10, 5, 3, 22, 11, 2]

जब मैं 10 और 2, तो 5 और 3 और फिर 2 और 2 स्वैप करके कोड कार्यक्रम शुरू होता माध्यम से जाना है। उस बिंदु पर i का मान 1 है और j का मान -1 है।

अब जिस तरह से मैं इसे देख तीन शर्तों

1. while(i<=j) कौन सा false रिटर्न देखते हैं कि है, क्योंकि i = 1 और j = -1

2. if(left < j) कौन सा false देता है, क्योंकि left = 0 और j = -1

3. if(i < right) जो भी false देता है, क्योंकि i = 1 और right = 1

लेकिन मेरे आश्चर्य करने के लिए जब कार्यक्रम right के लिए 40 if(i < right) लेकिन अचानक मूल्यों लाइन पिछले ब्रैकेट सही public static void display से पहले कार्यक्रम वापस छोड़ देता है करने के लिए हो जाता है, i, j और pivot5, 2, -1, और 3 से क्रमशः बदल गया है।

मैं बहुत आभारी हूं अगर कोई समझा सकता है कि मूल्य क्यों बदलते हैं।

मैं भी जो दिखाती हैं, जो मैं अपने ग्रहण खिड़की पर step I don't understand

public class QSort { 

    public static void quickSort(int[] arr, int left, int right){ 
     int i = left; 
     int j = right; 
     int temp; 
     int pivot = arr[(left+right)/2]; 
     System.out.println("\n\nleft = " + left + "\tright = " + right); 
     System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")"); 
     while(i <= j){ 
      while(arr[i] < pivot){ 
       System.out.println("i is: " + arr[i] + "(" + i + ")"); 
       i++; 
       System.out.println("i is: " + arr[i] + "(" + i + ")"); 
      } 
      while(arr[j] > pivot){ 
       System.out.println("j is: "+ arr[j] + "(" + j + ")"); 
       j--; 
       System.out.println("j is: "+ arr[j] + "(" + j + ")"); 
      } 
      if(i <= j){ 
       System.out.println("i is: " + arr[i] + "(" + i + ")"); 
       System.out.println("j is: "+ arr[j] + "(" + j + ")"); 
       System.out.println("Swapped " + arr[i] + "(" + i + ")"+ " with " + arr[j] + "(" + j + ")"); 
       temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 
       i++; 
       j--; 
       System.out.println("i is: (" + i + ")"); 
       System.out.println("j is: (" + j + ")"); 
       System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")"); 
      } 
     } 
     if(left < j){ 
      System.out.println("j is: (" + j + ")"); 
      quickSort(arr, left, j); 
     } 
     if(i < right){ 
      System.out.println("i is: (" + i + ")"); 
      quickSort(arr, i, right); 
     } 
    } 

    public static void display(int[] arr){ 
     if(arr.length > 0){ 
      System.out.print(arr[0]); 
     } 
     for(int i = 1; i < arr.length; i++){ 
      System.out.print(", " + arr[i]); 
     } 
    } 

    public static void main(String[] args) { 
     int[] data = new int[]{10,5,3,22,11,2}; 
     System.out.println("Before: "); 
     display(data); 
     quickSort(data, 0, data.length-1); 
     System.out.println("\nAfter: "); 
     display(data); 
    } 
} 

धन्यवाद एक बहुत देखते हैं दो तस्वीरें जोड़ लिया है!

Answer 1

मुझे लगता है कि आपकी समस्या यह है कि आप रिकर्सन को पूरी तरह समझ नहीं पाते हैं। कम से कम यही सवाल है कि यह आपके प्रश्न के विलुप्त होने से लगता है।

वैसे भी, मैंने सभी चरों का पता लगाकर बस अपने कार्यक्रम का पालन करने की कोशिश की है। आशा है कि इस मदद करता है: क्योंकि i<=j अब false (2 > 1) है

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[10,5,3,22,11,2] 0   5   
              0   5  arr[2] = 3 
[2,5,3,22,11,10]       1   4 
                3 
                2 
[2,3,5,22,11,10]       2   1 

जबकि पाश समाप्त हो गया है।

पहली शर्त left < j (0 < 1), true है ताकि आप quicksort फिर रिकर्सिवली फोन: quicksort(arr, 0, 1) - जिसका मतलब है कि तुम अब, सरणी [2,3] जो पहले से ही क्रमबद्ध हो जाता है को सॉर्ट तो कुछ नहीं होगा:

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[2,3,5,22,11,10] 0   1 
              0   1  arr[0] = 2 
                0 
[2,3,5,22,11,10]       1   -1 

जबकि लूप स्थिति अब false है। पहली स्थिति left < jfalse है (क्योंकि 0 > -1) और दूसरी स्थिति i < right भी झूठी है (क्योंकि 1 == 1) तो यह कॉल समाप्त हो गया है और आप वहां पर वापस लौट आए हैं। क्या वह थे? उपरोक्त तालिका की पहली शर्त। चर और पैरामीटर की स्थिति अब है:

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[10,5,3,22,11,2] 0   5   2   1  3 

दूसरी स्थिति की जांच की गई है (क्योंकि यह अगली पंक्ति निष्पादित है)। इसकी कीमत भी सच है क्योंकि स्थिति i < right (2 < 5) है। तो अब फिर से रिकर्सिवली quicksort कार्य करें: quicksort(arr, 2, 5) - अब आप सरणी [3,22,11,10] सॉर्ट जिसका अर्थ है:

arr     left  right  i   j  pivot 
----------------- ------- -------- ------- ----- ---------- 
[2,3,5,22,11,10]   2   5   
              2   5  arr[3] = 22 
              3 
[2,3,5,10,11,22]       4   4 
              5 

i > j अब तो हम थोड़ी देर के पाश से बाहर निकलें।

पहली शर्त left < j (2 < 4) true है, इसलिए हम आदेश [5,10,11] जो पहले से ही क्रमबद्ध हो जाता है को सॉर्ट करने में quicksort(arr, 2, 4) कहते हैं। मैं इस भाग को छोड़ दूंगा क्योंकि यह सरणी को बिल्कुल नहीं बदलता है।

जब रिकर्सिव कॉल किया जाता है, हम वापस लौटते हैं जहां हम थे और अब दूसरी स्थिति की जांच की जाएगी। i < right (5 < 5) false है और इसलिए हम कर चुके हैं।

मूल quicksort कॉल समाप्त हो गया है और सरणी क्रमबद्ध है।

Answer 2

पहली तस्वीर जो आपने दिखायी है वह डीबगर है, क्विकॉर्ट के दो पुनरावर्ती आविष्कारों के अंदर है: क्विकॉर्ट को मुख्य से बुलाया जाता है, और फिर लाइन 38 कॉल क्विकॉर्ट पर फिर से (यह क्विकॉर्ट का सिद्धांत है, यह एक पुनरावर्ती रणनीति है)। तो आप देखते हैं कि आप आंतरिक कॉल के लाइन 40 पर हैं, फिर जब आप वहां से कदम उठाते हैं, तो आप क्विकॉर्ट के पिछले आमंत्रण पर वापस जाते हैं (डीबगर आपको शीर्ष बाएं विंडो में तीन की बजाय दो लाइनों का ढेर दिखाता है) और आप पिवोट, आदि के पिछले मानों पर वापस आ गए हैं। सरणी को सभी रिकर्सिव इनवॉक्शंस के रूप में पास किया गया है, इसलिए इसे साझा किया गया है, लेकिन पूर्णांक चर नहीं हैं।

मुझे लगता है कि यह रिकर्सन है जो इसे समझना मुश्किल बनाता है, अपने कॉल स्टैक की जांच करें।

Answer 3

प्रिंट स्टेटमेंट और डीबगर का उपयोग करके सॉर्टिंग एल्गोरिदम का अध्ययन करने के आपके प्रयास सराहनीय हैं! लेकिन क्विक्सोर्ट का आपका वर्तमान कार्यान्वयन कम से कम शुरू में समझना मुश्किल है, क्योंकि इसमें दोनों पुनरावृत्ति और रिकर्सन चल रहा है (यानी आप लूप का उपयोग करते हैं और साथ ही, आपके पास एक प्रक्रिया quicksort स्वयं कॉलिंग है)।

चलिए Quicksort काम करता है और यह क्यों काम करता है यह देखने के लिए एक अलग दृष्टिकोण (पूरी तरह से पुनरावर्ती दृष्टिकोण) लेते हैं। इस पुनरावर्ती प्रक्रिया को एक पुनरावर्तक प्रक्रिया में परिवर्तित करना (कुछ हद तक आपने लिखा है) सौभाग्य से, तकनीक का मामला है (इस मामले में)! मैं प्रस्ताव करता हूं कि हम इसे यहां करें क्योंकि इस तरह हम जटिलता को बेहतर तरीके से नियंत्रित कर सकते हैं। दोबारा, कारण यह है कि मैं यह कर रहा हूं यह समझने के लिए कि पर क्या हो रहा है।

public static void qsort(int[] ints, int fi, int li) {       
    /* the recursive procedure */             
    if (fi < li) {                 
     int p = partition(ints, fi, li); // key routine -- see below           
     qsort(ints, fi, p - 1);              
     qsort(ints, p + 1, li);              
    }                    
    } 

यह है कि:

सर टोनी होरे एल्गोरिथ्म प्रस्तावित और इसकी सत्यता साबित हो गया, यह कुछ इस तरह था! सुंदर नहीं है? यह ठीक है। आप सब कुछ है:

• विभाजन दिया गया सरणी। मेरी आंखों में, विभाजन एक मुश्किल समस्या को हल करने के लिए एक सुरुचिपूर्ण प्रक्रिया है। समस्या सरल है: संख्याओं की एक सरणी को देखते हुए, सरणी को पुनर्व्यवस्थित करें जैसे कि इसमें कोई संख्या है, बाईं ओर की सभी संख्याएं इसके छोटे या उसके बराबर हैं और जिनके दाईं ओर सभी संख्याएं हैं इसके बराबर या उसके बराबर - सरणी में ऐसे तत्व की अनुक्रमणिका लौटाएं। मैं आपको इस समस्या को हल करने का प्रयास करने का आग्रह करता हूं। विकिपीडिया पर दी गई दोनों प्रक्रियाओं (लोमूटो और होरे) अच्छी तरह से काम करती हैं।
• एक बार जब आप सुनिश्चित करें कि आपके विभाजन की उम्मीद के रूप में काम कर रहे हैं, तो आप रिकर्सिवली तरह ही qsort प्रक्रिया का उपयोग कर दो विभाजन (पुनरावर्ती कॉल के आदेश करता नहीं बात) और आप कर लिया है!

मैं partition प्रक्रिया अपने आप को लागू करने की कोशिश की:

/** 
    Implements partitioning of array a from a[p] to a[r], leaves all the other elements of the array intact. 
    @param a the given int array 
    @param p int first index of the part of array to be partitioned 
    @param r int the second index of the part of array to be partitioned 
*/ 
    public static int partition(int[] a, int p, int r) { 
    //this is something I have written 
    int pivot = a[p]; 
    int i = p + 1; 
    int j = i - 1; 
    while (i <= r) { 
     if (a[i] < pivot) { 
     a[j] = a[i]; 
     a[i] = a[j+1]; 
     j++; 
     } 
     i++; 
    } 
    a[j] = pivot; 
    return j; 
    } 

    private static void swap(int[] ints, int i1, int i2) { 
    int tmp = ints[i2]; 
    ints[i2] = ints[i1]; 
    ints[i1] = tmp; 
    } 

अब, मैं अभी तक इस प्रक्रिया के शुद्धता साबित नहीं किया है, लेकिन हम चाहते हैं कि अलग-अलग कर सकते हैं। आप Lomuto procedure को भी कार्यान्वित कर सकते हैं और देख सकते हैं कि यह आपकी संतुष्टि के लिए काम करता है।

और यही वह है। यदि अब आप इसे डीबगर के साथ डीबग करना चाहते हैं, तो आप इसे करने के लिए सुसज्जित हैं। यहां entire implementation है।

अब, एक पुनरावृत्ति एक को यह पुनरावर्ती प्रक्रिया में परिवर्तित करने का सवाल बहुत ही दिलचस्प और इस दस्तावेज़ है: (बेशर्म प्लग: मैं इसे लिखा था) http://bit.ly/recurse-iterate आप कुछ सुराग देना चाहिए। उपरोक्त क्विक्सोर्ट प्रक्रिया का वास्तविक रूपांतरण एक पुनरावृत्त करने के लिए पाठक को अभ्यास के रूप में छोड़ दिया जाता है :-)।