Медиана 3 занимает больше времени, чем обычная быстрая сортировка в Java - PullRequest
Новая
       41

Медиана 3 занимает больше времени, чем обычная быстрая сортировка в Java

0 голосов
/ 27 марта 2019

У меня есть код быстрой сортировки в Java, который я хочу улучшить. Улучшенный код должен занимать меньше времени, чем код быстрой сортировки. Однако при использовании моего улучшенного кода, который реализует медиану 3 секционирования, это займет еще 400 миллисекунд. Кто-нибудь может помочь мне решить это? если возможно, можете ли вы предложить мне другие возможные способы улучшить мой код. У меня есть от 10 000 до 10 миллионов целых чисел для сортировки.

Quicksort 

public void quickSort(int arr[], int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(arr, begin, end);

        quickSort(arr, begin, partitionIndex-1);
        quickSort(arr, partitionIndex+1, end);
    }


}

private int partition(int arr[], int begin, int end) {
    int pivot = arr[end];
    int i = (begin-1);

    for (int j = begin; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;

            int swapTemp = arr[i];
            arr[i] = arr[j];
            arr[j] = swapTemp;
        }
    }

    int swapTemp = arr[i+1];
    arr[i+1] = arr[end];
    arr[end] = swapTemp;

    return i+1;
}

}

Улучшенный код 

package sorting;


public class improvement {

Clock c = new Clock();

  public void quickSort(int[] intArray) {

    recQuickSort(intArray, 0, intArray.length - 1);

  }

  public static void recQuickSort(int[] intArray, int left, int right) {
    int size = right - left + 1;
    if (size <= 3)
      manualSort(intArray, left, right);
    else {
      double median = medianOf3(intArray, left, right);
      int partition = partitionIt(intArray, left, right, median);
      recQuickSort(intArray, left, partition - 1);
      recQuickSort(intArray, partition + 1, right);
    }
  }

  public static int medianOf3(int[] intArray, int left, int right) {
  int center = (left + right) / 2;

    if (intArray[left] > intArray[center])
      swap(intArray, left, center);

    if (intArray[left] > intArray[right])
     swap(intArray, left, right);

   if (intArray[center] > intArray[right])
     swap(intArray, center, right);

   swap(intArray, center, right - 1);
   return intArray[right - 1];
  }

  public static void swap(int[] intArray, int dex1, int dex2) {
    int temp = intArray[dex1];
    intArray[dex1] = intArray[dex2];
    intArray[dex2] = temp;
 }

  public static int partitionIt(int[] intArray, int left, int right, double 
  pivot) {
    int leftPtr = left;
    int rightPtr = right - 1;

     while (true) {
       while (intArray[++leftPtr] < pivot) 
       ;
       while (intArray[--rightPtr] > pivot)
       ;
       if (leftPtr >= rightPtr)
         break;
       else
       swap(intArray, leftPtr, rightPtr);
    }
    swap(intArray, leftPtr, right - 1);
    return leftPtr;
 }

 public static void manualSort(int[] intArray, int left, int right) {
    int size = right - left + 1;
    if (size <= 1)
     return;
   if (size == 2) {
  if (intArray[left] > intArray[right])
    swap(intArray, left, right);
  return;
} else {
  if (intArray[left] > intArray[right - 1])
    swap(intArray, left, right - 1);
  if (intArray[left] > intArray[right])
    swap(intArray, left, right);
  if (intArray[right - 1] > intArray[right])
    swap(intArray, right - 1, right);
  }
 }
}
...