Быстрая сортировка (QSort) (реализация на C++)

C++   23 марта 2012  Автор статьи:  

В данной статье я представлю рекурсивный пример реализации быстрой сортировки. Массив, который нужно отсортировать будет глобальным, если же вы захотите сделать его локальным, то просто передавайте его как параметр в функцию.Конечно, после того, как вы сделаете это вам нужно будет использовать template для того, чтобы ваша функция работала со всеми типами данных. Я этим заниматься в рамках данной статьи не буду, поэтому просто приведу код рекурсивной сортировки quicksort:

#include
using namespace std;
int a[100];
void quickSort(int l, int r)
{
int x = a[l + (r - l) / 2];
//запись эквивалентна (l+r)/2,
//но не вызввает переполнения на больших данных
int i = l;
int j = r;
//код в while обычно выносят в процедуру particle
while(i <= j) { while(a[i] < x) i++; while(a[j] > x) j--;
if(i <= j) { swap(a[i], a[j]); i++; j--; } } if (i> n;
for(int i = 0; i < n; i++) { cin>>a[i];
}
quickSort(0, n-1);
for(int i = 0; i < n; i++) { cout<

  • Петро Мельник

    cпс

  • Alex

    Замечательно

  • Alex

    Замечательно

  • Денис

    Я этим заниматься в рамках данной статьи не буду

    А где статья-то? Только короткий листинг, и тот приведен без объяснения алгоритма. И почему делать нужно функцию шаблоннной при переносе массива из глобального скопа в скоп функции?

  • Хорин Алексей

    Не красиво делать массив глобальным!

    • В алгоритме это не важно.

  • Alt

    if (i<r)

    qsort(i, r);

    if (l<j)

    qsort(l, j);

    для чего эти два ифа?

    • Посмотрите теорию алгоритма, в этих ифах вся соль.

    • Bohdan Beniv

      в масиве мы берём сортировку от 1 к последнему числу (l and r) соответствено, потом делим на 2 подмасива, тоисть разделяем все числа на две половины, первый if занимается первой частью промежутка чисел, а второй соответственным.
      ето реккуренция .

Научиться программировать

  • на Delphi

  • на Java

  • на C++