Dynamic Array QuickSort functions

[Sir Robin]

In this thread it was asked how to go about sorting a dynamic array. The OP wanted to sort an array of actors by each actor's distance3d to another specific actor.
I didn't know of any built-in function to do this and a search of the forums didn't find me anything so I wrote a small library of static functions in a class struct called ArraySort to do the job. Since it's all static functions and no instance variables, I changed the class to a struct. Not sure the exact difference but perhaps some reduced overhead?

Code: Select all

struct ArraySort
{
    //*************************************************************************
    //
    //    SHUFFLE FUNCTIONS
    //
    // This group of functions is for shuffling an array, the opposite of
    // sorting an array
    //
    //*************************************************************************

    // takes a list of doubles and reverses the order
    static void ReverseDouble(array<double> ValueList)
    {
        int iMax = ValueList.size() - 1;
        int iHalf = ValueList.size() / 2;
        for (int i = 0; i < iHalf; i++)
        {
            SwapDouble(ValueList, i, iMax - i );
        }
    }

    // takes a list of ints and reverses the order
    static void ReverseInt(array<int> ValueList)
    {
        int iMax = ValueList.size() - 1;
        int iHalf = ValueList.size() / 2;
        for (int i = 0; i < iHalf; i++)
        {
            SwapInt(ValueList, i, iMax - i );
        }
    }

    // takes a list of strings and reverses the order
    static void ReverseString(array<string> ValueList)
    {
        int iMax = ValueList.size() - 1;
        int iHalf = ValueList.size() / 2;
        for (int i = 0; i < iHalf; i++)
        {
            SwapString(ValueList, i, iMax - i );
        }
    }

    // takes a list of doubles and shuffles them
    static void ShuffleDouble(array<double> ValueList)
    {
        for (int i = 0; i < ValueList.size(); i++)
        {
            SwapDouble(ValueList, i, random(0, ValueList.size() - 1) );
        }
    }

    // takes a list of ints and shuffles them
    static void ShuffleInt(array<int> ValueList)
    {
        for (int i = 0; i < ValueList.size(); i++)
        {
            SwapInt(ValueList, i, random(0, ValueList.size() - 1) );
        }
    }

    // takes a list of strings and shuffles them
    static void ShuffleString(array<string> ValueList)
    {
        for (int i = 0; i < ValueList.size(); i++)
        {
            SwapString(ValueList, i, random(0, ValueList.size() - 1) );
        }
    }

    //makes a shuffled list of ints with specified values
    static void MakeShuffledInt(array<int> ValueList, int StartValue, int StopValue, int StepValue = 1)
    {
        if (!ValueList) return;
        
        ValueList.clear();
        
        // avoid infinite loops
        if ((StartValue == StopValue) || (StepValue == 0) || (StartValue < StopValue ? StepValue < 0 : StepValue > 0))
        {
            ValueList.push(StartValue);
            return;
        }

        //make a list of ints
        int v = StartValue;
        if (StepValue > 0)
        {
            while (v <= StopValue)
            {
                ValueList.push(v);
                v+=StepValue;
            }
        }
        else
        {
            while (v >= StopValue)
            {
                ValueList.push(v);
                v+=StepValue;
            }
        }
        
        //shuffle the list
        ShuffleInt(ValueList);
    }

    //makes a shuffled list of doubles with specified values
    static void MakeShuffledDouble(array<double> ValueList, double StartValue, double StopValue, double StepValue = 1.0)
    {
        if (!ValueList) return;
        
        ValueList.clear();
        
        // avoid infinite loops
        if ((StartValue == StopValue) || (StepValue == 0) || (StartValue < StopValue ? StepValue < 0 : StepValue > 0))
        {
            ValueList.push(StartValue);
            return;
        }

        //make a list of doubles
        double v = StartValue;
        if (StepValue > 0)
        {
            while (v <= StopValue)
            {
                ValueList.push(v);
                v+=StepValue;
            }
        }
        else
        {
            while (v >= StopValue)
            {
                ValueList.push(v);
                v+=StepValue;
            }
        }
        
        //shuffle the list
        ShuffleDouble(ValueList);
    }

    //*************************************************************************
    //
    //    SORT FUNCTIONS
    //
    // This group of functions is for sorting an array
    //
    //*************************************************************************

