Was ist falsch mit meinem binären Einfügecode?

Question

Ich bin ein Anfänger in Java versucht, eine Klasse zu erstellen, die die binäre Insertion Sortierung implementiert und zufällige Arrays der Datengrößen 50, 500, 5000, 50000 und 500000 sortiert.

Das Programm funktioniert gut, wenn ich implementiert es als Einfügesorte.

public double InsertionSort(long array[]) { 
      setType("Insertion Sort"); 
      long temp; 
      int y; 
      double numOfSwap = 0, numOfComparisons = 0; 
      double startTime = System.nanoTime(); 
      for (int x = 1; x < array.length; x++) { 
       temp = array[x]; 
       numOfSwap++; 
       y = x; 
       numOfComparisons++; 
       while ((y > 0)) { 
        numOfComparisons++; 
        if ((array[y - 1]) > temp) { 
         array[y] = array[y - 1]; 
         numOfSwap++; 
         y = y - 1; 
        } else 
         break; 
       } 
       array[y] = temp; 
       numOfSwap++; 
      } 
      double endTime = System.nanoTime(); 
      setSwap(numOfSwap/3); 
      setComparisons(numOfComparisons); 
      setTime(endTime - startTime); 
      return getTime(); 

     } 

Aber als ich versuchte, eine binäre Suche einzufügen, funktionierte es nicht mehr.

public double binaryInsertionSort(long array[], int value, int left, int right) { 
      setType("Binary Insertion Sort"); 
      long temp; 
      int y; 
      int left, right; 
      double numOfSwap = 0, numOfComparisons = 0; 
      double startTime = System.nanoTime(); 
      for (int x = 1; x < array.length; x++) { 
       temp = array[x]; 
       numOfSwqp++; 
       int left = y; 
       int right = x; 
       if (left>right) 
        return -1; 
       int middle = (left + right)/2; 
       if (array[middle] == value) 
        return middle; 
       numOfComparisons++; 
       else if (array[middle]>value) 
        return binaryInsertionSort(array, value,left, middle -1); 
       numOfComparisons++; 
       else 
        return binaryInsertionSort (array, value, middle +1, right); 
       numOfComparisons++; 
      } 
      double endTime = System.nanoTime(); 
      setSwap(numOfSwap/3); 
      setComparisons(numOfComparisons); 
      setTime(endTime - startTime); 
      return getTime(); 
     } 

Kann mir bitte jemand helfen, meinen Code zu reparieren?

Answer 1

Es gab Fehler in Ihrem Code. Ich habe sie korrigiert. Zu allererst Ihre left und right Variablen sind in dieser Zeile definiert: -

public double binaryInsertionSort(long array[], int value, int left, int right) 

warum sind wieder Sie sie innerhalb Methode Körper definieren. Also habe ich ihre Doppeldeklaration entfernt. Zweitens haben Sie den Wert left Variable y zugewiesen, was falsch war. Eigentlich müssen Sie den Wert y to links vergeben. Dritter Fehler in Ihrem Code war, dass Ihre Methodenaufrufe falsch waren. Sie haben binaryInsertionSort mit vier Parametern definiert, und Sie haben sie mit einem einzigen Parameter aufgerufen, also habe ich Ihre Methodenaufrufe wie folgt geändert:

sortTime = binaryInsertionSort (sortedArray, 10,20,30);

Rest waren kleine Fehler. Hier ist corect Code Ihrer `binaryInsertionSort Methode: -

public double binaryInsertionSort(long array[], int value, int left, int right) { 

setType("Binary Insertion Sort"); 

long temp; 

int y=0; 

//int left, right; 

double numOfSwap = 0, numOfComparisons = 0; 

double startTime = System.nanoTime(); 

for (int x = 1; x < array.length; x++) { 

temp = array[x]; 

numOfSwap++; 

y=left; 

right = x; 

if (left>right){ 
return -1; 
} 

int middle = (left + right)/2; 

if (array[middle] == value){ 

    numOfComparisons++; 
    return middle; 

} else if (array[middle]>value){ 

    numOfComparisons++; 
    return binaryInsertionSort(array, value,left, middle -1); 

} else{ 

    numOfComparisons++;  
    return binaryInsertionSort (array, value, middle +1, right); 
    } 

} 

double endTime = System.nanoTime(); 

setSwap(numOfSwap/3); 

setComparisons(numOfComparisons); 

setTime(endTime - startTime); 

return getTime(); 

} 
` 

Ich verschickte Sie korrigierte Code Ihres Programms abzuschließen. Überprüfen Sie Ihre Mailbox. Bestätigen Sie mich, ob Sie meine Antwort nützlich finden oder nicht. Happy Coding :)

Answer 2

Ihr binärer Einfüge-Sortiercode enthält zahlreiche Fehler, über die Ihr Compiler Sie informieren muss. Ihre erste Aufgabe sollte es sein, all diese zu verstehen und zu beheben. Alternativ dazu scheinen viele der Probleme mit dem Binäreinfügungssortiercode daraus zu entstehen, dass sie durch den Versuch entstanden sind, den Standard-Einfügesortiercode anzupassen. Ich empfehle stattdessen, die binäre Version von Grund auf neu zu implementieren. Implementieren Sie außerdem die Sortierung zuerst; Fügen Sie Instrumentierung hinzu (Vergleich und Swap-Zählungen), nachdem die Sortierung selbst funktioniert.

Darüber hinaus gibt es einige deutliche Merkwürdigkeiten im Code:

• es ist atypisch und nicht von Vorteil, eine beliebige Version von Insertionsort rekursiv zu implementieren.

• Ihr spezifischer Versuch einer rekursiven Implementierung macht sowieso keinen Sinn: Die Hauptschleife würde nur eine Iteration ausführen und der Code nach der Schleife wäre tot.

• Es ist schwer sicher, aber ich denke, Sie haben die ganze Idee der binären Einfügung sort falsch. Sie scheinen zu versuchen, das Array in Teile aufzuteilen, um diese rekursiv zu sortieren, wie eine Zusammenführungssortierung oder schnelle Sortierung, aber so funktioniert die Sortierung nach binärer Sortierung nicht. Die Sortierung von Binäreinträgen unterscheidet sich von der Sortierung nach Standardeinfügungen hauptsächlich dadurch, dass sie eine binäre Suche anstelle einer linearen Suche verwendet, um die Einfügeposition für jedes Element zu finden.