My Quicksort Algorithm only works with First Index as the Pivot

Question

I've started working on Sort Algorithms and got Quicksort working with the Activation Method as the first index for the pivot.

Now, if i try to use either a random index or the the last one it either just doesn't do anything or it just sorts the last half. A Video Showing what i mean.

My Code:

    class Quicksort : Sortalgorithm
{
    int ActivationMethod = -1;

    Random rand = new Random();

    /// <summary>
    /// The Constructor for the Quicksort Algorithm
    /// </summary>
    /// <param name="arr">The Array to sort</param>
    /// <param name="Actv">Activation Method: 0=First; 1=Last; 2=Random</param>
    /// <param name="del">The Delay for the Algorithm between each sort</param>
    /// <param name="sound">Wether Sound should be played</param>
    /// <param name="gui">The Instance of the GUI</param> 
    public Quicksort(int[] arr, int Actv, int del, bool sound, gui gui) : base(del, sound, gui)
    {
        if (arr.Length < 5)
        {
            throw new Exception("Array has too few Entries");
        }
        ActivationMethod = Actv;
        toSort = arr; // Is A Global Array from the inherited Class
    }

    protected override int sort()
    {
        if (token.IsCancellationRequested) return 2; // To Properly Cancel a Sort
        return qsort(getPivot(), toSort.Length-1);
    }

    /// <summary>
    /// The Quicksort Recursive Logic. Both Params are needed for the "sub-array"
    /// </summary>
    /// <param name="start">StartIndex for the Current Array</param>
    /// <param name="end">EndIndex for the Current Array</param>
    /// <returns></returns>
    private int qsort(int start, int end)
    {
        if (start < end)
        {
            if (token.IsCancellationRequested) return 2; // To Properly Cancel a Sort
            int pivot = partition(start, end); //get the pivot
            qsort(start, pivot); // do the same for the frist part (smaller or equal to pivot)
            qsort(pivot + 1, end); //and now for the second part (the largen than pivot)
        }
        return 1;
    }

    /// <summary>
    /// The Partitioning Logic for The Array. Both Params are needed for the "sub-array"
    /// </summary>
    /// <param name="start">StartIndex for the Current Array</param>
    /// <param name="end">EndIndex for the Current Array</param>
    /// <returns></returns>
    private int partition(int start, int end)
    {
        int pivot = toSort[start]; //Depending on Activiation Method
        int swapIndex = start;
        for (int i = start + 1; i <= end; i++)
        {
            if (toSort[i] < pivot) //Sort the Index Accrodingly
            {
                if (token.IsCancellationRequested) return 2; // To Properly Cancel a Sort
                swapIndex++;
                swap(i, swapIndex); // Is A Method inherited from a Class
            }
        }
        swap(start, swapIndex);
        return swapIndex;
    }

    /// <summary>
    /// Get The Pivot returning on the Declared Activation Method in the Construcor
    /// </summary>
    /// <returns>PivotIndex</returns>
    private int getPivot()
    {
        switch (ActivationMethod)
        {
            case 0:
                return 0;
            case 1:
                return toSort.Length - 1;
            case 2:
                return rand.Next(0, toSort.Length - 1);
            default:
                throw new Exception("No Activationmethod Defined");
        };
    }
}

I've been Stuck for quite a while with this problem, any help would be appreciated

Answer 1

There's a flaw in your logic.

You do qsort(getPivot(), toSort.Length-1);

at the top level to select the pivot, and then in partition() you do

int pivot = toSort[start];

That's not going to work: the first argument to qsort is where to start sorting, so anything but zero here at the top level will prevent parts of the input from participating in the sort.

Instead the pivot needs to be selected for each partition, so that must take place inside partition():

private int partition(int start, int end)
    {
        int pivot = toSort[getPivot(start, end)]; //Depending on Activiation Method

And then getPivot() must be modified to take the start and end arguments into account when calculating the pivot index to be within the proper range, based on the desired pivot selection method.