Sortieralgorithmus

Svenja325

Mitglied
Hallo,
ich versuche gerade mergesort zu implementieren. Das ist mein Versuch:
Java:
public static <T extends Comparable<? super T>> void sort( List<T> list) {
        
        mergesort(list,0, list.size()-1);
        
    }   
        private static <T extends Comparable<? super T>> void mergesort (List<T> list, int p, int q) {
            
            if(q-p<1) return;
            int middle= (q+p)/2;
            mergesort(list,p,middle);
            mergesort(list, middle+1,q);
            merge(list, p,middle,q);
            
        }
        private static <T extends Comparable<? super T>> void merge (List<T> list, int p, int middle, int r) {
            
            List<T> left=new ArrayList<T>();
            List<T> right=new ArrayList<T>();
            
            for(int i=0; i<middle-p+1;i++) left.add(i, list.get(p+i));
            for(int i=0; i<r-middle;i++) right.add(i, list.get(middle+i+1));
            
            int leftindex=0;
            int rightindex=0;
            
            for(int i=p; i<r;i++) {
                if(left.get(leftindex).compareTo(right.get(rightindex))<0)
                    list.set(i, left.get(leftindex++));
                else  list.set(i, right.get(rightindex++));
                }
                
            }

Eingabe:
[4, 2, 2, 8]
Ausgabe:
[2, 2, 2, 8]


Sieht vllt jmd das Problem. Ich würde mich sehr freuen:)
 
X

Xyz1

Gast
Der Code ist total vermurkst... Ich vermute dass er nicht stabil ist. Hier is mein Versuch:

Java:
  public static <T extends Comparable<? super T>> void sort(List<T> list) {

    mergesort(list, 0, list.size() - 1);

  }

  private static <T extends Comparable<? super T>> void mergesort(List<T> list, int p, int q) {

    if (q - p < 1)
      return;
    int middle = (q + p) / 2;
    mergesort(list, p, middle);
    mergesort(list, middle + 1, q);
    merge(list, p, middle, q);

  }

  private static <T extends Comparable<? super T>> void merge(List<T> list, int p, int middle, int r) {

    System.out.println(p + " " + middle + " " + (middle + 1) + " " + r);

    List<T> left = new ArrayList<T>();
    List<T> right = new ArrayList<T>();

    for (int i = p; i <= middle; i++)
      left.add(list.get(i));
    for (int i = middle + 1; i <= r; i++)
      right.add(list.get(i));

    int ix = 0;

    for (int i = p; i <= r; i++) {
      if (left.isEmpty()) {
        list.set(ix++, right.remove(0));
      } else if (right.isEmpty()) {
        list.set(ix++, left.remove(0));
      } else {
        if (left.get(0).compareTo(right.get(0)) < 0)
          list.set(ix++, left.remove(0));
        else
          list.set(ix++, right.remove(0));
      }
    }

  }

  public static void main(String[] args) {
    List<Integer> li = IntStream.of(4, 2, 2, 8).boxed().collect(Collectors.toList());
    sort(li);
    System.out.println(li);
  }
 

mihe7

Top Contributor
Oder so:

Java:
    public static <T extends Comparable<? super T>>
            void sort(List<T> list) {
        mergesort(list, 0, list.size());
    }

    private static <T extends Comparable<? super T>> 
            void mergesort(List<T> list, int p, int q) {
        if (q - p > 1) {
            int m = (q+p)/2;
            mergesort(list, p, m);
            mergesort(list, m, q);
            merge(list, p, m, q);
        }
    }

    private static <T extends Comparable<? super T>>
            void merge(List<T> list, int p, int m, int q) {
        List<T> left = new ArrayList<>(list.subList(p, m));
        List<T> right = new ArrayList<>(list.subList(m, q));
        int l = 0, r = 0;
        for (int i = p; i < q; i++) {
            if (l < m - p && r < q - m) {
                if (left.get(l).compareTo(right.get(r)) < 0) {
                    list.set(i, left.get(l));
                    l++;
                } else {
                    list.set(i, right.get(r));
                    r++;
                }
            } else if (l < m - p) {
                list.set(i, left.get(l));
                l++;
            } else {
                list.set(i, right.get(r));
                r++;
            }
        }
    }
 
