# Sortierverfahren



## anfeanger01 (22. Mai 2019)

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
> 
> ...



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 (22. Mai 2019)

anfeanger01 hat gesagt.:


> 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 (22. Mai 2019)

anfeanger01 hat gesagt.:


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


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



anfeanger01 hat gesagt.:


> Dies umzusetzen fällt mir sehr schwer.


Das ist Sinn und Zweck der Sache.



anfeanger01 hat gesagt.:


> 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 (22. Mai 2019)

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 (22. Mai 2019)

anfeanger01 hat gesagt.:


> 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.


----------

