Сначала рекурсивная небольшая сторона quicksort

Я пытаюсь отладить этот код, который я нашел для создания быстрой сортировки, которая сначала сортирует меньший раздел.

public static void quicksortSmallSide(int[] a, int p, int r)
{
 int q = p;
 while(p
<p> Вход [20, 19, 20] использовался для получения неправильного выхода [20, 19, 20], и я понял. Я думаю, я исправил его, изменив его на следующий код, но я не думаю, что он еще не ошибся</p> <pre class="prettyprint linenums">public static void quicksortSmallSide(int[] a, int p, int r) { if(r-p< 1) return; int q = p; while(p</pre><code> <p> Например <code>{70, 24, -74, 9, 58, -61, -86, 7, -78, 11, -73, 13, -93} сортируется по [-93, -86, -74, -73, 7, -61, 9, 11, -78, 24, 58, 13, 70]

1 ответ

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

private static void quickSort(int[] arr, int lo, int hi){
 if(lo >= hi) return;

 int p = partition(arr, lo, hi);

 // modified to choose small partition first

 if((p - lo )<=(hi-p)){
 System.out.println(String.format("Sorting left first %d %d %d",lo,p,hi)) ;
 quickSort(arr, lo, p);
 quickSort(arr, p+1, hi);
 }else {
 System.out.println(String.format("Sorting right first %d %d %d",lo,p,hi)) ;
 quickSort(arr, p+1, hi);
 quickSort(arr, lo, p);
 }
}

licensed under cc by-sa 3.0 with attribution.