अनुकूलित बबल सॉर्ट (जावा)

Question

मैं जानना चाहता हूं कि मैं बबल प्रकार को कैसे अनुकूलित कर सकता हूं ताकि यह उन तत्वों को नज़रअंदाज़ कर सके जो पहले से ही पहले पास किए गए हैं।

Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**] 

हम देखते हैं कि [4,5,6] क्रमबद्ध क्रम में पहले से ही कर रहे हैं, इतना है कि यह अगले पास में यह 3 तत्वों का नजारा दिखता है कि मेरे कोड को संशोधित कर सकते हैं? (जिसका मतलब है कि सॉर्ट अधिक कुशल होगा?) क्या आप एक रिकर्सिव विधि सुझाते हैं?

public static void bubblesort(int[] a) { 
    for(int i=1; i<a.length; i++) { 
    boolean is_sorted = true; 

    for(int j=0; j<a.length; j++) { 
     if(a[j] > a[j+1]) { 
     int temp = a[j]; 
     a[j] = a[j+1]; 
     a[j+1] = temp; 
     is_sorted = false; 
     } 
    } 

    if(is_sorted) return; 
    } 
} 

आपके समय के लिए धन्यवाद!

Answer 1

सबसे पहले, आप एक बाहर के सीमा उपयोग कर सकते है:

for(int j=0; j<a.length; j++) { 
     if(a[j] > a[j+1]) { 

j == a.length-1 के लिए

, तो पाश हालत बल्कि j < a.length-1 होना चाहिए।

लेकिन, बुलबुला प्रकार में, आप जानते हैं कि k गुजरता के बाद, सबसे बड़ा k तत्वों सरणी के k पिछले प्रविष्टियों में हल कर रहे हैं, इसलिए पारंपरिक बुलबुला तरह

public static void bubblesort(int[] a) { 
    for(int i=1; i<a.length; i++) { 
    boolean is_sorted = true; 

    for(int j=0; j < a.length - i; j++) { // skip the already sorted largest elements 
     if(a[j] > a[j+1]) { 
     int temp = a[j]; 
     a[j] = a[j+1]; 
     a[j+1] = temp; 
     is_sorted = false; 
     } 
    } 

    if(is_sorted) return; 
    } 
} 

का उपयोग करता है अब, यह अभी भी होगा जब सरणी में सबसे बड़े तत्वों की लंबी क्रमबद्ध पूंछ होती है, तो बहुत सारे अनावश्यक पुनरावृत्तियों का पालन करें, कहें कि आपके पास k,k-1,...,1 पहले k तत्वों और k+1 से 100000000 के बाद क्रम में है। मानक बबल सॉर्ट k बार पूरे सरणी के माध्यम से (लगभग) पास करेगा।

लेकिन अगर आप याद है जहां आप अपने पिछले अदला-बदली करने, तुम्हें पता है कि कि सूचकांक के बाद, वहाँ क्रम में सबसे बड़ा तत्व हैं, तो

public static void bubblesort(int[] a) { 
    int lastSwap = a.length-1; 
    for(int i=1; i<a.length; i++) { 
    boolean is_sorted = true; 
    int currentSwap = -1; 

    for(int j=0; j < lastSwap; j++) { 
     if(a[j] > a[j+1]) { 
     int temp = a[j]; 
     a[j] = a[j+1]; 
     a[j+1] = temp; 
     is_sorted = false; 
     currentSwap = j; 
     } 
    } 

    if(is_sorted) return; 
    lastSwap = currentSwap; 
    } 
} 

पूरे के माध्यम से केवल एक पास के साथ ऊपर के उदाहरण को सॉर्ट होगा सरणी, और शेष केवल एक (लघु) उपसर्ग के माध्यम से गुजरता है।

बेशक, सामान्य रूप से, यह आपको अधिक नहीं खरीदता है, लेकिन फिर बबल प्रकार को अनुकूलित करना वैसे भी व्यर्थ अभ्यास है।

Answer 2

आपको आंतरिक लूप के लिए एक चर "आकार" का उपयोग करना चाहिए और इसे प्रत्येक चक्र में नवीनतम स्वैप तत्व में बदलना चाहिए। इस प्रकार आपका आंतरिक पाश नवीनतम "स्वैप किए गए" तत्व तक जाता है और शेष अनदेखा होता है (उर्फ उनके सही जगह में)। यानी

do { 
     int newsize =0; 
     for (int i = 1; i < size; i++) { 
      if (a[i - 1] > a[i]) { 
       int temp; 
       temp = a[i - 1]; 
       a[i - 1] = a[i]; 
       a[i] = temp; 
       newsize =i; 
      } 
     } 
     size = newsize; 
    } while (size > 0); 

Answer 3

public static Integer[] optimizedbubbleSort(Integer[] input){ 
    long startTime = System.nanoTime(); 
    boolean swapped = true; 
    for(int pass=input.length-1; pass>=0 && swapped; pass--){ 
     swapped = false; 
     for(int i=0; i<pass; i++){ 
      if(input[i]>input[i+1]){ 
       int temp = input[i]; 
       input[i] = input[i+1]; 
       input[i+1] = temp; 
       swapped = true; 
      } 
     } 
    } 
    System.out.println("Time taken for OPTIMIZED bubbleSort: "+(System.nanoTime() - startTime)); 
    return input; 
} 

Answer 4

public static void BubbleSorter(params int[] input){ 
     int newSize = input.Length-1, size = 0; 
     bool swap; 
     do 
     { 
      swap = false; 
      for (int j = 0; j < newSize; j++) 
      { 
       if (input[j] > input[j + 1]) 
       { 
        int temp = input[j + 1]; 
        input[j + 1] = input[j]; 
        input[j] = temp; 
        swap = true; 
        size = j; 
       } 
      } newSize = size; 
     } while (swap); 

     DisplayArrayElements(input); 
    } 

Answer 5

मैं एक विधि है कि शुरुआत और सरणी है कि पिछले छोरों में आदेश दिए गए हैं के अंत में भागों को छोड़कर द्वारा पुनरावृत्तियों की संख्या को कम कर तैयार की।

static int[] BubbleSortOptimized(int arr[]) { 
    int start = 0, stop = arr.length - 1, control = 0; 
    boolean ordered, nsCaught; 
    while (true){ 
     ordered = true; 
     nsCaught = false; 
     for (int i = start; i < stop; i++) { 
      if (i > 1) { 
       if (!nsCaught && arr[i-2] > arr[i-1]){ 
        ordered = false; 
        start = i-2; 
        nsCaught = true; 
       } 
      } 
      if (arr[i] > arr[i+1]){ 
       int hold = arr[i]; 
       arr[i] = arr[i+1]; 
       arr[i+1] = hold; 
       control = i; 
      } 
     } 
     System.out.println(Arrays.toString(arr)); 
     if (ordered) return arr; 
     stop = control; 
    } 
} 

लेकिन @Daniel Fischer के रूप में पहले के एक जवाब में कहा, it doesn't do a lot with larger arrays.