Bubblesort ohne Array

Diskutiere Bubblesort ohne Array im Java Basics - Anfänger-Themen Bereich.
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