HeapSort für Array of Strings funktioniert nur teilweise

Balunal

Neues Mitglied
Hallo,
Ich habe als Aufgabe eine HeapSort Variante zu implementieren, die Strings aufsteigend sortiert. Ich habe mich daran versucht, der Sortieralgorithmus funktioniert jedoch nur teilweise. Wenn es maximal 11 Elemente sind gibt es kein Problem, danach werden nur die ersten 6 und die letzten 5 Elemente sortiert. Würde mich freuen wenn Ich diesbezüglich Hilfe bekommen könnte, gerne auch ein völlig anderer Lösungsansatz.
Mfg

PS:
Die Ausgabe der main wäre hier:
a b c d e f i h g j k l m n

Java:
[/B]
public class HeapSort {

    static int idx = -1;
    static String []heap = new String[1000];
    static void heapForm(String k){
        idx++;
        heap[idx] = k;
        int child = idx;
        String tmp;
        int index = idx / 2;

        while (index >= 0){
            if (heap[index].compareTo(heap[child]) > 0){
                tmp = heap[index];
                heap[index] = heap[child];
                heap[child] = tmp;
                child = index;

                index = index / 2;
            }
            else{
                break;
            }
        }
    }


    static void heapSort() {
        int left1, right1;

        while (idx >= 0) {
            String k;
            k = heap[0];

            System.out.print(k + " ");

            heap[0] = heap[idx];

            idx = idx - 1;
            String tmp;
            int index = 0;
            int length = idx;

            left1 = 1;
            right1 = left1 + 1;

            while (left1 <= length) {

                if (heap[index].compareTo(heap[left1]) <= 0 &&
                        heap[index].compareTo(heap[right1]) <= 0){
                    break;
                }


                else {
                    if (heap[left1].compareTo(heap[right1])< 0){
                        tmp = heap[index];
                        heap[index] = heap[left1];
                        heap[left1] = tmp;
                        index = left1;
                    }

                    else {
                        tmp = heap[index];
                        heap[index] = heap[right1];
                        heap[right1] = tmp;
                        index = right1;
                    }
                }


                left1 = 2 * left1;
                right1 = left1 + 1;
            }
        }
    }

    static void sort(String k[], int n) {

        for (int i = 0; i < n; i++) {
            heapForm(k[i]);
        }
        heapSort();
    }

