Bubblesort ohne Array

[matrosehahn]

Hallo Leute ich muss als Projekt ein bubblesort Algorithmus schreiben ohne arrays zu verwenden hat einer eine Ahnung wie das funktionieren kann

 

[Tarrew]

Ja, mit Listen.

Mal ehrlich, du musst schon ein paar mehr Informationen liefern. In welcher Form liegen deine Elemente denn vor?

 

[matrosehahn]

Es sollen zwanzig Elemente die zufällig einen Wert von 1-9 vom Typ int bekommen. Jedes Element hat eine feste Reihe zugeordnet die dann nach der Größe sortiert werden soll das Programm soll aber ohne arrays und Listen auskommen.

 

[Kirby.exe]

Du könntest eine Datenstruktur coden, welche jeweils den Nachfolger Knoten kennt und Daten vom Typ int enthält, jedoch ist das eigentlich auch eine LinkedList.

 

[affot]

Jedes Element hat eine feste Reihe zugeordnet die dann nach der Größe sortiert werden soll das Programm soll aber ohne arrays und Listen auskommen.

Damit sind die beiden Möglichkeiten die mir einfallen ausgeschlossen... Was soll es denn sonst noch geben um Objekte anzuordnen???

 

[abc66]

@affot Nix.

@Kirby_Sike

import java.util.Iterator;

public class BS {
	public static class LL implements Iterable<Long> {
		public static class Elem {
			Elem a, b;
			long l;

			Elem(Elem a, Elem b, long l) {
				this.a = a;
				this.b = b;
				this.l = l;
			}
		}

		Elem a, b;

		void add(long l) {
			if (a == null) {
				a = new Elem(null, null, l);
				b = a;
			} else {
				Elem e = new Elem(b, null, l);
				b.b = e;
				b = e;
			}
		}

		@Override
		public Iterator<Long> iterator() {
			return new Iterator<Long>() {
				Elem c = a;

				@Override
				public boolean hasNext() {
					return c != null;
				}

				@Override
				public Long next() {
					long l = c.l;
					c = c.b;
					return l;
				}
			};
		}

