Быстрая сортировка в C++


Вот реализация все закончилось. Пожалуйста, напишите ваши отзывы!

#include <cstdio>
#include <cstdlib>

#include <iostream>

inline void swap(int * const a, const int i, const int j) {

    const int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void printArray(int *a, int len) {
    for(int i=0; i<len; i++)
        printf("%i ", a[i]);
    printf("\n");
}

void qsort(int * const a, const int len) {

    if(len < 2)
        return;

    const int pivot = a[rand() % len];

    printf("Choosed pivot %i\n", pivot);

    int lower = 0;
    int upper = len - 1;

    while(true) {

        while(a[lower] < pivot)
            lower++;

        while(a[upper] > pivot)
            upper--;

        printArray(a, len);

        if(lower == upper)
            break;

        swap(a, lower, upper);
    }

    printf("First Part ");
    printArray(a, lower);
    printf("Second Part ");
    printArray(a + lower + 1, len - lower - 1);
    printf("\n");

    qsort(a, lower);
    qsort(a + lower + 1, len - lower - 1);
}

int main() {

    int a[] = {1, 7, 3, 6, 5, 9, 2, 0, 4, 8};
    int len = sizeof(a)/sizeof(int);

    qsort(a, len);
    printArray(a, len);

    std::cin.get();
}


865
7
задан 12 декабря 2011 в 09:12 Источник Поделиться
Комментарии
2 ответа

#include <cstdio>
#include <cstdlib>

#include <iostream>

Если вы пишете на C++ предпочитают в cout и Кин , предусмотренных библиотеки iostream. Они обеспечивают намного лучше типа-безопасность по сравнению с аналогами. Ото, вы все еще можете использовать функции printf и scanf, ведь если вы не нуждаетесь в дополнительной гибкости, обеспечиваемой на C++ потоки, и вы хотите сохранить надбавки к минимальной. Во всяком случае, его не имеет смысла включать как здесь заголовки-вы либо через одно, либо другое.


inline void swap(int *const a, const int i, const int j) 
// ...

Вам не нужно писать свой собственный своп. Стандартная библиотека предоставляет полностью совместим с std::своп , который можно назвать так:

std::swap(a[lower], a[upper]);


Обратите внимание, что const и не добавляя ничего здесь для qsort прототипа, так как все это пройти по значению. Тонкий момент заключается в том, что указатель ниже-это тоже передачи по значению. Изменение в qsort не повлияет, где оригинал " а " указатели(передается по главной).

void qsort(int * const a, const int len)
// ...

Это qsort подписи более реминисценцию в стиле C функции, чем c++. В C++ это больше распространено, чтобы принять диапазон для сортировки по templatizing параметров с типы iterator. Что-то похожее на этот пример:

template <class RANDOMIT>
void qsort(RANDOMIT begin, const RANDOMIT &end);

Это хорошо освещены в других уже вопросы быстрой сортировки. Посмотри здесь и здесь более подробное описание и другие идеи, которые вы можете исследовать.


Я бы тоже вынесем код разметки для своей собственной функции просто держать задачи четко определен.

while(true) {
while(a[lower] < pivot)
lower++;
while(a[upper] > pivot)
upper--;

printArray(a, len);

if(lower == upper)
break;

swap(a, lower, upper);
}

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

while(true) 
{
// ...
if(lower >= upper) break;

if(a[lower] != a[upper]) { std::swap(a[lower], a[upper]); }
++lower, --upper;
}

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

@Виктор: все, что я хотел:

Так просто один очень мелкие не подберешь.

int a[] = {1, 7, 3, 6, 5, 9, 2, 0, 4, 8};
int len = sizeof(a)/sizeof(int);

Предпочитают определять это с точки зрения реальных элементов. Тогда при изменении типа массива нужно изменить только в одном месте:

int len = sizeof(a)/sizeof(a[0]); // a[0] will always have the correct type even if you
// change the underlying type of the array. And since
// is evaluated at compile time will always work.

Комментарий 1:

while(a[lower] < pivot)
lower++;
while(a[upper] > pivot)
upper--;

Какой набор делать элементы, которые равны оси идет?

Комментарий 2:

    if(lower == upper)
break;

Как часто это происходит?

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