Рекурсивная быстрая сортировка нескольких ошибок


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

Код сортирует массив из a[start] to a[end], используя метод медианы из трех. Я считаю, что проблема заключается в разделении. Пожалуйста, взгляните

    import java.util.*;
public class QuickSort
{
  public static void main(String [] args)
  {
    int [] arr = {6,4,1,14, 13,20,7,10,9,2,17};
    System.out.println(Arrays.toString(arr));
    quickSort(arr, 0,arr.length-1);
    System.out.println(Arrays.toString(arr));
    System.out.println("is the array sorted? " + isSorted(arr));
  }
public static void quickSort(int[] a, int start, int end)
  {
    if(end-start > 0) //base case for zero or one element? 
    {
        int pivotPosn = partition(a,start,end);
        quickSort(a,start, pivotPosn-1);
        quickSort(a,pivotPosn+1, end);
    }

  }
   /***
   * swap - Swaps two values in an array.
   ***/
  private static void swap(int [] a, int index1, int index2)
  {
    int temp = a[index1];
    a[index1] = a[index2];
    a[index2] = temp;
  }
  private static boolean isSorted(int [] a)
  {

    int i = a.length;
    boolean result = true;
    for(int j = 1; j<i; j++)
    {
      if(a[j-1] > a[j])
      {
        result = false;
      }
    }
    return result;
  }
  private static int medianOfThreeIndex(int [] a, int start, int end)
  {
    int mid= start + (end-start)/2; //find the middle of the array

    int vs = a[start];
    int vm = a[mid];
    int ve = a[end];

    if (vs >= vm  && vm >= ve)
    {
      return mid;
    }
    else if (vm >= vs  && vs >= ve)
    {
      return start;
    }
    else
    {
      return end;
    }
  }
  private static int partition(int [] a, int start, int end)
  {
    int boundary,pivot,pivotPosn;
    pivotPosn = medianOfThreeIndex(a,start,end);
    pivot = a[pivotPosn];
    boundary = start;

    swap(a,pivotPosn,end);//moving pivot to the right
    for(int curr = start+1; curr<=end;curr++)
    {
      if(a[curr]<pivot)
      {
        boundary++;
        swap(a,boundary,curr);
      }
    }
    swap(a,end,boundary); //swap pivot value back to its final place
    return boundary;
  }
}

Выход - [6, 4, 1, 9, 7, 13, 14, 10, 17, 20, 2] я не знаю, что я делаю неправильно : (

2   2   2015-01-28 19:04:28

2 ответа:

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

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

private static int partition(int [] a, int start, int end)
{
    int boundary,pivotPosn, pivot,bigStart;

    pivotPosn = start;
    pivot = a[pivotPosn];
    boundary = start;

    //Got rid of bigStart - it's not needed...
    swap(a,pivotPos,end); //Move your pivot value to the "right" or end of array

    // Note - it is fine to store the pivot at the "left" or start as
    // the OP originally did - in which case the following for
    // loop should run from start+1 to end inclusive and the 
    // boundary++ would come before the swap.

    for(int curr = start; curr<end;curr++)
    {
        if(a[curr]<pivot)
        {

            swap(a,boundary,curr);
            boundary++;
        }
    }
    swap(a,end,boundary); //swap your pivot value back to its final place
    return boundary;
}
Затем посмотрите на свой метод быстрой сортировки. Помните, что мы пока игнорируем medianOfThree. Вы ловите крайний случай, который вам на самом деле не нужен - массив 2-х членов. Гораздо проще было бы:
public static void quickSort(int[] a, int start, int end)
{
    if(end-start > 0) //base case for zero or one element? already 
    {
        int pivotPosn = partition(a,start,end);
        quickSort(a,start, pivotPosn-1);
        quickSort(a,pivotPosn+1, end);
    }
}

С этим он будет работать :)

Однако-вы можете захотеть вернуться к medianOfThree. Помните, куда мы положили pivotPosn = start?

Измените это на pivotPosn = medianOfThree(a,start,end); (или все, что вам нравится, как пока он находится в пределах массива-поиграйте).

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

private static int medianOfThreeIndex(int [] a, int start, int end)
{
    int mid= start + (end-start)/2; //find the middle of the array

    int vs = a[start];
    int vm = a[mid];
    int ve = a[end];

    if (vs >= vm  && vm >= ve)
    {
        return mid;
    }
    else if (vm >= vs  && vs >= ve)
    {
        return start;
    }
    else
    {
        return end;
    }

}

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

Ваш код кажется мне странным. Взгляните на http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html Код там кажется мне более ясным.