时间戳

首页 > 解决方案 > 我的快速排序算法仅适用于第一个索引作为枢轴

c# - 我的快速排序算法仅适用于第一个索引作为枢轴

问题描述

我已经开始研究排序算法，并让 Quicksort 使用激活方法作为枢轴的第一个索引。

现在，如果我尝试使用随机索引或最后一个索引，它要么不做任何事情，要么只对后半部分进行排序。显示我的意思的视频。

我的代码：

    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");
        };
    }
}

我已经被这个问题卡住了很长一段时间，任何帮助将不胜感激

标签： c#sortingquicksort

解决方案

你的逻辑有问题。

你做qsort(getPivot(), toSort.Length-1);

在顶层选择枢轴，然后在partition()你做

int pivot = toSort[start];

这是行不通的：第一个参数qsort是从哪里开始排序，所以在顶层除了零之外的任何东西都会阻止部分输入参与排序。

相反，需要为每个分区选择枢轴，因此必须在内部进行partition()：

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

然后getPivot()必须根据所需的枢轴选择方法，在计算枢轴索引时将start和参数考虑在内，使其在适当的范围内。end

推荐阅读