    // Pass this function an array of doubles and it will return that array
    // sorted alongside an array of original indices
    //
    //    on entry:
    //        ValueList: a list of doubles to to be sorted in ascending order
    //        IndexList: contents not important, will be cleared
    //    on exit:
    //        ValueList: a list of doubles sorted in ascending order
    //        IndexList: a list of indices pointing to locations in the original
    //            unsorted list
    static void SortDouble(array<double> ValueList, array<int> IndexList = null)
    {
        if (!ValueList) return;
        if (IndexList)
        {
            //make a list of indices, same size as the list of values
            IndexList.clear();
            IndexList.reserve(ValueList.size());
            for (int i = 0; i < ValueList.size(); i++)
            {
                //IndexList.push(i);
                IndexList[i]=i;
            }
            
            //quicksort the values and indices lists silmultaneously
            QuickSortDoubleIndex(ValueList, IndexList, 0, ValueList.size() - 1);
        }
        else
        {
            QuickSortDouble(ValueList, 0, ValueList.size() - 1);
        }
    }
    
    // Similar to above, except for a list of int values
    static void SortInt(array<int> ValueList, array<int> IndexList = null)
    {
        if (!ValueList) return;
        if (IndexList)
        {
            //make a list of indices, same size as the list of values
            IndexList.clear();
            IndexList.reserve(ValueList.size());
            for (int i = 0; i < ValueList.size(); i++)
            {
                //IndexList.push(i);
                IndexList[i]=i;
            }
            
            //quicksort the values and indices lists silmultaneously
            QuickSortIntIndex(ValueList, IndexList, 0, ValueList.size() - 1);
        }
        else
        {
            QuickSortInt(ValueList, 0, ValueList.size() - 1);
        }
    }
    
    // Similar to above, except for a list of int values
    static void SortString(array<string> ValueList, array<int> IndexList = null)
    {
        if (!ValueList) return;
        if (IndexList)
        {
            //make a list of indices, same size as the list of values
            IndexList.clear();
            IndexList.reserve(ValueList.size());
            for (int i = 0; i < ValueList.size(); i++)
            {
                //IndexList.push(i);
                IndexList[i]=i;
            }
            
            //quicksort the values and indices lists silmultaneously
            QuickSortStringIndex(ValueList, IndexList, 0, ValueList.size() - 1);
        }
        else
        {
            QuickSortString(ValueList, 0, ValueList.size() - 1);
        }
    }
    
    // Pass this function a list of actors and a reference point, it will sort
    // that list by their distance to the referencepoint.
    // Null entries in the list will be eliminated
    static void SortActorsByDistanceToPoint(array<actor> ActorList, vector3 ReferencePoint)
    {
        //create working lists
        array<double> ValueList;
        array<int> IndexList;
        
        //populate working lists
        for (int i = 0; i < ActorList.size(); i++)
        {
            if (ActorList[i])
            {
                ValueList.push( (ActorList[i].pos - ReferencePoint).length() );
                IndexList.push(i);
            }
        }

        //sort working lists
        QuickSortDoubleIndex(ValueList, IndexList, 0, ValueList.size() - 1);

        //create sorted list from original list and index list
        array<actor> ActorListSorted;
        For (Int i = 0; i < ValueList.size(); i++)
        {
            ActorListSorted.Push(ActorList[IndexList[i]]);
        }

        //replace original list with sorted list
        ActorList.move(ActorListSorted);
    }
    
    // Create a list of actors matching TID, then sort them by distance to the
    // ReferencePoint.
    static void SortTIDActorsByDistanceToPoint(int tid, vector3 ReferencePoint, array<actor> ActorList)
    {
        ActorList.clear();
        
        ActorIterator ai = level.CreateActorIterator(tid);
        actor mo;
        while (mo = ai.next())
        {
            ActorList.push(mo);
        }

        SortActorsByDistanceToPoint(ActorList, ReferencePoint);
    }
    
    //*************************************************************************
    //
    //    PRINT FUNCTIONS
    //
    // This group of functions is for printing an array, mostly for testing and
    // debug purposes.
    //
    //*************************************************************************

    static void PrintArrayDouble(array<double> ValueList, string Title = "ArrayDouble")
    {
        if (!ValueList)
        {
            console.printf(Title.." is null");
            return;
        }
        
        if (ValueList.size() == 1)
        {
            console.printf(Title.." has 1 element");
        }
        else
        {
            console.printf(Title.." has "..ValueList.size().." elements");
        }
        
        for (int i = 0; i < ValueList.size(); i++)
        {
            console.printf(Title.."["..i.."]="..ValueList[i]);
        }
    }

    static void PrintArrayInt(array<int> ValueList, string Title = "ArrayInt")
    {
        if (!ValueList)
        {
            console.printf(Title.." is null");
            return;
        }
        
        if (ValueList.size() == 1)
        {
            console.printf(Title.." has 1 element");
        }
        else
        {
            console.printf(Title.." has "..ValueList.size().." elements");
        }
        
        for (int i = 0; i < ValueList.size(); i++)
        {
            console.printf(Title.."["..i.."]="..ValueList[i]);
        }
    }

