Quicksort не правильно сортируется

Question

Попытка узнать о выполнении Quicksort, я не могу понять, почему он не сортируется правильно.

Используя эту последовательность:

6, 7, 12, 5, 9, 8, 65, 3

Он возвращает это:

3, 5, 7, 8, 9, 65 , 12, 6

Кажется, что-то немного, но не все. Что я пропустил?

Вот мой код:

static void Main(string[] args) 
     { 
      QuickSort qs = new QuickSort(); 

      int[] arr = new int[] { 6, 7, 12, 5, 9, 8, 65, 3 }; 

      foreach (int l in arr) 
      { 
       Console.Write(l + ", "); 
      } 

      int left = 0; 
      int right = arr.Count() - 1; 

      int[] arrr = qs.DoQuickSort(ref arr, left, right); 
      Console.WriteLine("Sorted List: "); 
      foreach (int i in arrr) 
      { 
       Console.Write(i + " "); 
      } 



      Console.ReadLine(); 
     } 

    public int Partition(int[] array, int left, int right, int PivotIndex) 
    { 
    int pivValue = array[PivotIndex]; 

    array = Swap(ref array, PivotIndex, right); 

    int storeIndex = left; 

    for (int i = PivotIndex; i < right-1; i++) 
    { 
     if (array[i] <= pivValue) 
     { 
      array = Swap(ref array, i, storeIndex); 
      storeIndex = storeIndex + 1; 
     } 
    } 

    array = Swap(ref array, storeIndex, right); 

    return storeIndex; 
} 

public int[] Swap(ref int[] arr, int first, int second) 
{ 
    int temp = arr[first]; 
    arr[first] = arr[second]; 
    arr[second] = temp; 

    return arr; 
} 

public int[] DoQuickSort(ref int[] array, int left, int right) 
{ 
    if (right > left) 
    { 
     int PivIndex = (left + right)/2; 
     int newPivIndex = Partition(array, left, right, PivIndex); 
     DoQuickSort(ref array, left, newPivIndex - 1); 
     DoQuickSort(ref array, newPivIndex + 1, right); 
    } 

    return array; 
} 

Answer 1

В дополнение к моим комментарием на сам вопрос, я хотел бы отметить, что Swap() и DoQuickSort() методы не должны возвращать массив (как в моей записке в комментарии, который объясняет что массив является ссылкой). Для этого, ваш код, чтобы сделать работу должен выглядеть следующим образом:

public int Partition(int[] array, int left, int right, int pivotIndex) 
{ 
    int pivValue = array[pivotIndex]; 

    Swap(array, pivotIndex, right); 

    int storeIndex = left; 

    for (int i = left; i < right; i++) 
    { 
     if (array[i] <= pivValue) 
     { 
      Swap(array, i, storeIndex); 
      storeIndex = storeIndex + 1; 
     } 
    } 

    Swap(array, storeIndex, right); 

    return storeIndex; 
} 

public void Swap(int[] arr, int first, int second) 
{ 
    int temp = arr[first]; 
    arr[first] = arr[second]; 
    arr[second] = temp; 
} 

public void DoQuickSort(int[] array, int left, int right) 
{ 
    if (right > left) 
    { 
     int pivIndex = (left + right)/2; 
     int newPivIndex = Partition(array, left, right, pivIndex); 
     DoQuickSort(array, left, newPivIndex - 1); 
     DoQuickSort(array, newPivIndex + 1, right); 
    } 
} 

Answer 2

В вашем методе Partition у вас есть неправильный выбор цикла:

for (int i = PivotIndex; i < right-1; i++) 

должны стать:

for (int i = left; i < right; i++) 

чекаут related wikipedia article, который говорит:

function partition(array, left, right, pivotIndex) 
    pivotValue := array[pivotIndex] 
    swap array[pivotIndex] and array[right] // Move pivot to end 
    storeIndex := left 
    for i from left to right - 1 // left ≤ i < right 
     if array[i] ≤ pivotValue 
      swap array[i] and array[storeIndex] 
      storeIndex := storeIndex + 1 
    swap array[storeIndex] and array[right] // Move pivot to its final place 
    return storeIndex 

Примечание: left ≤ i < right

Answer 3

просят, чтобы вы передали рыбу или учить, как ловить рыбу?

Изучение того, как отлаживать собственные программы, а не полагаться на других людей, чтобы сделать это за вас, - это умение, которое послужит вам в будущем.

Столкнувшись с этой проблемой, то первое, что я хотел бы сделать это разметить код с комментариями с указанием семантического назначения каждого участка кода:

// Choose a pivot halfway along the portion of the list I am searching. 
int PivIndex = (left + right)/2; 
// Partition the array so that everything to the left of the pivot 
// index is less than or equal to the pivot, and everything to 
// the right of the pivot is greater than or equal to the pivot. 
int newPivIndex = Partition(array, left, right, PivIndex); 
// Recursively sort each half. 
DoQuickSort(ref array, left, newPivIndex - 1); 
DoQuickSort(ref array, newPivIndex + 1, right); 

ОК, теперь где-то здесь появляется ошибка. Где? Начните перечислять факты, которые, по вашему мнению, верны, и написать утверждение для каждого факта. Напишите себе вспомогательные методы, такие как AllLessThan, которые проверяют утверждения для вас.

// Choose a pivot halfway along the portion of the list I am searching. 
int PivIndex = (left + right)/2; 

int pivotValue = array[PivIndex]; 
// Partition the array so that everything to the left of the pivot 
// index is less than or equal to the pivot, and everything to 
// the right of the pivot is greater than or equal to the pivot. 
int newPivIndex = Partition(array, left, right, PivIndex); 
Debug.Assert(array[newPivIndex] == pivotValue); 
Debug.Assert(AllLessThanOrEqual(array, left, newPivIndex, pivotValue)); 
Debug.Assert(AllGreaterThanOrEqual(array, newPivIndex, right, pivotValue)); 
// Recursively sort each half. 
DoQuickSort(ref array, left, newPivIndex - 1); 
Debug.Assert(IsSorted(array, left, newPivIndex)); 
DoQuickSort(ref array, newPivIndex + 1, right); 
Debug.Assert(IsSorted(array, left, right)); 

Теперь, когда вы запустите эту программу еще раз, в тот момент, один из ваших утверждений нарушаются, вы получите окно, которое появляется, чтобы сказать вам, что природа бага. Продолжайте это, документируйте свои предпосылки и постусловия утверждениями, пока не найдете ошибку.