>

배열에 10 개의 항목 만있을 때 작동하는 C #에서 퀵 정렬 알고리즘을 만들었습니다. 이 숫자를 늘리면 무한 루프에 빠집니다. 문제가있는 코드는 다음과 같습니다.

        while (true)
         {
            while (((IComparable)arrayToSort[left]).CompareTo(pivot) < 0)
            {
                left++;
            }
            while (((IComparable)arrayToSort[right]).CompareTo(pivot) > 0)
            {
                right--;
            }
            if (left < right) //This is where the loop becomes infinite.
            {
                object temp =arrayToSort[right];
                arrayToSort[right] = arrayToSort[left];
                arrayToSort[left] = temp;
                reDrawer.reDrawSample(right, g, arrayToSort, picSamples); //This is used to draw lines that are sorted to make the sorting visual.
                reDrawer.reDrawSample(left, g, arrayToSort, picSamples);
                refresher.refreshPicture(picSamples); //This is used to refresh the image with the lines.
                Thread.Sleep(20);
            }
            else
            {
                return right;
            }

문장은 거짓이지만 비교하면 둘 다 사실이지만, 그 방법을 볼 수 없습니다. 오른쪽 == 피벗 또는 왼쪽 == 피벗 일 때 발생합니다.

다른 사람이 문제를 볼 수 있습니까?

배열에는 현재 50 개의 변수가 있으며이 문제는 많은 수의 변수에서만 발생합니다. 변수가 50 개 미만인 배열을 사용하고 싶지 않습니다.

전체 방법은 다음과 같습니다.

class Quick_Sort
{
    /// <summary>
    /// This subroutine creates a pivot and partitions the array accordingly.
    /// </summary>
    /// <param name="arrayToSort"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    /// <returns></returns>
    public int partition(ArrayList arrayToSort, int left, int right)
    {
        int pivot = (int)arrayToSort[left];
        ReDrawer reDrawer = new ReDrawer();
        Refresher refresher = new Refresher();
        while (true)
        {
            while (((IComparable)arrayToSort[left]).CompareTo(pivot) < 0)
            {
                left++;
            }
            while (((IComparable)arrayToSort[right]).CompareTo(pivot) > 0)
            {
                right--;
            }
            if (left < right)
            {
                object temp =arrayToSort[right];
                arrayToSort[right] = arrayToSort[left];
                arrayToSort[left] = temp;
                reDrawer.reDrawSample(right, g, arrayToSort, picSamples);
                reDrawer.reDrawSample(left, g, arrayToSort, picSamples);
                refresher.refreshPicture(picSamples);
                Thread.Sleep(speed);
            }
            else
            {
                return right;
            }
        }
    }
    /// <summary>
    /// This recursive subroutine is responsible for sorting the array into the correct order after the individual partitions have been ordered.
    /// </summary>
    /// <param name="arr"></param>
    /// <param name="left"></param>
    /// <param name="right"></param>
    public void sortArray(ArrayList arr, int left, int right)
    {
        if (left < right)
        {
            int pivot = partition(arr, left, right);
            if (pivot > 1)
            {
                sortArray(arr, left, pivot - 1);
            }
            if (pivot + 1 < right)
            {
                sortArray(arr, pivot + 1, right);
            }
        }
    }
}

sortArray가 호출되면 left = 0, right = 49&array는 임의의 50 요소 1 차원 배열입니다.

reDrawer 및 refresher에 대한 참조는 정렬 알고리즘에 영향을 미치지 않고 그림 상자에만 결과를 표시하므로 무시할 수 있습니다.


  • 답변 # 1

    와이즈 비즈

    그렇습니다.이 경우 왼쪽/오른쪽으로 증가/감소하지 않습니다. 매번 반복 할 때마다 둘 다 적어도 한 번씩 증가/감소해야합니다.

    It occurs when right == pivot or left == pivot.

    public int partition(ArrayList arrayToSort, int left, int right) { int pivot = (int)arrayToSort[left]; left--; right++; //To prevent the first iteration from ignoring the outermost elements ReDrawer reDrawer = new ReDrawer(); Refresher refresher = new Refresher(); while (true) { do { left++; }while (((IComparable)arrayToSort[left]).CompareTo(pivot) < 0); do { right--; }while (((IComparable)arrayToSort[right]).CompareTo(pivot) > 0); if (left < right) { object temp =arrayToSort[right]; arrayToSort[right] = arrayToSort[left]; arrayToSort[left] = temp; reDrawer.reDrawSample(right, g, arrayToSort, picSamples); reDrawer.reDrawSample(left, g, arrayToSort, picSamples); refresher.refreshPicture(picSamples); Thread.Sleep(speed); } else { return right; } } }

  • 이전 android - Xamarin Visual Studio 또는 에뮬레이터에서 APK 가져 오기
  • 다음 sql server - DatabaseIntegrityChecksql이 디스크의 텍스트 파일에 로그합니까?