Бесконечный цикл в алгоритме быстрой сортировки, когда массив имеет два экземпляра одинакового значения - PullRequest
Новая
       11

Бесконечный цикл в алгоритме быстрой сортировки, когда массив имеет два экземпляра одинакового значения

0 голосов
/ 18 декабря 2018

Я пытался написать функцию быстрой сортировки в Visual Basic на практике.Это было достаточно просто сделать, и это прекрасно работает для массивов, которые не имеют одинаковое число, появляющееся дважды.Но как только это происходит, вторая итерация цикла, продвигающего левый указатель к правому указателю, застревает в бесконечном цикле, и я не могу понять, почему это происходит.

ЕслиУ кого-нибудь есть идея, почему он застрял, я буду признателен за помощь.Вот код: 

Public Function Partition(ByVal a As Integer(), ByVal left As Integer, ByVal right As Integer)

    Dim temp As Integer

    Do While left <> right

        Do While (a(left) < a(right)) And (left <> right)
            left = left + 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

        Do While (a(left) < a(right)) And (left <> right)
            right = right - 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

    Loop

    Return left
End Function

Sub QuickSort(ByVal a As Integer(), ByVal left As Integer, ByVal right As 
Integer)

    If left < right Then
        Dim position As Integer = Partition(a, left, right)
        QuickSort(a, left, position - 1)
        QuickSort(a, position + 1, right)
    End If

End Sub

1 Ответ

0 голосов
/ 18 декабря 2018

Это происходит всякий раз, когда a(left) и a(right) совпадают.После того, как вы поменяете их местами, они останутся прежними, поэтому вы меняете их снова и снова.
Чтобы избежать этой ситуации, вам необходимо

1.Заменить цикл ниже: 

Do While (a(left) < a(right)) And (left <> right)
            left = left + 1                
        Loop

наthis: 

Do While (a(left) <= a(right)) And (left <> right)
            left = left + 1                
        Loop

, чтобы расположить элементы, равные оси, на ее левую сторону

2.Добавить одношаговое продвижение после второго цикла (но только для случаякогда итераторы не указывают на один и тот же элемент, что подразумевает конец разбиения): 

  Do While (a(left) < a(right)) And (left <> right)
            right = right - 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

        If left <> right
           left = left + 1
        End if

Таким образом, измененная функция выглядит следующим образом: 

Public Function Partition(ByVal a As Integer(), ByVal left As Integer, ByVal right As Integer)

    Dim temp As Integer

    Do While left <> right

        Do While (a(left) <= a(right)) And (left <> right)
            left = left + 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

        Do While (a(left) < a(right)) And (left <> right)
            right = right - 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

        If left <> right
           left = left + 1
        End if
    Loop

    Return left
End Function

PS.Это может быть дополнительно оптимизировано, чтобы избежать замены одинаковых элементов или замены элемента на себя, я оставлю это для вас

...