algorithm
Tri du cycle
Recherche…
Cycle Trier les informations de base
Cycle Sort est un algorithme de tri utilisant un tri comparatif qui est théoriquement optimal en termes de nombre total d'écritures dans le tableau d'origine, contrairement à tout autre algorithme de tri sur place. Le tri par cycle est un algorithme de tri instable. Il est basé sur l'idée de permutation dans laquelle les permutations sont prises en compte dans les cycles, qui font individuellement pivoter et renvoient une sortie triée.
Exemple de cycle Trier:
Espace auxiliaire: O(1)
Complexité temporelle: O(n^2)
Mise en œuvre du pseudocode
(input)
output = 0
for cycleStart from 0 to length(array) - 2
item = array[cycleStart]
pos = cycleStart
for i from cycleStart + 1 to length(array) - 1
if array[i] < item:
pos += 1
if pos == cycleStart:
continue
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
while pos != cycleStart:
pos = cycleStart
for i from cycleStart + 1 to length(array) - 1
if array[i] < item:
pos += 1
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
return outout
Implémentation C #
public class CycleSort
{
public static void SortCycle(int[] input)
{
for (var i = 0; i < input.Length; i++)
{
var item = input[i];
var position = i;
do
{
var k = input.Where((t, j) => position != j && t < item).Count();
if (position == k) continue;
while (position != k && item == input[k])
{
k++;
}
var temp = input[k];
input[k] = item;
item = temp;
position = k;
} while (position != i);
}
}
public static int[] Main(int[] input)
{
SortCycle(input);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
Sous licence CC BY-SA 3.0
Non affilié à Stack Overflow