K

kneitzel

Gast
Sieht vllt jmd das Problem. Ich würde mich sehr freuen:)

Also ich meine zumindest ein Problem zu sehen. Im Merge prüfst Du nicht den index von dem linken und rechten part, Das sieht man beim Code von Tobias recht gut: Ist links denn noch ein Element? Wie kannst Du das linke mit dem rechten Element vergleichen, wenn es links oder rechts gar nichts mehr gibt?

Und dann nur meine Sichtweise zu dem ++ Operator: Alleine für sich ok, aber mitten in einer Operation würde ich das nicht verwenden. Der Part ist zwar in sich korrekt, aber ich empfinde es als unübersichtlich und schwer zu lesen.
 

Meniskusschaden

Top Contributor
Sieht vllt jmd das Problem.
Wenn du beim Merge-Schritt alle Elemente einer Hälfte verarbeitet hast, musst du auch noch die verbliebenen Elemente der anderen Hälfte verarbeiten. Das fehlt im Moment noch.

Da scheint noch ein kleiner Fehler im Merge-Schritt zu sein:
Java:
int ix = 0;
Das müsste meines Erachtens z.B. so aussehen:
Java:
int ix = p;
 
X

Xyz1

Gast
mihe, Dein Code funktioniert nicht:
Java:
  public static <T extends Comparable<? super T>> void sort(List<T> list) {

    mergesort(list, 0, list.size());

  }

  private static <T extends Comparable<? super T>> void mergesort(List<T> list, int p, int q) {

    if (q - p > 1) {
      int middle = (q + p) / 2;
      mergesort(list, p, middle);
      mergesort(list, middle, q);
      merge(list, p, middle, q);
    }

  }

  private static <T extends Comparable<? super T>> void merge(List<T> list, int p, int middle, int r) {

    System.out.println(p + " " + middle + " " + (middle + 1) + " " + r);

    List<T> left = new ArrayList<T>(list.subList(p, middle));
    List<T> right = new ArrayList<T>(list.subList(middle, r));

    int ix = 0;

    for (int i = p; i < r; i++) {
      if (left.isEmpty()) {
        list.set(ix, right.remove(0));
      } else if (right.isEmpty()) {
        list.set(ix, left.remove(0));
      } else {
        if (left.get(0).compareTo(right.get(0)) < 0)
          list.set(ix, left.remove(0));
        else
          list.set(ix, right.remove(0));
      }
      ix++;
    }

  }

  public static void main(String[] args) {
    List<Integer> li = new Random().ints(new Random().nextInt(50)).mapToObj(e -> e / (Integer.MAX_VALUE / 10))
        .collect(Collectors.toList());
    sort(li);
    System.out.println(li);
  }


Code:
0 1 2 2
2 3 4 4
0 2 3 4
4 5 6 6
7 8 9 9
6 7 8 9
4 6 7 9
0 4 5 9
[2, 2, 9, -7, -6, 9, -7, -6, 9]
 

Svenja325

Mitglied
Hallo,
danke für euere Rückmeldungen. Ich habe mich am Code von mihe7 orientiert. Den problematischen Teil habe ich dann so gelöst:

Java:
int leftindex=0;
            int rightindex=0;
            
            for(int i=p; i<=r;i++) {
                if(leftindex<middle-p+1 && rightindex<r-middle) {
                    if(left.get(leftindex).compareTo(right.get(rightindex))<0) {
                        list.set(i, left.get(leftindex));
                        leftindex++;
                    }   
                    else {
                        list.set(i, right.get(rightindex));
                        rightindex++;
                        }
                        
                }
                else if(leftindex<middle-p+1) {
                    list.set(i, left.get(leftindex));
                    leftindex++;
                    
                }
                else {
                    list.set(i, right.get(rightindex));
                    rightindex++;
                    
                }
        
            }