		void bubblesort() {
			boolean sorted = false;
			while (!sorted) {
				sorted = true;
				Elem d = a;
				while (d.b != null) {
					if (d.l > d.b.l) {
						if (a == d) {
							a = d.b;
						}
						if (b == d.b) {
							b = d;
						}
						Elem c = d.a;
						Elem e = d.b;
						Elem f = e.b;
						// swap d and e
						if (c != null)
							c.b = e;
						if (f != null)
							f.a = d;
						e.a = c;
						e.b = d;
						d.a = e;
						d.b = f;
						sorted = false;
					} else {
						d = d.b;
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		LL list = new LL();
		list.add(3);
		list.add(2);
		list.add(2);
		list.add(1);
		list.iterator().forEachRemaining(l -> System.out.print(l + ", "));
		System.out.println();
		
		list.bubblesort();
		list.iterator().forEachRemaining(l -> System.out.print(l + ", "));
		System.out.println();
		
		list.add(2);
		list.add(0);
		list.iterator().forEachRemaining(l -> System.out.print(l + ", "));
		System.out.println();
		
		list.bubblesort();
		list.iterator().forEachRemaining(l -> System.out.print(l + ", "));
		System.out.println();
	}
}

doppelt verkettete Liste, in der Elem s nur ans Ende hinzugefügt werden können, eine leere Liste kann jedoch nicht sortiert werden

 

[Kirby.exe]

@affot Nix.

@Kirby_Sike

import java.util.Iterator;

public class BS {
    public static class LL implements Iterable<Long> {
        public static class Elem {
            Elem a, b;
            long l;

            Elem(Elem a, Elem b, long l) {
                this.a = a;
                this.b = b;
                this.l = l;
            }
        }

        Elem a, b;

        void add(long l) {
            if (a == null) {
                a = new Elem(null, null, l);
                b = a;
            } else {
                Elem e = new Elem(b, null, l);
                b.b = e;
                b = e;
            }
        }

        @Override
        public Iterator<Long> iterator() {
            return new Iterator<Long>() {
                Elem c = a;

                @Override
                public boolean hasNext() {
                    return c != null;
                }

                @Override
                public Long next() {
                    long l = c.l;
                    c = c.b;
                    return l;
                }
            };
        }

        void bubblesort() {
            boolean sorted = false;
            while (!sorted) {
                sorted = true;
                Elem d = a;
                while (d.b != null) {
                    if (d.l > d.b.l) {
                        if (a == d) {
                            a = d.b;
                        }
                        if (b == d.b) {
                            b = d;
                        }
                        Elem c = d.a;
                        Elem e = d.b;
                        Elem f = e.b;
                        // swap d and e
                        if (c != null)
                            c.b = e;
                        if (f != null)
                            f.a = d;
                        e.a = c;
                        e.b = d;
                        d.a = e;
                        d.b = f;
                        sorted = false;
                    } else {
                        d = d.b;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        LL list = new LL();
        list.add(3);
        list.add(2);
        list.add(2);
        list.add(1);
        list.iterator().forEachRemaining(l -> System.out.print(l + ", "));
        System.out.println();
       
        list.bubblesort();
        list.iterator().forEachRemaining(l -> System.out.print(l + ", "));
        System.out.println();
       
        list.add(2);
        list.add(0);
        list.iterator().forEachRemaining(l -> System.out.print(l + ", "));
        System.out.println();
       
        list.bubblesort();
        list.iterator().forEachRemaining(l -> System.out.print(l + ", "));
        System.out.println();
    }
}

doppelt verkettete Liste, in der Elem s nur ans Ende hinzugefügt werden können, eine leere Liste kann jedoch nicht sortiert werden

Ich meinte es ähnlich xD Hab auch noch irgendwo eine double LinkedList rumliegen

 

[abc66]

Ist sogar stabil

/e Das Schlimme ist ja, dass bei einer double LinkedList beim Vertauschen 4 Elemente "umverkettet" werden müssen, das wird schnell zu Spaghetti Code.

 

[temi]

zwanzig Elemente die zufällig einen Wert von 1-9 vom Typ int bekommen. Jedes Element hat eine feste Reihe zugeordnet die dann nach der Größe sortiert werden soll das Programm soll aber ohne arrays und Listen auskommen.

Da es sich nur um einstellige Werte handelt, könnte man diese auch hintereinander in einem String anordnen.

 

[abc66]

Da es sich nur um einstellige Werte handelt, könnte man diese auch hintereinander in einem String anordnen.

Das wäre auch eine Liste. Es gibt keine andere Datenstruktur, in der Elem s einfach vertauscht werden können.

 

[abc66]

Siehe auch https://de.wikipedia.org/wiki/Datenstruktur#Speicher-_und_Rechenaufwand_von_Datenstrukturen

 

[Blender3D]

Es gibt keine andere Datenstruktur, in der Elem s einfach vertauscht werden können

Einfach nicht aber möglich z.B. ein Stack ist weder Liste noch Array.
Folgender Code liefert das Ergebnis.

import java.util.Random;

public class start {
    public final static Random rnd = new Random(System.currentTimeMillis());

    public static void main(String[] args) {
        ElementStack e = createRndElements();
        System.out.println(e);
        System.out.println("-------------");
        e.bubblesort();
        System.out.println(e);
    }

    static ElementStack createRndElements() {
        ElementStack elements = new ElementStack();
        String[] name = { "Hallo", "Jetzt", "Peter", "Susi", "Immer", "Test", "Auch", "Berg", "Stein" };

        for (int i = 0; i < name.length; i++) {
            int value;
            do {
                value = rnd.nextInt(9) + 1; // name.lenght has to be >= 9
            } while (!elements.push(new Element(name[i], value)));
        }
        return elements;
    }
}

public class Element {
    public final int value;
    public final String name;

    public Element(String name, int value) {
        this.name = name;
        this.value = value;
    }

    @Override
    public String toString() {
        return value + "\t" + name;
    }
}

import java.util.Stack;

public class ElementStack {
    private Stack<Element> elements = new Stack<Element>();

    /**
     * Push element to container. Constrain is that elements value is unique.
     *
     * @param e
     * @return true if successful
     */
    public boolean push(Element e) {
        for (Element element : elements) {
            if (element.value == e.value)
                return false;
        }
        elements.push(e);
        return true;
    }

    private void swap(int idA, int idB) {
        Element a = elements.get(idA);
        Element b = elements.get(idB);
        elements.remove(idA);
        elements.insertElementAt(b, idA);
        elements.remove(idB);
        elements.insertElementAt(a, idB);
    }

    public void bubblesort() {
        int cnt = elements.size();
        boolean swapped;
        do {
            swapped = false;
            for (int i = 0; i < cnt - 1; i++) {
                if (elements.get(i).value > elements.get(i + 1).value) {
                    swap(i, i + 1);
                    swapped = true;
                }
            }
            cnt--;
        } while (swapped);
    }

    public boolean isEmpty() {
        return elements.size() == 0;
    }

    @Override
    public String toString() {
        if (isEmpty())
            return "";
        StringBuffer str = new StringBuffer(elements.get(0).toString());
        for (int i = 1; i < elements.size(); i++) {
            str.append(System.lineSeparator());
            str.append(elements.get(i));
        }
        return str.toString();
    }
}

 

[abc66]

Nun ja, was ist Stack<Element> intern denn? Man könnte sagen, ein Baum oder eine Halde wäre auch nicht eine Liste oder ein Array, intern jedoch schon.

 

[Blender3D]

Man könnte sagen, ein Baum oder eine Halde wäre auch nicht eine Liste oder ein Array, intern jedoch schon.

Stimmt das ist dann aber immer so. Man könnte noch eine Datei wählen in die man schreibt. Im weitesten Sinne wäre das aber auch eine Liste oder ein Array.

 

[temi]

Da stellt sich dann irgendwann die Frage, wie die streng die Anforderung tatsächlich gemeint ist. Das sollte der TE dringend noch mal klären.

Ein Gedanke wäre noch long gewesen, aber der ist leider nicht groß genug für 20 Stellen.

 

[Blender3D]

Ein Gedanke wäre noch long gewesen, aber der ist leider nicht groß genug für 20 Stellen.

mit 3 Bits lassen sich Zahlen von 0-8 -> 1-9 darstellen.
3*20 = 60
Long hat 64 Bits
Aber die Bits sind im Speicher auch als Array von Bits vorhanden.

 

[abc66]

mit 3 Bits lassen sich Zahlen von 0-8 -> 1-9 darstellen.

Du meinst die Zahlen von einschließlich 0 bis einschließlich 7 (oder von 1 bis 8):

import java.util.Iterator;
import java.util.Spliterators;
import java.util.stream.Collectors;
import java.util.stream.StreamSupport;

public class BS {
	public static class LL implements Iterable<Long> {
		private static final int MAX = 20;
		private long inter = 0;

		public void set(int i, long v) {
			if (i < 0 || i >= MAX || v < 0 || v > 7) {
				throw new IllegalArgumentException();
			}
			for (int j = 0; j < i; j++) {
				v <<= 3;
			}
			unset(i);
			inter |= v;
		}

		public void unset(int i) {
			if (i < 0 || i >= MAX) {
				throw new IllegalArgumentException();
			}
			long v = 0b111;
			for (int j = 0; j < i; j++) {
				v <<= 3;
			}
			inter &= ~v;
		}

		public long get(int i) {
			if (i < 0 || i >= MAX) {
				throw new IllegalArgumentException();
			}
			long v = inter;
			for (int j = 0; j < i; j++) {
				v >>>= 3;
			}
			return v & 0b111;
		}

		public void swap(int i, int j) {
			if (i < 0 || i >= MAX || j < 0 || j >= MAX) {
				throw new IllegalArgumentException();
			}
			long v = get(i);
			set(i, get(j));
			set(j, v);
		}

		@Override
		public Iterator<Long> iterator() {
			return new Iterator<Long>() {
				int i = 0;

				@Override
				public boolean hasNext() {
					return i < MAX;
				}

				@Override
				public Long next() {
					long v = get(i);
					i++;
					return v;
				}
			};
		}

		public Iterator<Long> backwardIterator() {
			return new Iterator<Long>() {
				int i = MAX - 1;

				@Override
				public boolean hasNext() {
					return i >= 0;
				}

				@Override
				public Long next() {
					long v = get(i);
					i--;
					return v;
				}
			};
		}

		@Override
		public String toString() {
			String forward = StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator(), 0), false).collect(Collectors.toList()).toString();
			String backward = StreamSupport.stream(Spliterators.spliteratorUnknownSize(backwardIterator(), 0), false).collect(Collectors.toList()).toString();
			return forward + ", " + backward;
		}

		void bubblesort() {
			boolean sorted = false;
			while (!sorted) {
				sorted = true;
				int i = 0;
				while (i < MAX - 1) {
					if (get(i) > get(i + 1)) {
						swap(i, i + 1);
						sorted = false;
					}
					i++;
				}
			}
		}
	}

	public static void main(String[] args) {
		LL l = new LL();
		System.out.println(l);
		l.set(0, 7);
		l.set(2, 6);
		l.set(4, 7);
		l.set(19, 4);
		l.set(18, 5);
		l.swap(2, 4);
		System.out.println(l);
		l.bubblesort();
		System.out.println(l);
	}
}

/e Die toString Methode ist natürlich das pure Grauen...

 

[mihe7]

/e Das Schlimme ist ja, dass bei einer double LinkedList beim Vertauschen 4 Elemente "umverkettet" werden müssen, das wird schnell zu Spaghetti Code.

Tausch einfach wie Werte in den Elementen statt die Elemente

 

[abc66]

@mihe7 Das mach ich in meiner zweiten bubblesort Methode ja schon...

 

[mihe7]

Du meinst die aus #17? Da ist aber keine DLL im Spiel

 

[abc66]

Du meinst die aus #17? Da ist aber keine DLL im Spiel

Genau #17 meinte ich... Genau quasi keine DLL

 

[Blender3D]

Du meinst die Zahlen von einschließlich 0 bis einschließlich 7 (oder von 1 bis 8):

[0-8] lassen sich mit 3 Bits darstellen. Ich hätte das mit 2 integers anstatt einem Long gelöst. weil bei einer 32 Bit VM = Long dann zu kurz.

import java.util.Random;

public class start {
    public final static Random rnd = new Random(System.currentTimeMillis());

    public static void main(String[] args) {
        LongStack stack = new LongStack();
        for (int i = 0; i < 20; i++)
            stack.push(rnd.nextInt(9) + 1);
        System.out.println(stack);
        stack.bubblesort();     
        System.out.print(stack);
    }
}

public class LongStack {
    public final static int VALUE_MIN = 1;
    public final static int VALUE_MAX = 9;
    private final static int EMPTY = -1;
    private final static int MAX_ID = 19;
    private final static int BITS = 3;
    private final static int BLACK_MASK = 0b111;

    private int pos = EMPTY;
    private int dataLow = 0;
    private int dataHigh = 0;

    public void bubblesort() {
        int cnt = pos + 1;
        boolean swapped;
        do {
            swapped = false;
            for (int i = 0; i < cnt - 1; i++) {
                if (get(i) > get(i + 1)) {
                    swap(i, i + 1);
                    swapped = true;
                }
            }
            cnt--;
        } while (swapped);
    }

    private void checkEmpty() throws IllegalAccessError {
        if (isEmpty())
            throw new IllegalAccessError("Cant pop from empty stack!");
    }

    private void checkFull() throws IllegalAccessError {
        if (isFull())
            throw new IllegalAccessError("Cant push on full stack!");
    }

    private void checkRangeId(int id) {
        if (id < 0 || id > MAX_ID)
            throw new IllegalArgumentException("Id" + " not in range (" + 0 + "-" + MAX_ID + ")");
    }

    private void checkRangeValue(int value) {
        if (value < VALUE_MIN || value > VALUE_MAX)
            throw new IllegalArgumentException(
                    "Value <" + value + ">" + " not in range (" + VALUE_MIN + "-" + VALUE_MAX + ")");
    }

    public void clearAll() {
        dataLow = 0;
        dataHigh = 0;
        pos = EMPTY;
    }

    private boolean isEmpty() {
        return pos == EMPTY;
    }

    private boolean isFull() {
        return pos == MAX_ID;
    }

    public int pop() {
        checkEmpty();
        return (int) get(pos--) + 1;
    }

    public void push(int value) {
        checkFull();
        set(value, ++pos);
    }

    private int get(int id) {
        checkRangeId(id);
        int value = dataLow;
        if (id >= 10) {
            value = dataHigh;
            id = id % 10;
        }
        return (int) ((value >>> (id * BITS)) & BLACK_MASK) + 1;
    }

    private void set(int value, int id) {
        checkRangeValue(value);
        checkRangeId(id);
        int mask = value - 1;
        if (id >= 10) {
            id %= 10;
            mask <<= id * BITS;
            dataHigh &= ~(BLACK_MASK << (id * BITS));
            dataHigh |= mask;
        } else {
            mask <<= id * BITS;
            dataLow &= ~(BLACK_MASK << (id * BITS));
            dataLow |= mask;
        }
    }

    private void swap(int idA, int idB) {
        int tmp = get(idA);       
        set(get(idB), idA);
        set(tmp, idB);
    }

    public String toString() {
        if (isEmpty())
            return "empty";
        String str = "|";
        for (int i = 0; i <= pos; i++) {
            str += (get(i)) + "|";
            if (i == 9)
                str += "-|";
        }
        return str;
    }
}

 

[mrBrown]

[0-8] lassen sich mit 3 Bits darstellen.

Nein, wie schon korrekt gesagt nur 0-7.

 000b = 0
 111b = 7
1000b = 8

Wie willst du da die 8 anders darstellen?

Ich hätte das mit 2 integers anstatt einem Long gelöst. weil bei einer 32 Bit VM = Long dann zu kurz.

In Java hat ein long immer 64 Bit, ein int immer 32 Bit, völlig egal ob 32- oder 62-Bit JVM

 

[Blender3D]

In Java hat ein long immer 64 Bit, ein int immer 32 Bit, völlig egal ob 32- oder 62-Bit JVM

Interessant. Habe 32-Bit VM installiert und mit der Long Lösung durch die shift Operationen falsche Werte bekommen wenn ich mehr als 10 Werte gespeichert hatte 10*3 = 30Bits.
Unter 64 -Bit hats mit Long aber geklappt. Ich hatte auch 64 Bits in der 32 Bit VM bei Long. Eventuell ein Bug der VM ?
Deshalb habe ich Sicherheitshalber auf 2 Int umgestellt die Laufen auf beiden VMs.
Mein Code habe ich nur bei der get() und set() Methode für 2 ints angepasst.
Vielleicht weist Du wo mein grundlegender Fehler liegt.

 

[mihe7]

Habe 32-Bit VM installiert und mit der Long Lösung durch die shift Operationen falsche Werte bekommen wenn ich mehr als 10 Werte gespeichert hatte 10*3 = 30Bits.

Bitte um Code und Testfall.

 

[abc66]

Also mit 3 Bits können nur 8 Zahlen an der Zahl dargestellt werden... Anders ist das nicht möglich.

 

[abc66]

Wo ist @httpdigest eigentlich? Vielleicht hätte er für return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator(), 0), false).collect(Collectors.toList()).toString() + ", " + StreamSupport.stream(Spliterators.spliteratorUnknownSize(backwardIterator(), 0), false).collect(Collectors.toList()).toString(); eine Idee...?

 

[Meniskusschaden]

Also mit 3 Bits können nur 8 Zahlen an der Zahl dargestellt werden... Anders ist das nicht möglich.

Das stimmt. Allerdings muss man die Ziffern ja nicht unbedingt an exakt passenden Bitgruppen ausrichten. Man kann die 20-stellige Ziffernfolge ja auch als 20-stellige Zahl im Neuner-System auffassen. 9²⁰ ist kleiner als 2⁶⁴, also sollte das noch in eine long-Variable passen.

 

[mihe7]

Wo ist @httpdigest eigentlich?

Evtl. reboot?

 

[abc66]

Evtl. reboot?

Windows Update

 

[abc66]

@Blender3D

public final static int VALUE_MIN = 1; public final static int VALUE_MAX = 9; private final static int EMPTY = -1; private final static int MAX_ID = 19; private final static int BITS = 3; private final static int BLACK_MASK = 0b111; private int pos = EMPTY; private int dataLow = 0; private int dataHigh = 0;

Genau so etwas ist es, was mir auf der Arbeit Kopfschmerzen bereitet....