En java, quelle est la meilleure façon de trier un tableau d'entiers si seul le dernier élément est déplacé?

Question

C'est un tableau d'entiers. Il a été créé comme suit: Aucun élément n'est répété. Chaque fois qu'un élément est ajouté, son numéro est l'entier disponible suivant, à partir de 0. De cette façon, si vous ajoutez 6 éléments dans une rangée, ils seront 0, 1, 2, 3, 4, 5, dans cet ordre. Si vous supprimez un élément, le tableau rétrécit et un 'trou' est laissé entre deux des éléments, ils ne sont plus consécutifs à cause de cet écart: 0, 1, 3, 4, 5. Puis vient le problème: si vous ajouter un nouvel élément, il est ajouté à la fin, mais a le prochain entier disponible. Donc, le tableau est maintenant 0, 1, 3, 4, 5, 2. Il doit être trié, donc le 2 peut occuper sa place entre le 1 et le 3. Quelle est la meilleure façon de le faire? J'ai pensé à plusieurs méthodes. La liste est presque ordonnée, et elle a la propriété que, quand elle est ordonnée, chaque élément est égal ou supérieur à son index dans le tableau. Je fais actuellement un tri à bulles (ne rigole pas), je pense que le tri rapide est trop rapide, je ne veux pas aller récursif ou utiliser des tableaux temporaires, et je ne veux pas changer la méthode add-element (qui ajoute l'élément à la fin), il doit donc être trié immédiatement après l'ajout d'un élément (donc seul le dernier élément est déplacé)

Answer 1

Prenez le dernier élément et effectuez un insertion sort.

Answer 2

Qu'en est-il de l'utilisation d'un java.util.BitSet à la place? Vous obtiendrez l'insertion et la suppression à temps constant (trouver la première place libre prendra quand même O (n)). Et avec nextSetBit, vous pouvez parcourir l'ensemble dans l'ordre croissant. Avec nextClearBir(), trouver le premier index inutilisé devient aussi trivial.

Answer 3

Peut-être que vous devriez regarder l'idée de Insertion Sort.

Answer 4

Vous n'avez pas besoin de trier la liste, il suffit d'insérer le dernier élément dans l'ordre:

int pos = array.length - 1: 
while (pos > 0 && array[pos] < array[pos - 1]) { 
    tmp = array[pos - 1]; 
    array[pos - 1] = array[pos]; 
    array[pos] = tmp; 
    pos--; 
} 

Answer 5

//based on gpeche's code 
int pos = array.length - 1; 
int val = array[pos]; 
while (pos > 0 && array[pos-1] > val) { 
    array[pos] = array[pos - 1]; 
    pos--; 
} 

array[pos] = val; 

Answer 6

Êtes-vous contraint d'utiliser un tableau? Si ce n'est pas le cas, utilisez simplement un TreeSet. Pourquoi écrire votre propre algorithme de tri lorsque vous pouvez utiliser des bibliothèques standard qui exécutent déjà cette fonction? Il a garanti O (log (n)) temps pour les insertions.

import java.util.TreeSet; 

TreeSet<Integer> sortedSet = new TreeSet<Integer>(); 
// Add integers as needed 
sortedSet.add(someInt); 
// If you need an array at the end 
Integer[] array = sortedSet.toArray(new Integer[sortedSet.size()]);