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.
 

LimDul79

Mitglied
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.
 
Oben Unten