Sortierverfahren raten

Mat

Aktives Mitglied
Bin letztens auf ein interessantes Sortierverfahren gestoßen. Ratet mal anhand des Ergebnisses, wie es heißen könnte:

Code:
Input:  [5, 44, 27, 56, 74, 98, 63, 6, 60, 46]
Output: [5, 44, 56, 74, 98]

Anwendungsbeispiel:
public static void main(String[] args) {
  Random rnd = new Random();
  int[] input = rnd.ints(10, 1, 100).toArray();

  System.out.println(Arrays.toString(input));
  System.out.println(Arrays.toString(sort(input)));
}

Ihr könnt euch auch überlegen, wie der Algorithmus dazu aussehen könnte. Oder meinen Implementierungsversuch ansehen:
Java:
private static int[] sort(final int[] input) {
  int n = input.length;
  if (n <= 1)
    return input;

  int[] output = new int[n];

  int cmpElem = input[0];
  int pointer = 0;
  int outputPointer = 0;
  output[outputPointer++] = cmpElem;

  while (pointer < n - 1) {
    int nextElem = input[++pointer];

    if (cmpElem <= nextElem) {
      cmpElem = nextElem;
      output[outputPointer++] = cmpElem;
    }
  }

  return Arrays.copyOf(output, outputPointer);
}


Nein, das ist keine tägliche Adventskalenderaktion.. aber wäre mal eine Idee.
 
Ich würde es DeletionSort nennen :)
Gehe von links nach rechts durch die Eingabe durch und immer wenn man auf ein Element stößt, was nicht größer als das letzte Element ist, wird es entfernt.
 
Zurück
Oben Unten