Quicksort Recursion

Question

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

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

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

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

исходный массив является

[100, 305, 2, 2002, 18, 99, 211, 30, 50, 1000, 403, 4, 400, 77]

и когда достигается переполнение стека массив

[2, 4, 18, 30, 50, 99, 77, 100, 211, 1000, 403, 305, 400, 2002]

class OtherQuickSort { 

static void sort(int[] array){ 

    quickSort(array, 0, array.length - 1) 

} 

static void quickSort(int[] array, int first, int last){ 
     int pivotIndex = partition(array, first, last) 

     quickSort(array, first, pivotIndex - 1) 
     quickSort(array, pivotIndex, last) 
} 

static int partition(int[] array, int first, int last){ 
    int pivotIndex = (first + last)/2 
    int pivotValue = array[pivotIndex] 

    swapIndices(array, pivotIndex, last) 

    int indexFromRight = last - 1 
    int indexFromLeft = first 

    while(indexFromLeft <= indexFromRight){ 
     while(array[indexFromLeft] < pivotValue){ 
      indexFromLeft++ 
     } 
     while(array[indexFromRight] > pivotValue){ 
      indexFromRight-- 
     } 

     if(indexFromLeft <= indexFromRight) { 
      swapIndices(array, indexFromLeft, indexFromRight) 
      indexFromLeft++ 
      indexFromRight-- 
     } 
    } 

    swapIndices(array, indexFromLeft, last) 

    indexFromLeft 
} 

static void swapIndices(int[] array, int left, int right){ 
    int leftValue = array[left] 
    array[left] = array[right] 
    array[right] = leftValue 
} 
} 

Answer 1

Вам необходимо обновить метод quickSort. Значение в pivotIndex уже находится в своем отсортированном положении, поэтому вам не нужно передавать его снова.

static void quickSort(int[] array, int first, int last){ 
    if(last > first){ 
     int pivotIndex = partition(array, first, last); 

     quickSort(array, first, pivotIndex-1); 
     quickSort(array, pivotIndex+1, last); 
    } 
}