In java, what is the best way to sort an integer array if only the last element of the number is offset?

Question

This is an array of integers. It was created this way: No element is repeated. Each time an element is added, its number is the next available integer, starting at 0. Thus, if you add 6 elements to a string, they will be 0, 1, 2, 3, 4, 5 in that order. If you delete an element, the array is compressed, and the “hole” remains between the two elements, they are no longer consecutive because of this gap: 0, 1, 3, 4, 5. Then the problem arises: if you add a new element, it will be added at 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 it can take its place between 1 and 3. What is the best way to do this? I thought of several methods. The list is almost ordered, and it has the propertythat when it is ordered, each element is equal to or greater than its index in the array. I'm currently doing bubble sorting (don't laugh), I think the quick sort is overflowing, I don't want to go recursively or use temporary arrays, and I don't want to change the add-element method (which adds an element to end), so I need it sort right after adding an item (so only the last item is inappropriate)

Answer 1

Take the last item and sort the insert .

Answer 2

Maybe you should take a look at the idea of Insertion Sort .

Answer 3

, :

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 4

java.util.BitSet ? ( - O (n)). nextSetBit . nextClearBir() .

Answer 5

//based on gpeche 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 forbidden to use an array? If not, then just use TreeSet . Why write your own sorting algorithm when you can use standard libraries that already perform this function? It 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()] );