Реализация случайного алгоритма быстрой сортировки

CLRS говорит нам обменять A[r] на A[i], где i — случайная величина между p и r. Однако, если бы я случайным образом выбрал переменную в качестве опорной в функции быстрой сортировки и обменялся значениями, какова теперь будет временная сложность?

Будет ли алгоритм теперь работать хуже, чем тот, что приведен в книге?

Вот код

 package Clrs;
    import java.util.Random;
    public class Clrs
    {
        public static void main(String[] args) 
        {
                int[] a = new int[]{7,6,5,4,3,2,1}; 
                quicksort(a,0,a.length-1);
                        System.out.println(); 

            for (int i : a) {
            System.out.println(i);
            }
    }
    static void  quicksort(int a[],int p,int r)
    {
     int q;
     if(p<r)
     {
            Random random = new Random();
            int y = p+random.nextInt(r-p+1);
            int temp = a[y];
            a[y]=a[r];
            a[r]=temp;
            q = partition(a,p,r);
            quicksort(a,p,q-1);
            quicksort(a,q+1,r);
     }
    }
    static int partition(int a[],int p,int r)
    {        
        int x=a[r];
        int i=p-1;
        for (int j = p; j <= r-1; j++) {
            if(a[j]<=x)
            {
                i++;
                swap(a,i,j);
            }                       
        }        
        swap(a,i+1,r);      
        return i+1;
    }
    static void swap(int a[],int x,int y)
    {
        int t=a[x];
        a[x]=a[y];
        a[y]=t;
    }
}

algorithm quicksort clrs
person Sam Ahuj    schedule 25.06.2015    source источник
comment
en.wikipedia.org/?title=Quicksort#Choice_of_pivot   -  person thelaws    schedule 25.06.2015

Ответы (2)


arrow_upward
3
arrow_downward

Теоретическая сложность остается прежней. O(nlogn) средний случай и O(n^2) худший случай.

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

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

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

В качестве примечания, использование первого (или последнего) элемента в качестве опорного элемента, как это делает «классическая» быстрая сортировка, является плохой идеей, поскольку вероятность того, что массив будет отсортирован или почти отсортирован в реальных приложениях, намного выше, чем можно было бы ожидать, заставляя алгоритм довольно часто попадать в наихудшее поведение. Дополнительную информацию об этом можно найти в этой теме: Почему нас интересует, сколько времени занимает сортировка уже отсортированного файла?< /а>

person amit    schedule 25.06.2015
comment
Я не уверен, что это только злонамеренный вход. Входные данные для функций сортировки часто очень неоднородны. Возможно, злонамеренный + систематически предвзятый? - person Ami Tavory; 25.06.2015

arrow_upward
0
arrow_downward

Когда мы говорим о сложности Big-O определенного алгоритма. Часто речь идет о теоретической средней временной сложности. Хотя вы должны знать, что существует наихудший сценарий, когда временная сложность может быть намного хуже, чем средняя.

Например, быстрая сортировка O(n log n) средней сложности вычислений. Но в худшем случае это O(n2), когда ваш исходный массив полностью перевернут и вы выбрали неверный поворот.

person BufBills    schedule 25.06.2015