    public static void main(String[] args)
    {
        String arr[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n" };
        int n = arr.length;
        sort(arr, n);
    }
}

[B]
 

Meniskusschaden

Top Contributor
Wenn du das letzte Heap-Element an die Wurzel geholt hast und es anschließend nach unten sinken lässt, berechnest du die Kindknoten auch dann aus dem linken Teilbaum, wenn es in den rechten Teilbaum ging.
 

Balunal

Neues Mitglied
Wenn du das letzte Heap-Element an die Wurzel geholt hast und es anschließend nach unten sinken lässt, berechnest du die Kindknoten auch dann aus dem linken Teilbaum, wenn es in den rechten Teilbaum ging.
Aber warum tritt das dann erst ab 11 Elementen auf? Und wie würdest du vorschlagen das zu lösen? Bin etwas ideenlos im Moment und weiß nicht, ob Ich einfach etwas offensichtliches im Code übersehe oder etwas an HeapSort missverstanden habe.
Aber vielen Dank für die Antwort schonmal :D
 

Meniskusschaden

Top Contributor
Aber warum tritt das dann erst ab 11 Elementen auf?
Das liegt vermutlich an den Beispieldaten. Ich habe das nicht weiter untersucht, weil mir inzwischen weitere Fehler aufgefallen sind: Deine Berechnung der Kindknoten bzw. Elternknoten passt für ein Array mit Startindex 1. Du verwendest jedoch Startindex 0 und müsstest die Formeln deshalb entsprechend anpassen. Dadurch könnte derzeit schon beim Einfügen eines Elementes die Heap-Bedingung verletzt werden.
Und wie würdest du vorschlagen das zu lösen?
Ich habe in folgender Grafik mal ein Beispiel dargestellt. Beim Übergang vom vorletzten zum letzten Baum passiert der Fehler, weil du dort nicht mehr die Kinder der neuen Position von D untersuchst, sondern die linken Enkel der vorherigen Position von D. Das musst du ändern.

Bildschirmfoto vom 2022-06-08 22-55-57.png
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Zrebna Bitte um Empfehlungen für "zeitlose" Bücher bzgl. Backend mit Spring und Beans Allgemeine Java-Themen 25
D Lesbare args für die main-Methode Allgemeine Java-Themen 6
B Algorithmus für Arbeit mit fehlenden Listenelementen? Allgemeine Java-Themen 1
kodela Eingabe für TextArray bedingt sperren Allgemeine Java-Themen 3
Karl_Der_Nette_Anfänger Hat wer ne Lösung für verknüpfte Postleitzahlen? (Baum/Wurzel Struktur) Allgemeine Java-Themen 11
R 11 GB File lesen ohne zu extrahieren Filedaten Bereich für Bereich adressieren dann mit Multi-Thread id die DB importieren Allgemeine Java-Themen 3
G KeyListener für JTextField Allgemeine Java-Themen 5
webracer999 Library für Textsuche (z. B. include/exclude, and/or)? Allgemeine Java-Themen 5
I Module-Info für Jar erzeugen Allgemeine Java-Themen 7
krgewb Java-Bibliothek für ONVIF Allgemeine Java-Themen 1
B Simpler Eventlistener für Tastaturtaste bauen? Allgemeine Java-Themen 13
_user_q Eingegebenen Text Zeile für Zeile ausgeben lassen Allgemeine Java-Themen 11
E Key für TOTP Algorythmus(Google Authentificator) Allgemeine Java-Themen 0
S Formel für Sonnenwinkel in ein Programm überführen Allgemeine Java-Themen 11
M pfx-Zertifikat in Tomcat für SSL-Verschlüsselung nutzen Allgemeine Java-Themen 14
R Best Practice Erfahrungswerte für eine Migration von JSF nach Angular (oder anderes JS-Framework) Allgemeine Java-Themen 1
jhCDtGVjcZGcfzug Klassen Was genau passiert hier? Kann mir das jemand bitte Zeile für Zeile erklären? Allgemeine Java-Themen 1
rosima26 Bester Sortieralgorithmus für kurze Arrays Allgemeine Java-Themen 40
S Mit Methoden kann man definieren für was <T> steht. Geht das auch irgendwie für Variablen? Allgemeine Java-Themen 12
MangoTango Operatoren while-Schleife für Potenz Allgemeine Java-Themen 3
B Lottospiel, genug Reihen tippen für 3 Richtige (Spaß mit Arrays)? Allgemeine Java-Themen 46
B Mit welchen Datentypen und Strukturierung am Besten dutzende Baccaratspiele Shcritt für Schritt durchsimulieren? Allgemeine Java-Themen 26
D Klassendesign für einen Pascal Interpreter Allgemeine Java-Themen 6
I OCR Library für Belegerkennung Allgemeine Java-Themen 7
farah GetterMathod für Farbkanäle Allgemeine Java-Themen 6
B Welcher Datentyp für sehr große Zahlenbereiche? Allgemeine Java-Themen 1
S Webservices für binäre Daten? Allgemeine Java-Themen 5
G Licence-Header für InHouse entwickelten Source Allgemeine Java-Themen 8
M Schleife für einen TicTacToe Computer Allgemeine Java-Themen 5
O git ignore für Intellji braucht es die .idea Dateien? Allgemeine Java-Themen 8
F Java Script für das Vorhaben das richtige? Allgemeine Java-Themen 9
M wiviel Java muss ich für die Berufswelt können ? Allgemeine Java-Themen 5
Robertop Datumsformat für GB ab Java 16 Allgemeine Java-Themen 1
Thallius Verschiedene entities für gleichen Code…. Allgemeine Java-Themen 8
OnDemand Zentrale "Drehscheibe" für verschiedene APIs Allgemeine Java-Themen 14
S Übergabe eines Sortierkriteriums für ein Artikel Array mittels BiPredicate<Artikel, Artikel> Allgemeine Java-Themen 13
F Streams als Alternative für dieses Problem ? Allgemeine Java-Themen 15
D SHA-3 für Java-version 1.8 Allgemeine Java-Themen 1
N Validator für einen SQL-Befehl Allgemeine Java-Themen 22
Muatasem Hammud Erstellung von Testdaten für Arrays Allgemeine Java-Themen 6
B Logikfehlersuche, das perfekte Lottosystem für 3 Richtige mit Arraylists? Allgemeine Java-Themen 61
G Methoden für die Zukunft sinnvoll? Allgemeine Java-Themen 4
M API für PLZ Umkreissuche Allgemeine Java-Themen 3
1Spinne JDK 8 für Eclipse installieren Allgemeine Java-Themen 5
Tobero Meine Funktion für das beinhalten eines Punktes in einem Kreis funktioniert nicht Allgemeine Java-Themen 5
L Methoden Parser für gängige Datumsformate? Allgemeine Java-Themen 1
H Interface PluginSystem ClassNotFound exception für library Klassen Allgemeine Java-Themen 10
N relativier Pfad für sqlite-Datenbank in Gradle/IntelliJ Allgemeine Java-Themen 2
buchfrau Anagram für beliebiges Wort Allgemeine Java-Themen 2
TonioTec Api für Datenaustausch zwischen Client und Server Allgemeine Java-Themen 0
W Suche Ursache für NPE - woher kommt sie? (Hilfe beim Debugging) Allgemeine Java-Themen 19
Kirby.exe Distanz Map für die Distanztransformation erstellen Allgemeine Java-Themen 1
F PI Regler für Heizung Allgemeine Java-Themen 7
8u3631984 Generelle Log4j.xml für alle Module Allgemeine Java-Themen 5
M Wie übergebe ich den Zähler für die Anzahl Rekursionsschritte korrekt? Allgemeine Java-Themen 2
B Login für User, der im Hintergrund Schedules ausführt Allgemeine Java-Themen 16
L RegEx für Teile einer Berechnung Allgemeine Java-Themen 14
S Java-Task-Management-Tool für Windows und Mac selber programmieren Allgemeine Java-Themen 4
M Java 2D Array für ein Grid erstellen ? Allgemeine Java-Themen 2
Z Welches GUI Framework für Java ist aktuell? Allgemeine Java-Themen 16
N Convert.FromBase64 von C# für Java Allgemeine Java-Themen 11
N fixed-keyword von C# für Java Allgemeine Java-Themen 6
O Suche Scripter für alt:V Project! Allgemeine Java-Themen 0
S Interface Design von HookUp oder Callback Methoden für eigenes Framework Allgemeine Java-Themen 9
O Suche Unterstützung für ein OpenSource-Projekt (grafischer Editor) Allgemeine Java-Themen 13
Kirby.exe Software für Graphische Visualisierung Allgemeine Java-Themen 20
B OOP Auslöser für NullPointerException Allgemeine Java-Themen 3
L Generator für einen Parser implementieren Allgemeine Java-Themen 13
DonMalte Ambitioniertes Projekt für Einsteiger & Motivierte Allgemeine Java-Themen 0
Kirby.exe Movement System für Spiel Allgemeine Java-Themen 13
Kirby.exe Framework für Game Design Allgemeine Java-Themen 8
W Alternative für Threads Allgemeine Java-Themen 6
S Rückgabe einer HttpURLConnection für eine Seite einlesen bei der man eingeloggt ist..? Allgemeine Java-Themen 5
Elyt Compiler-Fehler Datei kann nicht erstellt werden. Die Syntax für den Dateinamen etc. ist falsch. Allgemeine Java-Themen 2
Thallius Rätsel für Windows Profis Allgemeine Java-Themen 8
D OOP Gemeinsamen ID-Raum für zwei Klassen implementieren Allgemeine Java-Themen 7
D Input/Output Implementierung eines CommandHandlers/Parsers für viele Eingaben Allgemeine Java-Themen 26
Thallius Alternative für SwingWorker Allgemeine Java-Themen 5
I Lohnt sich heutzutage der Aufwand einer Portierung für MacOS Allgemeine Java-Themen 8
L Klassen Algorithmus für das folgende Problem entwickeln? Allgemeine Java-Themen 30
J Datenstruktur für eine Map erstellen Allgemeine Java-Themen 2
H OOP Setting(config) für Applikation sicheren? Allgemeine Java-Themen 9
OnDemand PDF Libary für Formulare Allgemeine Java-Themen 7
S Warmup für Lineare-Suche mit Zeitmessung Allgemeine Java-Themen 2
T Allgemeine Frage: GUI für 3D-Visualisierung Allgemeine Java-Themen 5
M Brainstorming für mein Projekt Allgemeine Java-Themen 30
K OOP Suche Hilfe + Erklärung für eine Hausaufgabe Allgemeine Java-Themen 1
F Was ist der Dateityp meines Parameters für die Main Methode. Allgemeine Java-Themen 6
C Bibliotheken für Algorithmische Geometrie Allgemeine Java-Themen 2
C Daten für Klassifikationsverfahren gewinnen Allgemeine Java-Themen 6
C code oder Bibliotheken für 2-Center Problem Allgemeine Java-Themen 4
I Overlay für Spiele Allgemeine Java-Themen 5
B Suche nach einem Testprogramm für meine BA Allgemeine Java-Themen 0
I GUI für kleine Pop-Ups unter Windows Allgemeine Java-Themen 1
A NetBeans Suche Programmierer für eine Belegarbeit Allgemeine Java-Themen 11
HarleyDavidson Best Practice Wohin mit der Konfigurationsdatei für Desktopapplikationen? Allgemeine Java-Themen 3
R MAC-Adresse eindeutig für einen PC ? Bezug zu Netzwerk, wieso ? Allgemeine Java-Themen 7
N Java API für CardDav und CalDav gesucht Allgemeine Java-Themen 4
R Idee für Methodenrumpf Allgemeine Java-Themen 5
O Suche größeres Beispiel für WebserverAnwendung mit Java Allgemeine Java-Themen 2

Ähnliche Java Themen


Oben