Это программа на C++ быстрая сортировка в порядке?


Я написал программу быстрой сортировки на C++.

  1. Нормально ли это реализовать таким образом?
  2. Я правильно используя указатели?
  3. Мой стиль хорошо?
  4. Любые идеи для его ускорения или экономии памяти?

void change(int *i, int *j)
{
int temp = *j;
 *j = *i;
*i = temp;
}


int *toplace(int *start, int *end)
{
    int *i = start+1, *j= end;

    while(i<=j)
    {
    for(; *i<=*start && i<=end; i++);
    for(; *j>=*start && start+1<=j; j--);   
    if (i<j) change(i++,j--); 
    }

    change(start,i-1); 
    return i-1;
}



void quicksort(int *start, int *end)
{
    if (start >= end) return;

    for(int *debug = start;debug<=end;debug++) std::cout<<*debug <<" ";
    std::cout<<std::endl;  //this and...

    int *temp = start;
    temp = toplace(start,end);

    for(int *debug = start;debug<=end;debug++) std::cout<<*debug <<" ";
    std::cout<<std::endl; //...this are only to "see under the hood"
    std::cout<<std::endl;

    quicksort(start,temp-1);
    quicksort(temp+1,end);

}

Пример использования:

int main(int argc, char* argv[])
{
    int A[] = {5,14,8,12,1,2,11,15,6,9,7,3,13,4,10};
    int n = sizeof (A) / sizeof(A[0]);

    quicksort(A, &A[n-1]);

    for (int i =0; i<n; i++) std::cout<<A[i] <<" ";

    getchar();
    return 0;
}

производит вывод:

5 14 8 12 1 2 11 15 6 9 7 3 13 4 10
1 4 3 2 5 12 11 15 6 9 7 8 13 14 10

1 4 3 2
1 4 3 2

4 3 2
2 3 4

2 3
2 3

12 11 15 6 9 7 8 13 14 10
8 11 10 6 9 7 12 13 14 15

8 11 10 6 9 7
6 7 8 10 9 11

6 7
6 7

10 9 11
9 10 11

13 14 15
13 14 15

14 15
14 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


1075
15
задан 24 ноября 2011 в 04:11 Источник Поделиться
Комментарии
2 ответа

Интерфейс для быстрой сортировки:

quicksort(A, &A[n-1]);

В C я бы ожидал увидеть указатель и размер.
В C++ я бы ожидал увидеть двух итераторов (как выше), но в целом конечный пункт находится, как правило, после конца (если вы хотите быть последовательным с C++ идиомы и стл способ делать вещи).

quicksort(A, A+n); // This is what I would expect to see.

Перемен!
Я бы назвал этот своп()

void change(int *i, int *j)
{
int temp = *j;
*j = *i;
*i = temp;
}

Также в C++ я бы передать значения быть заменены ссылкой. И там уже есть функция std::swap (своп), который прекрасно работает.

Вашего для() петли, которые ничего не делают в организме.

for(; *i<=*start && i<=end; i++);

Это трудно читать, когда делаешь ремонт. На первый взгляд похоже, что вы случайно не отступ код правильно, нужно изучить код, чтобы понять это правильно. Я считаю, что лучше поставить пустую тела (возможно даже с комментарием /* намеренно пуст */

for(; *i<=*start && i<=end; i++)  { /* Empty */ }

В вашей петли вы проверяете переменную цикла от начала и конца. Они не должны быть проверены друг против друга?

while(i<=j)
{
for(; *i<=*start && i<=end; i++);
for(; *j>=*start && start+1<=j; j--);

// Should be:

for(; *i<=*start && i <= j; i++) { /* Empty */ }
for(; *j>=*start && i <= j; j--) { /* Empty */ }

Ваша быстрая сортировка вроде работает, но немного не традиционный в пару особенностей.

Точка разворота *начать. Значений, которые равны, кажется, идут в обе части ведра. Традиционно они идут в определенное ведро.

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

В настоящее время код работает с указателей на целые. Но на самом деле вы используете указатели, как итераторы. Поэтому вы должны templatize его так, чтобы входы не являются указателями, но являются универсальными итераторы, то это позволяет использовать алгоритм на любой тип контейнера (с боковым повлиять на то, что он работает с любой тип, который реализует <= оператор.

10
ответ дан 24 ноября 2011 в 05:11 Источник Поделиться

Во-первых там уже СТД::сорт функция в стандартной библиотеке. Если вы в курсе этого и просто написал это в качестве учебного упражнения это хорошо, но если вы действительно хотите использовать этот код в производство, нет никаких причин не использовать СТД::сорт , а не. Это, как говорится, Вот отзыв ваш код:


Эффективность

Одно важное замечание о Ваш алгоритм, который вы используете первый элемент массива в качестве опорного элемента. Это довольно неэффективно, если вы сортируете массив, который уже частично отсортирован (ведущих к квадратичной выполнения). Вы должны использовать вместо случайного элемента.

Кроме того, я не вижу никаких недостатков в коде.


Генерики

В настоящее время код работает только на массива Ints. Это плохо, потому что нет никаких причин, вы не должны быть в состоянии использовать) все, что сопоставимо с использованием <,> и т. д. вместо Интс б) другие коллекции, например, векторs вместо массивов. Если вы превратите свои функции в шаблон функции, вы можете легко достичь этого путем простой замены всех вхождений инт* с помощью шаблона аргумент.

Вы могли бы дальнейшей генерализации функция сортировки, с помощью дополнительного компаратора аргумент, как СТД::сорт делает.


Читаемости кода и общей передовой практикой

Я бы переименовать изменить функцию, чтобы поменять , потому что эту функцию обычно называют и имя поменять действительно не дают хорошее представление о том, что функция делает. Я бы также использовать ссылки вместо указателей, потому что это хорошая практика, чтобы избежать с помощью советов, Если вы не нуждаетесь в них. И снова: если вы не просто повторно реализовать это в качестве учебного упражнения, использовать с std::своп вместо того, чтобы строить свой собственный (который делает то же самое).

В вашей функции, вы должны переименовать темп на что-то более описательное, потому что имя содержит абсолютно никакой информации.

Также все операторы печати делает ваш код трудно следовать. Я хочу удалить их и использовать отладчик, когда я должен вместо того, чтобы отлаживать код.

Пару замечаний не помешают.

10
ответ дан 24 ноября 2011 в 05:11 Источник Поделиться