Sorting an array without actually changing the order of the elements

The code below gives you the sort order of an array without changing the order in the array itself, which can be quite useful.

For example, if you have an array a = {3,2,6,4,9,1}, then s = SortLinked(a) produces s = {6,2,1,4,3,5} ie item 6 in a is the smallest, then item 2, etc…

The sort algorithm is quick sort, which is usually the fastest.

function SortLinked(A)
    local switches
    local gap
    local Low
    local Num
    local hold
    local Low = 1
    local Num = #A
    local sList={}
    
    for ii = 1,Num do
      sList[ii] = ii
    end
    
    gap = Num - Low + 1
    repeat
      gap = math.floor((gap / 13) * 10)
      if gap < 1 then gap = 1 end
      if gap == 9 or gap == 10 then gap = 11 end
      switches = 0
      for ii = Low, Num - gap do
        if A[sList[ii]] > A[sList[ii + gap]] then
          sList[ii],sList[ii + gap]=sList[ii + gap],sList[ii]
          switches = 1
        end
      end
    until switches + gap == 1
    return sList
end

Interesting. When i need that info, i rather use the std lua sort() function on the table {{value,index}} like: {{3,1},{2,2},{6,3}, etc…} with the relevant comp(a,b) function. The sort should be faster, but the overhead to create/decode the table is higher, so i dont know which is faster.

I thought Lua always sorted the array elements. If there is a way to just get the sort order of an array without disturbing it, could you post an example for my education please?

My explanation was confusing: the elements are sorted and the order disturbed. But since the second field of each element in my table is the original index, i just have to read it once the table is sorted. My comment was not really important, it was just to show another way to achieve your goal: getting the sorted indexes. If i am still unclear and you are really interested, i will write an example.

Hello @Ignatz. This Section of Programming in Lua discussing the use of an iterator may be of interest.

.@Ignatz I was curious how it would be done using table.sort as suggested by @Jmv38. I’m not sure what I would use it for, but it I learned a few things trying to write it. So here is my version.


function setup()
    a={3,2,6,4,9,1}
    s=SortLinked(a)
    print("table a= ",table.concat(a," "))
    print("table s= ",table.concat(s," "))
end

function SortLinked(inTab)
    local w,s={},{}
    for x,y in pairs(inTab) do
        w[x]={}
        w[x][1],w[x][2]=x,a[x]
    end
    table.sort(w,function(a,b) return(a[2]<b[2]) end)
    for x,y in pairs(w) do
        table.insert(s,y[1])
    end
    return(s)
end

You’ve got it right Dave!

It’s faster than mine, too. I learn something every day, thanks for that.

if its just printing here is a c code

--modify it as per your needs
int main()
{
        int count;
        printf("enter no of elements\
");
        scanf("%d",&count);
        float array[count];
        printf("enter array elements\
");
        for(int i=0;i<count;i++)
        {
                scanf("%f",&array[i]);
        }
        float min,min1,max;
        min=array[0];
        max=array[0];
        min1=array[0];
        for(int i=0;i<count;i++)  //first find min and max out of array
        {
                if(array[i]<min)
                        min=array[i];
                if(array[i]>max)
                        max=array[i];
        }               
        printf("%f\
",min);
        while(min!=max)
        {
                for(int i=0;i<count;i++)
                {
                        if(array[i]!=min && array[i]>min)     //choose an element greater than already found min and not equal to min itself
                        {
                                min1=array[i];
                                break;
                        }
                }       
                for(int i=0;i<count;i++)
                {
                        if(array[i]<min1 && array[i]>min)    //with the choosen element in above loop find which is lowest out of array
                                min1=array[i];
                }               
                printf("%f\
",min1);
                min=min1;                                   //update min element
        }       
}
                                                                                                                         45,0-1        Bot