Блог

Главная - Вопросы по программированию - Оптимизация раздела быстрой сортировки для дубликатов Java

Оптимизация раздела быстрой сортировки для дубликатов Java

#java #quicksort

#java #быстрая сортировка

Вопрос:

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

Буду признателен за любую помощь, спасибо.

Комментарии:

1. Нет необходимости выполнять внутреннюю замену, если элементы равны. Измените условие подкачки с > на >= .

2. Повторяющиеся элементы являются проблемой только для схемы разделов Lomuto. Схема разделения Хоара будет тратить время на замену равных элементов, но по мере увеличения количества дубликатов разделение приближается к идеальному разделению 50% / 50%.

Ответ №1:

Одним из решений может быть удаление дубликатов, затем быстрая сортировка, а затем добавление их обратно. Удаление и добавление дубликатов может выполняться за линейное время.

Удаление дубликатов

Этот метод удаляет дубликаты из заданного массива и возвращает отображение <число в массиве, количество>:

 public static Map<Integer, Integer> removeDuplicates(Integer[] arr) {
    
    LinkedList<Integer> duplicatesRemoved = new LinkedList<>();
    HashMap<Integer, Integer> counts = new HashMap<>();
    
    for (Integer n: arr) {
        if (counts.containsKey(n)) {
            counts.put(n, counts.get(n) 1);
        } else {
            counts.put(n, 1);
            duplicatesRemoved.add(n);
        }
    }
    
    return duplicatesRemoved.toArray(new Integer[0]);
}

Добавление дубликатов обратно в отсортированный массив

Выполнив быструю сортировку, вы можете добавить дубликаты обратно (опять же, за линейное время):

 public static Integer[] expand(Integer[] arr, HashMap<Integer, Integer> counts) {
      
    LinkedList<Integer> expanded = new LinkedList<>();
      
    for (Integer n: arr) {
        Integer count = counts.get(n);
        for (int i=0; i < count; i  ) {
            expanded.add(n);
        }
    }
      
    return expanded.toArray(new Integer[0]);
}

Это избавит вас от сложной работы по обработке дубликатов в сортировке.

Ответ №2:

Рассматривали ли вы возможность использования 3-сторонней быстрой сортировки разделов? это работает быстрее, если есть дубликаты. https://medium.com/@nehasangeetajha/3-way-quick-sort-18d2dcc5b06b

 private static void quickSort(int[] arr, int l,int r){
    if(l >= r){
        return;
    }
    int value = arr[l];
    int lt = l;
    int gt = r;
    int i = l 1;
    while(i <= gt){
        if(arr[i] < value){
            swap(arr, i  , lt  );
        }
        else if(arr[i] > value){
            swap(arr,i, gt--);
        }
        else{
            i  ;
        }
    }
    quickSort(arr, l, lt-1);
    quickSort(arr, gt 1, r);
}