In java, what is the best way to sort an integer array if only the last number item is displaced?

Question

It's an array of integers. It was created this way: No element is repeated. Every time an element is added, its number is the next available integer, from 0 onwards. This way, if you add 6 elements in a row, they will be 0, 1, 2, 3, 4, 5, in that order. If you delete an element, the array shrinks, and a 'hole' is left between two of the elements, they are no longer consecutive because of that gap: 0, 1, 3, 4, 5. Then comes the problem: if you add a new element, it gets added to the end, but has the next available integer. So, the array is now 0, 1, 3, 4, 5, 2. It needs to be sorted, so the 2 can occupy its place between the 1 and the 3. What is the best way to do it? I have thought of several methods. The list is nearly ordered, and it has the property that, when it is ordered, every element is equal to or greater than its index in the array. I am currently doing a bubble sort (don't laugh), i think quick sort is overkill, i dont want to go recursive or use temporary arrays, and i dont want to change the add-element method (which adds the element at the end), so it must be sorted immediately after adding an element (so only the last element is out of place)

Answer 1

Take the last element and do a insertion sort.

Answer 2

What about using a java.util.BitSet instead? You'd get constant-time insertion and removal (finding the first free place will still take O(n) though). And with nextSetBit, you can iterate over the set in ascending order. With nextClearBir(), finding the first unused index becomes trivial, too.

Answer 3

Maybe you should look at the idea of Insertion Sort.

Answer 4

You do not need to sort the whole list, just insert the last element in order:

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

Are you constrained to use an array? If not, then just use a TreeSet. Why write your own sort algorithm when you can make use of standard libraries that perform this function already? It has guaranteed O(log(n)) time for 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()] );