С++: Быстрая сортировка (qsort, quick sort)

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

Программа на си вот такая:


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 256
int a[N];

void qsort(int l, int r)
{
int w,x,i,j;
i=l;
j=r;
x=a[(l+r)/2];
while (i<=j)
{
while (a[i]<x) i++;
while (x<a[j]) j--;
if (i<=j)
{
w=a[i]; a[i]=a[j]; a[j]=w;
i++; j--;
}
}
if (l<j) qsort(l,j);
if (i<r) qsort(i,r);

}
void main()
{
int i,n;
srand((unsigned) time(NULL));
printf("Enter N: "); scanf("%d", &n);
for (i=0; i<n; i++)
{
a[i]=1+rand()%n;
printf("%d ", a[i]);
}
printf("\n");
qsort(0,n-1);

for (i=0; i<n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}

функция принимает 2 параметра:

l это left, т.е левая граница и r соответственно правая. Это границы, с которых нужно сортировать. Массив не принимает, может перепишу да выложу рядом, если надо будет кому-либо. Сейчас сортирует массив с именем а. Размерность задана константой выше.

В основном теле программы происходит всё так:

Массив заполняется числами от 0 до n и сами числа тоже величиной до n, тут же он выводится на экран. Далее выполняется перенос строки и вызывается функция сортировки для всего массива. В завершение программа выводит измененный массив в консоль и переносит строку для красоты.

Код проверен на Visual Studio 2010. Работает.

Вывод программы для массива в 30 чисел

4 Responses

  1. Виктор 24.04.2012 / 12:14

    Спасибо.
    Мне нужно вставить счетчики сравнений и присваиваний.куда их вставить?

    • Pyatnitsev 24.04.2012 / 14:45

      Сравнение после каждого из While, внутри циклов, после всех if, а перестановка — это w=a[i]; a[i]=a[j]; a[j]=w; следовательно перестановка будет тут

Добавить комментарий