Not logged in. · Lost password · Register

Ezekiel15
Ezekiel15
Member since Oct 2015
182 posts
Subject: Vorschlag für Altklausur SS 15 - Aufgabe 7 (Sortieren) - MergeSort
Ich denke mein Code hier löst die Aufgabe komplett, (besteht meine TestCases). Da ich aber generell sehr selbstunsicher bin, stelle ich den Code noch nicht auf der Altklausuren Seite online. D.h. wer sich sicher ist,  dass mein Code funktioniert, darf gerne kommentieren bzw. dann die auf der AltklausurenSeite entsprechenden Code Teile online stellen. Ansonsten: Anregungen/Verbessunergsvorschläge sind immer auch gerne willkommen.

PS: Die System.out.println(), habe ich lediglich zur Kontrolle eingebaut, (für die Aufgabe keinen Belang)

public class MergeSortUsing4Lists {
    public static void mergeSortExtern(LinkedList<Integer> b) {
        assert b != null;
        assert b.size() > 0;

        LinkedList<Integer> b0 = new LinkedList<>();
        LinkedList<Integer> b1 = new LinkedList<>(b.subList(0, b.size() / 2));
        LinkedList<Integer> b2 = new LinkedList<>(b.subList(b.size() / 2, b.size()));
        LinkedList<Integer> b3 = new LinkedList<>();

        merge(1, b0, b1, b2, b3);

        b.clear();
        b.addAll(b0);
        b.addAll(b1);
    }

    public static void merge(int len, LinkedList<Integer> b0, LinkedList<Integer> b1, LinkedList<Integer> b2,
            LinkedList<Integer> b3) {
        LinkedList<Integer> target = b0; // alternating between b0 and b3

        do {
            System.out.println();
            System.out.println(b0);
            System.out.println(b1);
            System.out.println(b2);
            System.out.println(b3);
            System.out.println();
            int z1 = 0, z2 = 0; // counter for the already stored integers from
                                // b1/b2 till len

            // if possible, store integers from b1 AND b2
            while (!b1.isEmpty() && !b2.isEmpty() && z1 < len && z2 < len) {
                if (b1.getFirst() <= b2.getFirst()) {
                    target.addLast(b1.getFirst());
                    b1.removeFirst();
                    z1++;
                } else {
                    target.add(b2.getFirst());
                    b2.removeFirst();
                    z2++;
                }
            }

            // if there are still integers from b1
            while (!b1.isEmpty() && (b2.isEmpty() || z2 == len) && z1 < len) {
                target.addLast(b1.getFirst());
                b1.removeFirst();
                z1++;
            }

            // if there are still integers from b2
            while (!b2.isEmpty() && (b1.isEmpty() || z1 == len) && z2 < len) {
                target.addLast(b2.getFirst());
                b2.removeFirst();
                z2++;
            }

            target = target == b0 ? b3 : b0;

        } while (!b1.isEmpty() || !b2.isEmpty());
        // b3 is not empty => recursion call!
        if (!b2.isEmpty() || !b3.isEmpty()) {
            merge(2 * len, b1, b0, b3, b2);
        } else {
            System.out.println();
            System.out.println(b0);
            System.out.println(b1);
            System.out.println(b2);
            System.out.println(b3);
            System.out.println();
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> a = new LinkedList<Integer>(
                Arrays.asList(10, 2, 1, 7, 6, 9, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));

        // LinkedList<Integer> b = new LinkedList<Integer>(Arrays.asList(5, 8,
        // 4, 23, 24, 1, 2, 3, 7, 12, 3));

        mergeSortExtern(a);
    }
}
This post was edited 2 times, last on 2016-03-12, 11:39 by Ezekiel15.
Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
622 posts
+1 Ezekiel15
Ich habe mich gerade auch an der Aufgabe versucht. Danke für den Code! So konnte ich meine Variante gleich testen ;)