    static void PrintArrayString(array<string> ValueList, string Title = "string")
    {
        if (!ValueList)
        {
            console.printf(Title.." is null");
            return;
        }
        
        if (ValueList.size() == 1)
        {
            console.printf(Title.." has 1 element");
        }
        else
        {
            console.printf(Title.." has "..ValueList.size().." elements");
        }
        
        for (int i = 0; i < ValueList.size(); i++)
        {
            console.printf(Title.."["..i.."]="..ValueList[i]);
        }
    }

    //*************************************************************************
    //
    //    WORKER FUNCTIONS
    //
    // Functions below this line are for internal use. You won't need to call
    // them directly unless you are doing something specific and you know what
    // you're doing.
    //
    //*************************************************************************

    static void SwapDouble(array<double> ValueList, int index1, int index2)
    {
        double temp=ValueList[index1];
        ValueList[index1]=ValueList[index2];
        ValueList[index2]=temp;
    }

    static void SwapInt(array<int> ValueList, int index1, int index2)
    {
        int temp=ValueList[index1];
        ValueList[index1]=ValueList[index2];
        ValueList[index2]=temp;
    }

    static void SwapString(array<string> ValueList, int index1, int index2)
    {
        string temp=ValueList[index1];
        ValueList[index1]=ValueList[index2];
        ValueList[index2]=temp;
    }

    static void QuickSortDouble(array<double> ValueList, int low, int high)
    {
        if (low < high) {
            int pi = QuickSortPartitionDouble(ValueList, low, high);
            QuickSortDouble(ValueList, low, pi - 1);
            QuickSortDouble(ValueList, pi + 1, high);
        }
    }
    
    static int QuickSortPartitionDouble(array<double> ValueList, int low, int high)
    {
        double pivot = ValueList[high];

        int i = (low - 1);

        for (int j = low; j <= high- 1; j++)
        {
            if (ValueList[j] < pivot)
            {
                i++;
                SwapDouble(ValueList, i, j);
            }
         }
        SwapDouble(ValueList, i + 1, high);
        return (i + 1);
    }
    
    static void QuickSortDoubleIndex(array<double> ValueList, array<int> IndexList, int low, int high)
    {
        if (low < high) {
            int pi = QuickSortPartitionDoubleIndex(ValueList, IndexList, low, high);
            QuickSortDoubleIndex(ValueList, IndexList, low, pi - 1);
            QuickSortDoubleIndex(ValueList, IndexList, pi + 1, high);
        }
    }
    
    static int QuickSortPartitionDoubleIndex(array<double> ValueList, array<int> IndexList, int low, int high)
    {
        double pivot = ValueList[high];

        int i = (low - 1);

        for (int j = low; j <= high- 1; j++)
        {
            if (ValueList[j] < pivot)
            {
                i++;
                SwapDouble(ValueList, i, j);
                SwapInt(IndexList, i, j);
            }
         }
        SwapDouble(ValueList, i + 1, high);
        SwapInt(IndexList, i + 1, high);
        return (i + 1);
    }
    
    static void QuickSortInt(array<int> ValueList, int low, int high)
    {
        if (low < high) {
            int pi = QuickSortPartitionInt(ValueList, low, high);
            QuickSortInt(ValueList, low, pi - 1);
            QuickSortInt(ValueList, pi + 1, high);
        }
    }
    
    static int QuickSortPartitionInt(array<int> ValueList, int low, int high)
    {
        int pivot = ValueList[high];

        int i = (low - 1);

        for (int j = low; j <= high- 1; j++)
        {
            if (ValueList[j] < pivot)
            {
                i++;
                SwapInt(ValueList, i, j);
            }
         }
        SwapInt(ValueList, i + 1, high);
        return (i + 1);
    }
    
    static void QuickSortIntIndex(array<int> ValueList, array<int> IndexList, int low, int high)
    {
        if (low < high) {
            int pi = QuickSortPartitionIntIndex(ValueList, IndexList, low, high);
            QuickSortIntIndex(ValueList, IndexList, low, pi - 1);
            QuickSortIntIndex(ValueList, IndexList, pi + 1, high);
        }
    }
    
    static int QuickSortPartitionIntIndex(array<int> ValueList, array<int> IndexList, int low, int high)
    {
        int pivot = ValueList[high];

        int i = (low - 1);

        for (int j = low; j <= high- 1; j++)
        {
            if (ValueList[j] < pivot)
            {
                i++;
                SwapInt(ValueList, i, j);
                SwapInt(IndexList, i, j);
            }
         }
        SwapInt(ValueList, i + 1, high);
        SwapInt(IndexList, i + 1, high);
        return (i + 1);
    }
    
