Почему моя быстрая сортировка такая медленная? - PullRequest
Новая
       15

Почему моя быстрая сортировка такая медленная?

2 голосов
/ 01 января 2011

Я практикую написание алгоритмов сортировки как часть подготовки к собеседованию, и мне интересно, может ли кто-нибудь помочь мне определить, почему эта быстрая сортировка не очень быстрая?Кажется, он имеет правильную сложность во время выполнения, но он медленнее, чем моя сортировка слиянием, с постоянным коэффициентом около 2. Я также буду признателен за любые комментарии, которые улучшат мой код и не обязательно ответят на вопрос.*Большое спасибо за вашу помощь!Пожалуйста, не стесняйтесь, дайте мне знать, если я сделал какие-либо ошибки этикета.Это мой первый вопрос здесь.

private class QuickSort implements Sort {

        @Override
        public int[] sortItems(int[] ts) {
            List<Integer> toSort = new ArrayList<Integer>();
            for (int i : ts) {
                toSort.add(i);
            }
            toSort = partition(toSort);
            int[] ret = new int[ts.length];
            for (int i = 0; i < toSort.size(); i++) {
                ret[i] = toSort.get(i);
            }
            return ret;
        }

        private List<Integer> partition(List<Integer> toSort) {
            if (toSort.size() <= 1)
                return toSort;
            int pivotIndex = myRandom.nextInt(toSort.size());
            Integer pivot = toSort.get(pivotIndex);
            toSort.remove(pivotIndex);
            List<Integer> left = new ArrayList<Integer>();
            List<Integer> right = new ArrayList<Integer>();
            for (int i : toSort) {
                if (i > pivot)
                    right.add(i);
                else
                    left.add(i);
            }
            left = partition(left);
            right = partition(right);
            left.add(pivot);
            left.addAll(right);
            return left;
        }

}

Спасибо огромное, всем, кто помог!

Это мой намного улучшенный класс для потомков: 

private class QuickSort implements Sort {

        @Override
        public int[] sortItems(int[] ts) {
            int[] ret = ts.clone();
            partition(ret,0,ret.length);
            return ret;
        }

        private void partition(int[] toSort,int start,int end) {
            if(end-start<1) return;
            int pivotIndex = start+myRandom.nextInt(end-start);
            int pivot = toSort[pivotIndex];
            int curSorted = start;
            swap(toSort,pivotIndex,start);
            for(int j = start+1; j < end; j++) {
                if(toSort[j]<pivot) {
                    if(j!=curSorted+1) 
                        swap(toSort,curSorted,curSorted+1);
                    swap(toSort,j,curSorted++);
                }
            }
            // Now pivot is at curSorted
            partition(toSort,start,curSorted);
            partition(toSort,curSorted+1,end);
        }
    }

Ответы [ 2 ]

9 голосов
/ 01 января 2011

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

1 голос
/ 01 января 2011

Помимо не повторного использования списков, вы конвертируете между Integer и int на каждом шаге: 

        for (int i : toSort) {  // converts from Integer to int
            if (i > pivot)
                right.add(i);  // converts from int to Integer
            else
                left.add(i);   // converts from int to Integer
        }

Обратите внимание, что преобразование из int в Integer в целом требует создания нового объекта.

И, наконец, random.nextInt () может быть нетривиальной операцией. Возможно, было бы лучше выбрать случайный свод, только если toSort превышает определенный размер, и в противном случае использовать более простую стратегию выбора пивора (измерить!).

...