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

Question

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

3 45 12 -3 4 -3 21 0 6 20

Вот как должен выглядеть вывод.:

Количество точек разворота: 7
Первый элемент: -3
Последний элемент: 45

Вот что я получаю:

Количество пивотов: 5
Первый элемент: -3
Последний элемент: 45

В другом примере он работает с правильным количеством пивотов:

9 2 4 7 3 7 10 11 12 13 13 10 13 13

Что я должен получить, а также что я получу:

Количество точек разворота:10
Первый элемент: 2
Последний элемент: 13

Меня особенно смущает, что в некоторых случаях это работает, а в других - нет.

Воткод:

public static void quickSort(int[] arr, int start, int end, CountObject count){

    int partition = partition(arr, start, end, count);
    //partition will return the position the pivot. The pivot will be at the right place, hence if either side
    //of the pivot consists of only one element, it should not be sorted

    //check whether the part left from the pivot should still be sorted

   if(partition-1>start) {
        quickSort(arr, start, partition - 1, count);
    }
    //check whether the part right from the pivot should still be sorted
    if(partition+1<end) {
        quickSort(arr, partition + 1, end, count);
    }

}

public static int partition(int[] arr, int start, int end, CountObject count){
    int pivot = arr[start];
    count.increaseCount();

    //checks if left pointer < pivot
    for(int i=end; i>start; i--){
        if(arr[i]>pivot){
            int temp= arr[end];
            arr[end]=arr[i];
            arr[i]=temp;
            end--;
        }
    }


    int temp = arr[start];//=pivot
    arr[start] = arr[end];
    arr[end] = temp;

    return end;



}

}

Я использую класс CountObject для подсчета.Он содержит метод увеличенияCount и переменную экземпляра count.

Answer 1

Так что я наконец понял это.Мне пришлось использовать другую технику, чтобы пройти через список.В моем OP я использовал первый элемент как pivot и сравнил его со всеми элементами beginnign с конца списка.Теперь я начну со 2-го элемента списка / текущего подсписка.

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

import java.util.Scanner;

public class Quickie {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int temp;

        int size = sc.nextInt();

        int[] list = new int[size];
        for (int i = 0; i < size; i++) {
            temp = sc.nextInt();
            list[i] = temp;
        }
        int end = size - 1;
        CounterClass count = new CounterClass(0);

        quickSort(list, 0, end, count);

        int firstElement = list[0];
        int lastElement = list[size - 1];
        System.out.println("Number of pivots: " + count.getCount());
        System.out.println("First Element: " + firstElement);
        System.out.println("Last Element: " + lastElement);
    }
    private static void quickSort (int []arr, int start, int end, CounterClass count){
        int partition = partition(arr, start, end, count);

        if (partition-1>start){
            quickSort(arr, start, partition-1,count);
        }
        if (partition+1<end){
            quickSort(arr, partition+1,end,count);
        }
    }
    private static int partition (int[]arr, int start, int end, CounterClass count){
        int pivot = arr[start];

        count.count++;
        int pointer = start+1;
        int i =pointer;
        for (int j=pointer; j<=end;j++){
            if (arr[j]<pivot){
                int temp = arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
                i++;
            }
        }
        i-=1;

        int temp=arr[start];
        arr[start]=arr[i];
        arr[i]=temp;
        return (i);
    }



}


class CounterClass{
    int count;
    public CounterClass(int count){
        this.count = count;
    }

    public int getCount() {
        return count;
    }
}