    static void QuickSortString(array<string> ValueList, int low, int high)
    {
        if (low < high) {
            int pi = QuickSortPartitionString(ValueList, low, high);
            QuickSortString(ValueList, low, pi - 1);
            QuickSortString(ValueList, pi + 1, high);
        }
    }
    
    static int QuickSortPartitionString(array<string> ValueList, int low, int high)
    {
        string pivot = ValueList[high];

        int i = (low - 1);

        for (int j = low; j <= high- 1; j++)
        {
            if (ValueList[j] < pivot)
            {
                i++;
                SwapString(ValueList, i, j);
            }
         }
        SwapString(ValueList, i + 1, high);
        return (i + 1);
    }
    
    static void QuickSortStringIndex(array<string> ValueList, array<int> IndexList, int low, int high)
    {
        if (low < high) {
            int pi = QuickSortPartitionStringIndex(ValueList, IndexList, low, high);
            QuickSortStringIndex(ValueList, IndexList, low, pi - 1);
            QuickSortStringIndex(ValueList, IndexList, pi + 1, high);
        }
    }
    
    static int QuickSortPartitionStringIndex(array<string> ValueList, array<int> IndexList, int low, int high)
    {
        string pivot = ValueList[high];

        int i = (low - 1);

        for (int j = low; j <= high- 1; j++)
        {
            if (ValueList[j] < pivot)
            {
                i++;
                SwapString(ValueList, i, j);
                SwapInt(IndexList, i, j);
            }
         }
        SwapString(ValueList, i + 1, high);
        SwapInt(IndexList, i + 1, high);
        return (i + 1);
    }
    
}

The functions:

Reversing

• static void ReverseDouble(array<double> ValueList)
• static void ReverseInt(array<double> ValueList)
• static void ReverseString(array<double> ValueList)

The above functions will take the given list and reverse it's order.

Shuffling

• static void ShuffleDouble(array<double> ValueList)
• static void ShuffleInt(array<int> ValueList)
• static void ShuffleString(array<string> ValueList)

The above functions will take the given list and shuffle it's order.

• static void MakeShuffledInt(array<int> ValueList, int StartValue, int StopValue, int StepValue = 1)
• static void MakeShuffledDouble(array<double> ValueList, double StartValue, double StopValue, double StepValue = 1.0)

The above functions will create a new list of numbers from StartValue to StopValue (incremented by StepValue) and shuffle the list.
How is this better than just calling random(min,max) a bunch of times? If you want a bunch of random numbers without repeats, this is the way to get that.

Sorting

• static void SortDouble(array<double> ValueList, array<int> IndexList = null)
• static void SortInt(array<int> ValueList, array<int> IndexList = null)
• static void SortString(array<string> ValueList, array<int> IndexList = null)

The above functions are the basic sorters. Give them a ValueList to be sorted and an empty IndexList. ValueList will be sorted ascending order and IndexList will contain a list of the original indices in sorted order.
This is useful if ValueList is a reference to another array and you want to know what the proper sort order would be for that array.
The order would be SourceArray[IndexList[0]]..SourceArray[IndexList[IndexList.Size()-1]]
If you pass a null as IndexList then no IndexList will be generated and you still get a properly sorted ValueList.

• static void SortActorsByDistanceToPoint(array<actor> ActorList, vector3 ReferencePoint)
• static void SortTIDActorsByDistanceToPoint(int tid, vector3 ReferencePoint, array<actor> ActorList)

The first function takes a list of actors and sorts them in ascending order of their distance to the given reference point.
The second takes a TID, generates a list of actors from that tid, then does the same as the previous function.

To create your own sort function to sort on another value, copy the function and change the ValueList.push to push whatever value you want to sort by - health, mass, pos.z, etc. You can also edit the if (ActorList) line if you want to exclude certain elements from the sort. For example if sorting by distance and you want to exclude actors greater than a certain distance, you can put that criteria in this line.

Printing

• static void PrintArrayDouble(array<double> ValueList, string Title = "ArrayDouble")
• static void PrintArrayInt(array<int> ValueList, string Title = "ArrayInt")
• static void PrintArrayString(array<string> ValueList, string Title = "ArrayString")

Probably not useful in-game but handy for testing and debugging.

[Nash]

Thank you! I will definitely find this useful.

Can you add a string array sorter too (alphabetically), to complete the set? :D

[Sir Robin]

If zscript has a string comparator (eg if ("abc" < "xyz")) then it will be pretty straight forward.
I'll also put some shufflers in for when you want a random unsorted list.

[Sir Robin]

added the string sort and a few other features. See first post for update

[Nash]

Thank you kindly, once again. :D You have a permanent spot in the credits of all my stuff, now!

[Sir Robin]

This library has functions to get a nonrepeating random number sequence, but I've also posted a more streamlined class for that function:
viewtopic.php?t=78488