Eigener Sortieralgorithmus

[keyvee]

Hallo!

Ich könnte eine Idee gebrauchen, wie ich meinen Algorithmus fertigstellen kann. Es geht um folgendes:

Gegeben ist ein Objekt mit Integer Werten. Erlaubt sind nur drei vorgegebene Operationen.
- .get(i) gibt das Element an der Stelle i zurück.
- .length() gibt die Anzahl an Elementen zurück
- .flip(i) dreht das Objekt (im Prinzip ein Array) bis zur Indexposition i um. Bsp:
{1,2,3,4}.flip(2) wird zu {3,2,1,4}

Im ersten Schritt geht man von einem Array der Länge i aus. Das Array ist bis zur Position i-1 sortiert (d.h. nur das letzte Element muss noch einsortiert werden). Dazu habe ich diesen Algorithmus aufgestellt:

    public void special_sort(SpecialArray arr) {
        arr.flip(arr.length()-1);
       
        for (int i = 2; i < arr.length(); i++){
            if (arr.get(i) < arr.get(0)){
                arr.flip(i-1);
                arr.flip(i-2);
            } else {
                arr.flip(arr.length()-2);
            }
        }
       
        arr.flip(arr.length()-1);
        System.out.println(arr.toString());

    }

Ich kann mir vorstellen, dass der so noch nicht durchlaufen wird. Aber das ist nicht mein Problem.
Wenn ich mit diesem Algorithmus ein Array einer beliebigen länge sortieren möchte, dann muss ich erstmal mit einem Element anfangen und das Array nach jedem Durchlauf um ein Element erweitern. Und genau hier komme ich nicht weiter. Ich habe ja nur die drei Operationen gegeben und kann nicht schreibend auf einen Index zugreifen und ich kann das Array auch nicht einfach kopieren.
Ich suche also nach einer Möglichkeit mein Array zuerst auf das erste Element zu begrenzen und dann immer um ein Element zu erweitern.

Ich hoffe ihr habt eine Idee

 

[kneitzel]

Also eine Möglichkeit, ein Array zu "begrenzen", ist einfach die Grenzen mitzugeben.

Statt nur dem Array gibst Du dann noch Start und Ende vor. Hier kann man ggf. noch Prüfen, dass 0 <= Start <= Ende und Ende <= Array.length -1 ist.

Und dann nutzt Du halt nur noch Start und Ende statt eben Konstanten wie 0 oder Array.length.

Konrad

 

[Jardcore]

Du könntest auch einen Heap verwenden (PriorityQueue in Java) und durch einen Comperator deine Sortierung übergeben.
Dann bräuchtest du keine eigene Datenstruktur konstruieren sondern hättest schon eine optimierte.

 

[KaffeeFan]

.length() gibt dir nicht die Anzahl an Elementen zurück