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.
.@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
--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
}
}