Ich hoffe, dass das mit den Indizes ok ist.
Und dann nur meine Sichtweise zu dem ++ Operator: Alleine für sich ok, aber mitten in einer Operation würde ich das nicht verwenden. Der Part ist zwar in sich korrekt, aber ich empfinde es als unübersichtlich und schwer zu lesen.
Das habe ich versucht, auch übersichtlicher zu gestalten:)
 
X

Xyz1

Gast
Was eher an Deinem ix liegt. Nimm stattdessen einfach i (oder wie @Meniskusschaden in #9 geschrieben hat, setz ix auch auf p
Sowas Blödes. Klar wie Kloßbrühe... Wieso konnte mir das nicht auffallen? Bin ich dumm?

Hier ist jetzt die an mihe angelehnte Version:
Java:
  public static <T extends Comparable<? super T>> void sort(List<T> list) {

    mergesort(list, 0, list.size());

  }

  private static <T extends Comparable<? super T>> void mergesort(List<T> list, int p, int q) {

    if (q - p > 1) {
      int middle = (q + p) / 2;
      mergesort(list, p, middle);
      mergesort(list, middle, q);
      merge(list, p, middle, q);
    }

  }

  private static <T extends Comparable<? super T>> void merge(List<T> list, int p, int middle, int r) {

    System.out.println(p + " " + middle + " " + (middle + 1) + " " + r);

    List<T> left = new ArrayList<T>(list.subList(p, middle));
    List<T> right = new ArrayList<T>(list.subList(middle, r));

    for (int i = p; i < r; i++) {
      if (left.isEmpty()) {
        list.set(i, right.remove(0));
      } else if (right.isEmpty()) {
        list.set(i, left.remove(0));
      } else {
        if (left.get(0).compareTo(right.get(0)) < 0)
          list.set(i, left.remove(0));
        else
          list.set(i, right.remove(0));
      }
    }

  }

  public static void main(String[] args) {
    List<Integer> li = new Random().ints(new Random().nextInt(50)).mapToObj(e -> e / (Integer.MAX_VALUE / 10))
        .collect(Collectors.toList());
    sort(li);
    System.out.println(li);
  }


Code:
0 1 2 2
3 4 5 5
2 3 4 5
0 2 3 5
5 6 7 7
8 9 10 10
7 8 9 10
5 7 8 10
0 5 6 10
10 11 12 12
13 14 15 15
12 13 14 15
10 12 13 15
15 16 17 17
18 19 20 20
17 18 19 20
15 17 18 20
10 15 16 20
0 10 11 20
[-9, -9, -8, -8, -7, -7, -7, -6, -6, -5, -4, -2, -2, -1, 2, 4, 8, 8, 9, 9]


Nur kostet remove() sehr viel Zeit, deswegen solltest Du das so machen wie @Meniskusschaden oder @mihe7 .
 

mihe7

Top Contributor
Ich hoffe, dass das mit den Indizes ok ist.
Ich habs jetzt nicht getestet aber zusammen mit Deinen sort und mergesort-Methoden sollte das so stimmen. Es geht ja nur darum, dass der jeweilige bis-Index bei Dir inklusive ist: middle gehört noch zur linken Seite und i geht bis einschließlich r, passt also.

Wieso konnte mir das nicht auffallen? Bin ich dumm?
Ich glaube, das lag am Freitag, den 13.: https://www.java-forum.org/thema/rekursion.185270/#post-1195378 :)

EDIT:
Nur kostet remove() sehr viel Zeit, deswegen solltest Du das so machen wie @Meniskusschaden oder @mihe7 .
Wobei eine LinkedList schon einiges bringen sollte.
 
X

Xyz1

Gast
Wobei eine LinkedList schon einiges bringen sollte
Das stimmt. Wenn es keine LinkedList sein soll, dann täte es auch eine ArrayDeque:


... Most ArrayDeque operations run in amortized constant time. Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove(), and the bulk operations, all of which run in linear time. ...

Demnach läuft auch removeFirst() in 1.
 

Ähnliche Java Themen

Neue Themen


Oben