Написание быстрой сортировки с одной петлей

Question

Мой брат хочет, чтобы я оптимизировал свой код, используя только один цикл.Я не вижу, как быстрая сортировка может иметь только один цикл и работать.(Он сказал мне удалить внутреннюю петлю)

public class QuickSort {
public static void Quick(int[] target, int lo, int hi) {
    if (lo >= hi) {
        return;
      }
    Random numberGenerator = new Random();
    int pivot = numberGenerator.nextInt(hi-lo)+lo;
    int pivotValue = target[pivot];
    target[pivot]=target[hi];
    target[hi]=pivotValue;
    pivot=hi;
    int counter;
    for(counter=lo; counter<pivot ; counter++){
        while(target[counter]>target[pivot]){ 
            if(pivot-counter==1){
                int temp=target[counter];
                target[counter]=target[pivot];
                target[pivot]=temp;
                //return; //possibly the problem
            }
            else{
                int temp1 = target[pivot-1];
                int temp2 = target[pivot];
                target[pivot]=target[counter];
                target[pivot-1]=temp2;
                target[counter]=temp1;
                pivot=pivot-1;
            }
        }
    }
    Quick(target, lo, counter-1);
    Quick(target, counter, hi); 
}

public static void main(String[] args) {
    int sizeOfArray = 10;
    int numberOfTests = 1000;

    int numFailed = 0;
    for (int i = 0; i < numberOfTests; i++)
    {
        int[] iNeedSorting = new int[sizeOfArray];
        populateArrayWithRandomNums(iNeedSorting);
        //System.out.printf("Test #%d\n", i);
        //System.out.printf("Original Array: %s\n", intArrayToString(iNeedSorting));
        Quick(iNeedSorting, 0, iNeedSorting.length-1);

        if (!isSorted(iNeedSorting)) {numFailed++;}
        //System.out.printf("New Array: %s\n\n", intArrayToString(iNeedSorting));
    }
    System.out.printf("%d test failed\n\n", numFailed);
}

}

Answer 1

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

Ваш внешний цикл for перемещает счетчик на один шаг влево (при условии, что вы записываете массив слева направоправо).Ваша внутренняя петля for перемещает ось на один шаг вправо (за исключением особого случая, когда счетчик почти достиг опоры и вы совершаете последний своп).Там нет ничего, что перемещает счетчик назад вправо или поворот назад влево.Таким образом, вы не выполняете дополнительную работу из-за двух циклов, это вопрос ясности, а не эффективности.

Обычный способ записи разбиения - это использование одного цикла с двумя счетчиками вместо одного.Один счетчик тот, который вы использовали: все слева от него меньше, чем стержень.Другой счетчик играет симметричную роль: все справа от него больше, чем стержень.Тело цикла выполняет следующие действия:

• , если target[left_counter] и target[right_counter] неуместны, меняйте их местами;после этого и target[left_counter], и target[right_counter] находятся на нужной стороне массива, поэтому увеличивайте left_counter и уменьшайте right_counter;

• в противном случае: если target[left_counter] включенжелаемая сторона, приращение left_counter;если target[right_counter] находится на желаемой стороне, уменьшите right_counter.

Цикл завершается, когда счетчики пересекаются.Это в конечном итоге завершится, потому что по крайней мере один из счетчиков перемещается на каждой итерации.

Answer 2

Согласно ученым (или, по крайней мере, алгоритму быстрой сортировки, который я изучал, и я также быстро проверил книгу структур и алгоритмов данных), быстрая сортировка - это рекурсия.Разделение набора данных (для которого необходим цикл), а затем рекурсивная сортировка левой и правой сторон.