Lets say, I have an Array, and I want to sort that Array's indexes, while iterating the array. Array would not be modified, but the indexes would be put in sorted order according to the value of the Array's elements. Let me give you an example.
Array = [ 1, 7, 5, 4, 3, 8 ]
The sorted indexes would be,
SortedIndexes = [ 0, 4, 3, 2, 1, 5 ]
I want it such that after I have iterated the whole array, I already have those sorted indexes. Now, what would be the best way to do this.
You would start by creating an auxiliary array containing the indices of the main array, intitially in order. The auxiliary array is what you'll actually be sorting.
You could then combine an iteration over the main array with an insertion sort of the auxiliary array. For each index in your main iteration, you first perform whatever processing you want for your main operation, and then you perform the insertion step of the insertion sort in your auxiliary array. When you're done, the auxiliary array contains the sorted indices.
Insertion sort is a comparison sort, and hence its average and worst-case costs scale with N2, but it is among the best in that class. Its main advantage here is that it works in a manner that would integrate cleanly with your main iteration. If the data are not going to be enormous, then the scaling is probably not an issue. For smallish data, Insertion Sort might actually outperform some of the alternatives that scale better.
Merge sort does more moves but fewer compares than quick sort. In this case, the indexes are being moved, and the objects are being compared. The fact that the compare overhead for the objects involves one level of indirection (accessed via the indexes), and that the object compares will typically be randomly distributed and not cache friendly means that compare overhead is greater than index move overhead, in which case merge sort should be faster than quick sort.
Once you have an array of sorted indices, you can reorder the original array in place in O(n) time using a variation of cycle sort. This has the side effect of restoring the array of indexes back to 0 to n-1.
void reorder_according_to(int array[], size_t indices[], size_t len)
{
size_t i, j, k;
int t;
for(i = 0; i < len; i++){
if(i != indices[i]){
t = array[i];
k = i;
while(i != (j = indices[k])){
array[k] = array[j];
indices[k] = k;
k = j;
}
array[k] = t;
indices[k] = k;
}
}
}
SortedIndexeswith the current iteration value per iteration.O(n log n)limit applies to comparison sorts. But I deleted that comment.counting sortorradix sortproducing the required indexes in sorted order (without iterating the array more than once)?