Bubblesort ohne Array

Diskutiere Bubblesort ohne Array im Java Basics - Anfänger-Themen Bereich.
Bitte aktiviere JavaScript!
M

matrosehahn

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

Tarrew

Ja, mit Listen.

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

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_Sike

Kirby_Sike

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

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???
 
A

abc66

@affot Nix.

@Kirby_Sike
Java:
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_Sike

Kirby_Sike

@affot Nix.

@Kirby_Sike
Java:
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 :)
 
A

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. :(
 
T

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

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





Java:
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;
    }
}
Java:
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;
    }
}
Java:
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();
    }
}
 
A

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

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

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

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.
 
Zuletzt bearbeitet:
A

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):
Java:
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...
 
Blender3D

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.
Java:
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);
    }
}
Java:
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;
    }
}
 
Blender3D

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

abc66

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

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

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

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

Bubblesort ohne Array

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben