Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Sorting an array without actually changing the order of the elements

IgnatzIgnatz Mod
edited March 2013 in Code Sharing Posts: 5,396

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
Tagged:

Comments

  • Jmv38Jmv38 Mod
    Posts: 3,277

    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.

  • IgnatzIgnatz Mod
    Posts: 5,396

    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?

  • Jmv38Jmv38 Mod
    Posts: 3,277

    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.

  • Posts: 489

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

  • dave1707dave1707 Mod
    Posts: 6,935

    .@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
  • Jmv38Jmv38 Mod
    Posts: 3,277

    You've got it right Dave!

  • IgnatzIgnatz Mod
    Posts: 5,396

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

  • edited February 2 Posts: 1

    if its just printing here is a c code

    --modify it as per your needs
    int main()
    {
            int count;
            printf("enter no of elements\n");
            scanf("%d",&count);
            float array[count];
            printf("enter array elements\n");
            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\n",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\n",min1);
                    min=min1;                                   //update min element
            }       
    }
    
                                                                                                                             45,0-1        Bot
    
Sign In or Register to comment.