Ein paar Bedingungen konnte man bei dir einfacher schreiben, zumindest funktioniert es in dieser Form. Siehe Kommentare im Code.
Außerdem habe ich noch zwei weitere Test Cases hinzugefügt. Vor allem der mit einer ungeraden Anzahl von Elementen hinzugefügt hat bei mir noch einen Fehler aufgedeckt ;)

  1. public class MergeSortUsing4Lists {
  2.      public static void mergeSortExtern(LinkedList<Integer> b) {
  3.          assert b != null;
  4.          assert b.size() > 0;
  5.  
  6.          LinkedList<Integer> b0 = new LinkedList<>();
  7.          LinkedList<Integer> b1 = new LinkedList<>(b.subList(0, b.size() / 2));
  8.          LinkedList<Integer> b2 = new LinkedList<>(b.subList(b.size() / 2, b.size()));
  9.          LinkedList<Integer> b3 = new LinkedList<>();
  10.  
  11.          merge(1, b0, b1, b2, b3);
  12.  
  13.          b.clear();
  14.          b.addAll(b0);
  15.          b.addAll(b1);
  16.      }
  17.  
  18.      public static void merge(int len, LinkedList<Integer> b0, LinkedList<Integer> b1, LinkedList<Integer> b2,
  19.              LinkedList<Integer> b3) {
  20.          LinkedList<Integer> target = b0; // alternating between b0 and b3
  21.  
  22.          do {
  23.              System.out.println();
  24.              System.out.println(b0);
  25.              System.out.println(b1);
  26.              System.out.println(b2);
  27.              System.out.println(b3);
  28.              System.out.println();
  29.              int z1 = 0, z2 = 0; // counter for the already stored integers from
  30.                                  // b1/b2 till len
  31.  
  32.              // if possible, store integers from b1 AND b2
  33.              while (!b1.isEmpty() && !b2.isEmpty() && z1 < len && z2 < len) {
  34.                  // Wegen <= ist es stabil (hattest du richtig; nur als Anmkerung für die Leser im Wiki)
  35.                  if (b1.getFirst() <= b2.getFirst()) {
  36.                      target.addLast(b1.removeFirst()); // etwas kürzer: removeFirst() gibt das Element auch zurück
  37.                      z1++;
  38.                  } else {
  39.                      target.add(b2.removeFirst());
  40.                      z2++;
  41.                  }
  42.              }
  43.  
  44.              // if there are still integers from b1
  45.  
  46.              // "!b2.isEmpty() && z2 < len" reicht als Bedingung aus, denn beide können nicht gleichzeitig noch Reste haben,
  47.              // denn dann wäre die while-Schleife oben noch ausgeführt worden.
  48.              while (!b1.isEmpty() && z1 < len) {
  49.                  target.addLast(b1.removeFirst());
  50.                  z1++;
  51.              }
  52.  
  53.              // if there are still integers from b2
  54.  
  55.              // Dasselbe Argument wie oben
  56.              while (!b2.isEmpty() && z2 < len) {
  57.                  target.addLast(b2.removeFirst());
  58.                  z2++;
  59.              }
  60.  
  61.              target = target == b0 ? b3 : b0;
  62.  
  63.          } while (!b1.isEmpty() || !b2.isEmpty());
  64.          // b3 is not empty => recursion call!
  65.  
  66.          // b2 ist an dieser Stelle sicher leer, sonst wäre obige do-while-Schleife noch ausgeführt worden
  67.          if (!b3.isEmpty()) {
  68.              merge(2 * len, b1, b0, b3, b2);
  69.          } else {
  70.              System.out.println();
  71.              System.out.println(b0);
  72.              System.out.println(b1);
  73.              System.out.println(b2);
  74.              System.out.println(b3);
  75.              System.out.println();
  76.          }
  77.      }
  78.  
  79.      public static void main(String[] args) {
  80.          LinkedList<Integer> a_empty = new LinkedList<Integer>();
  81.          mergeSortExtern(a_empty);
  82.  
  83.          LinkedList<Integer> a = new LinkedList<Integer>(
  84.                  Arrays.asList(10, 2, 1, 7, 6, 9, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
  85.  
  86.          mergeSortExtern(a);
  87.  
  88.          // odd number of elements (added number 19)
  89.          LinkedList<Integer> a_odd = new LinkedList<Integer>(
  90.                  Arrays.asList(10, 2, 1, 7, 6, 9, 19, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
  91.  
  92.          mergeSortExtern(a_odd);
  93.      }
  94.  }
Ezekiel15
Ezekiel15
Member since Oct 2015
182 posts
Fürs generelle Testen von Sorts habe ich mir eine Klasse geschrieben, die mir einen Array durchmischt. Das ist vielleicht auch ganz nützlich. Bei Gelegenheit/Notwendigkeit würde ich meine Klasse noch ausbauen..

PS: Wie fügst du Zeilennummerierung bei Code hinzu? code , /code in []-Klammern ändert bei mir erstaunlich wenig.

import java.util.Random;

public class ArrayShuffler<T> {

    public T[] shuffle(T[] t) {
        int len = t.length;
        Random r = new Random();
        for (int i = 0; i < len; i++) {
            int j = r.nextInt(len);
            swap(t, i, j);
        }
        return t;
    }

    private void swap(T[] t, int i, int j) {
        T temp = t[i];
        t[i] = t[j];
        t[j] = temp;
    }
}

Vielen Dank für deine Bemerkungen im Code!
This post was edited 2 times, last on 2016-03-12, 14:55 by Ezekiel15.
ic97usop
ehemals Chayyam
Member since Sep 2015
369 posts
Quote by Ezekiel15:
PS: Wie fügst du Zeilennummerierung bei Code hinzu? code , /code in []-Klammern ändert bei mir erstaunlich wenig.

Dafür soll man im Post nicht einfach nur "code", sondern "code=java" (jeweils in eckigen Klammern und ohne Anführungszeichen) verwenden.
Eine ruhige, sachliche und freundliche Arbeitsweise ist der Schlüssel zum Erfolg.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen