Выбрать опору для быстрого выбора, используя медиану, реализованную в Java?

Question

Я нашел этот код в GitHub для quickselect алгоритм иначе известный как order-statistics, Этот код работает нормально.

я не понимаю medianOf3 метод, который должен расположить первый, средний и последний индексы в отсортированном порядке. но на самом деле это не так, когда я вывести массив, после вызова medianof3 метод. Я мог бы следовать этому методу относительно того, что он делает, за исключением последнего вызова swap(list, centerIndex, rightIndex - 1);, Может кто-нибудь объяснить, почему это называется?

import java.util.Arrays;



/**
* This program determines the kth order statistic (the kth smallest number in a
* list) in O(n) time in the average case and O(n^2) time in the worst case. It
* achieves this through the Quickselect algorithm.
*
* @author John Kurlak <[e-mail]>
* @date 1/17/2013
*/
public class Quickselect {
   /**
* Runs the program with an example list.
*
* @param args The command-line arguments.
*/
   public static void main(String[] args) {
       int[] list = { 3, 5, 9, 10, 7, 40, 23, 45, 21, 2 };
       int k = 6;
       int median = medianOf3(list, 0, list.length-1);
       System.out.println(median);
       System.out.println("list is "+ Arrays.toString(list));
       Integer kthSmallest = quickselect(list, k);

       if (kthSmallest != null) {
           System.out.println("The kth smallest element in the list where k=" + k + " is " + kthSmallest + ".");
       } else {
           System.out.println("There is no kth smallest element in the list where k=" + k + ".");
       }
       System.out.println(Arrays.toString(list));
   }

   /**
* Determines the kth order statistic for the given list.
*
* @param list The list.
* @param k The k value to use.
* @return The kth order statistic for the list.
*/
   public static Integer quickselect(int[] list, int k) {
       return quickselect(list, 0, list.length - 1, k);
   }

   /**
* Recursively determines the kth order statistic for the given list.
*
* @param list The list.
* @param leftIndex The left index of the current sublist.
* @param rightIndex The right index of the current sublist.
* @param k The k value to use.
* @return The kth order statistic for the list.
*/
   public static Integer quickselect(int[] list, int leftIndex, int rightIndex, int k) {
       // Edge case
       if (k < 1 || k > list.length) {
           return null;
       }

       // Base case
       if (leftIndex == rightIndex) {
           return list[leftIndex];
       }

       // Partition the sublist into two halves
       int pivotIndex = randomPartition(list, leftIndex, rightIndex);
       int sizeLeft = pivotIndex - leftIndex + 1;

       // Perform comparisons and recurse in binary search / quicksort fashion
       if (sizeLeft == k) {
           return list[pivotIndex];
       } else if (sizeLeft > k) {
           return quickselect(list, leftIndex, pivotIndex - 1, k);
       } else {
           return quickselect(list, pivotIndex + 1, rightIndex, k - sizeLeft);
       }
   }

   /**
* Randomly partitions a set about a pivot such that the values to the left
* of the pivot are less than or equal to the pivot and the values to the
* right of the pivot are greater than the pivot.
*
* @param list The list.
* @param leftIndex The left index of the current sublist.
* @param rightIndex The right index of the current sublist.
* @return The index of the pivot.
*/
   public static int randomPartition(int[] list, int leftIndex, int rightIndex) {
       int pivotIndex = medianOf3(list, leftIndex, rightIndex);
       int pivotValue = list[pivotIndex];
       int storeIndex = leftIndex;

       swap(list, pivotIndex, rightIndex);

       for (int i = leftIndex; i < rightIndex; i++) {
           if (list[i] <= pivotValue) {
               swap(list, storeIndex, i);
               storeIndex++;
           }
       }

       swap(list, rightIndex, storeIndex);

       return storeIndex;
   }

   /**
* Computes the median of the first value, middle value, and last value
* of a list. Also rearranges the first, middle, and last values of the
* list to be in sorted order.
*
* @param list The list.
* @param leftIndex The left index of the current sublist.
* @param rightIndex The right index of the current sublist.
* @return The index of the median value.
*/
   public static int medianOf3(int[] list, int leftIndex, int rightIndex) {
       int centerIndex = (leftIndex + rightIndex) / 2;

       if (list[leftIndex] > list[rightIndex]) {
           swap(list, leftIndex, centerIndex);
       }

       if (list[leftIndex] > list[rightIndex]) {
           swap(list, leftIndex, rightIndex);
       }

       if (list[centerIndex] > list[rightIndex]) {
           swap(list, centerIndex, rightIndex);
       }

       swap(list, centerIndex, rightIndex - 1);

       return rightIndex - 1;
   }

   /**
* Swaps two elements in a list.
*
* @param list The list.
* @param index1 The index of the first element to swap.
* @param index2 The index of the second element to swap.
*/
   public static void swap(int[] list, int index1, int index2) {
       int temp = list[index1];
       list[index1] = list[index2];
       list[index2] = temp;
   }
}

Answer 1

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

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

К сожалению, выполняемая оптимизация должна быть реорганизована из medianOf3() и переехал в randomPartition(),

По сути, оптимизация заключается в том, что мы хотим максимально частично "отсортировать" наш подмассив перед его разбиением. Причина в том, что чем больше отсортированы наши данные, тем лучше будут наши будущие варианты выбора разделов, что означает, что, как мы надеемся, наше время выполнения будет ближе к O(n), чем O(n^2). в randomPartition() метод, мы перемещаем значение разворота в крайнее правое положение подмассива, на который мы смотрим. Это перемещает крайнее правильное значение в середину подмассива. Это нежелательно, поскольку крайнее правильное значение должно быть "большим значением". Мой код пытается предотвратить это, помещая сводный индекс прямо рядом с крайним правым индексом. Затем, когда сводный индекс поменялся местами с самым правым индексом в randomPartition()"большее" крайнее правое значение не перемещается в середину подмассива, а остается справа.

Answer 2

Функция medianOf3 это определить порядок левой медианы и справа. Последнее заявление

swap(list, centerIndex, rightIndex - 1)

используется для достижения следующих предварительных условий рода:

Однако вместо повторения в обе стороны, как в быстрой сортировке, быстрый выбор повторяется только в одну сторону - сторону с элементом, который он ищет. Это уменьшает среднюю сложность от O(n log n) (в быстрой сортировке) до O(n) (в быстрой выборке).

И тогда алгоритм продолжается с:

   for (int i = leftIndex; i < rightIndex; i++) {
       if (list[i] <= pivotValue) {
           swap(list, storeIndex, i);
           storeIndex++;
       }
   }

чтобы

что значения слева от оси меньше или равны оси, а значения справа от точки больше, чем точка.