Sortierverfahren

[anfeanger01]

Hallo,

ich bin Java Anfänger und hänge derzeit an einer Aufgabe fest.

Und zwar soll das ganze so aussehen:

Sortieren Sie das folgende Feld mit 12 Werten.

98 23 77 33 76 24 95 18 76 23 66 11

Initial erhalten wir 6 Teilsequenzen mit je zwei Werten, die wir mit Sortieren durch Einfügen sortieren.

98 95 → 95 98
23 18 → 18 23
77 76 → 76 77
33 23 → 23 33
76 66 → 66 76
24 11 → 11 24

Dabei werden die Werte nicht umkopiert, sondern bleiben an Ihrer Stelle im Feld. Betrachten wir das ursprüngliche Feld, dann sehen wir

95 18 76 23 66 11 98 23 77 33 76 24

Nach dem Sortieren mit Abstand 3 von Feldern der Länge 4 erhalten wir

23 18 11 33 23 24 95 66 76 98 76 77

Nach dem Sortieren mit Abstand 1 von einem Feld der Länge 12 erhalten wir

11 18 23 23 24 33 66 76 76 77 95 98

Hinweis 3. Verwenden Sie als Datenstrukturen nur Grundtypen und Felder. Verwenden Sie nur static-Methoden. Vermeiden Sie globale Variablen (Klassenvariablen). Versuchen Sie unnötige Speicherallokation zu vermeiden. Importieren Sie adstool.jar als einzige JAR-Datei in Ihr Pro- jekt. Für die Analysen ist es sinnvoll und ausreichend handschriftliche Anlagen zu verwenden.

Für mich sieht es aus wie ein MergeSort, oder liege ich da falsch? Bei dem wird ja quasi das Array geteilt, wobei in dieser Aufgabe nur die Werte geteilt werden sollen und eben nicht das Array. Dies umzusetzen fällt mir sehr schwer. Ich weiß, dass ich das Array mit den Werten implementieren muss, sprich

int [] werte = {98, 23, 77, 33, 76, 24, 95, 18, 76, 23, 66, 11};

und als Variable bspw. int teilSequenz;

nun gehts an die Methode, die die Werte des Arrays eben in die teilSequenzen teilt und genau an dieser Stelle komme ich nicht weiter. Ich habe keine Ahnung wie diese Methode auszusehen hat, ich kann mir momentan auch noch nichts darunter vorstellen und im www finde ich auch nichts zu diesem Thema.

Ich würde mich freuen, wenn vielleicht jemand einen Tipp für mich hat.

Vielen Dank schon einmal und LG.

 

[Meniskusschaden]

Für mich sieht es aus wie ein MergeSort, oder liege ich da falsch?

Für mich sieht das eher nach Shellsort aus. Das würde ich mir mal ansehen.

 

[mihe7]

Für mich sieht es aus wie ein MergeSort, oder liege ich da falsch?

Das ist Shellsort (https://de.wikipedia.org/wiki/Shellsort)

Dies umzusetzen fällt mir sehr schwer.

Das ist Sinn und Zweck der Sache.

nun gehts an die Methode, die die Werte des Arrays eben in die teilSequenzen teilt

Brauchst Du in der Form nicht. Du musst nur geschickt durch dass Array "springen".

 

[anfeanger01]

Vielen Dank schonmal an euch beide @Meniskusschaden @mihe7.

Wie programmiert man das denn, ohne ein bestimmtes, bzw in dem Fall ShellSort, zu benutzen?

ich habe bisher

import de.medieninf.ads.ADSTool;





public class Aufg2 extends ADSTool.Sort {


    





    public static void main(String[] args) {  


        


        int [] sortiert = {98, 23, 77, 33, 76, 24, 95, 18, 76, 23, 66, 11};


        


        sortieren(sortiert);
        printArray(sortiert);


    }



        public static int[] sortieren(int[] werte) {
            for(int i = 0; i < werte.length/2; i++) {
                int teilSequenzen = i;
                for(int j = werte.length; j < werte.length; j--) {
                    if(werte[j] < werte[i]) {
                        teilSequenzen = j;
              }
       } 
 }


            return werte; 
}

  public static void printArray(int[] werte) {
      for(int i = 0; i < werte.length; i++) {
         System.out.println(werte[i]);
   }

  }

 @Override
 public void sort(int[] arg0) {
 // TODO Auto-generated method stub

    }

        }

        }

denn, ich muss ja das array bzw die werte halbieren?
oder seh ich das falsch? Der Code funktioniert einfach gar nicht..

 

[mihe7]

denn, ich muss ja das array bzw die werte halbieren?

Wenn das Problem zu schwer ist, musst Du es in einfachere teilen. Dazu sind Zettel und Stift hilfreich.

Du hast ein Array und einen Abstand. Der Abstand gibt an, welche Elemente im Array "zusammengehören".

Index  0  1  2  3  4  5  6  7  8  9 10 11
Werte 98 23 77 33 76 24 95 18 76 23 66 11

Jetzt überlegst Du Dir, wie es aussieht, wenn Du bei Index 0 mit einem Abstand von 6 beginnst:

Index  0  1  2  3  4  5  6  7  8  9 10 11
Werte 98 23 77 33 76 24 95 18 76 23 66 11
       ^                 ^                 ^
       |        6        |        6        |
       |<--------------->|<--------------->|

Du beginnst also bei Index 0. Index 0 ist ein gültiger Index, so dass Du den Wert im Array an Index 0 verwenden kannst. Dann addierst Du den Abstand zum Index und erhältst als neuen Index 6. Index 6 ist ebenfalls ein gültiger Index, so dass Du den Wert im Array an Index 6 verwenden kannst . Dann addierst Du den Abstand zum Index und erhältst als neuen Index 12. Index 12 ist kein gültiger Index mehr. Ab hier macht es keinen Sinn weiter zu machen. BTW: "verwenden kannst" hat hier keine nähere Bedeutung. Es geht erst einmal nur darum, sich den Algorithmus für die Bildung der "Teilarrays" zu überlegen.

D. h. wenn Du bei Index 0 beginnst, wählst Du die Indizes {0, 6} und dem entsprechend die Werte {98, 95} aus.

Wie gehts weiter? Klar, mit Index 1. Gleiches Spiel:

Index  0  1  2  3  4  5  6  7  8  9 10 11
Werte 98 23 77 33 76 24 95 18 76 23 66 11
          ^                 ^                 ^
          |        6        |        6        |
          |<--------------->|<--------------->|

Das treibt man eine Zeit lang, bis man bei Index 5 angelangt ist:

Index  0  1  2  3  4  5  6  7  8  9 10 11
Werte 98 23 77 33 76 24 95 18 76 23 66 11
                      ^                 ^                 ^
                      |        6        |        6        |
                      |<--------------->|<--------------->|

Dadurch wird klar: wenn Du jetzt bei 6 weitermachen würdest, würde das "Teilarray" nur noch aus einem Wert bestehen und dieser wäre außerdem bereits in dem Teilarray vorhanden, das Du bei Index 0 erhalten hast: {98, 95} enthält 95.

Das spielst Du mal mit Abstand 3 durch. Wie gesagt: es geht erstmal darum, die Bildung der Teilarrays zu verstehen. Dann kannst Du dafür mal einen Algorithmus formulieren.

Wenn Du das hast, kannst Du Dir mal Gedanken machen, wie Insertionsort funktioniert.