01.12.2009, 19:29
общий
это ответ
Здравствуйте, Dimon4ik. В приложении две программы: C (по Кернигану&Ричи), С++ (по Кормен, Лейзерсон, Ривест "Алгоритмы. Построение и анализ". Комментарии Кернигана и Ричи понятные.
Приложение:
#include <stdio.h>
/* Керниган, Ричи, Язык программирования Си, 2-е издание */
/* Глава 4. Функции и сруктура программы, стр.100 */
/*
Следующий хороший пример рекурсии - это быстрая сортировка,
предложенная Ч.А.Р. Хоаром в 1962 г.
Для заданного массива выбирается один элемент, который разбивает
остальные элементы на два подмножества - те, что меньше, и те,
что не меньше него. Та же процедура рекурсивно применяется и к двум
полученным подмножествам. Если в подмножестве менее двух элементов,
то сортировать нечего, и рекурсия завершается. Наша версия быстрой
сортировки, разумеется, не самая быстрая среди всех возможных,
но зато одна из самых простых.
В качестве делящего элемента мы используем серединный элемент.
*/
/* qsort: сортирует v[left]...v[right] по возрастанию */
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right) /* ничего не делается, если */
return; /* в массиве менее двух элементов */
swap(v, left, (left + right)/2); /* делящий элемент */
last = left; /* переносится в v[0] */
for(i = left+1; i <= right; i++) /* деление на части */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last); /* перезапоминаем делящий элемент */
qsort(v, left, last-1);
qsort(v, last+1, right);
}
/* swap: поменять местами v[i] и v[j] */
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
int main()
{
int arr[] = {9,3,1,5,8,2,4,7};
int len = sizeof(arr)/sizeof(int);
for (int i=0; i<len; ++i)
printf("%d;", arr[i]);
printf("\n");
qsort(arr, 0,len-1);
for (int i=0; i<len; ++i)
printf("%d;", arr[i]);
printf("\n");
return 0;
}
/***********************************/
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int> &a, int l, int r);
void qs(vector<int> &a, int l, int r);
int main()
{
vector<int> a;
a.push_back(9);
a.push_back(3);
a.push_back(1);
a.push_back(5);
a.push_back(8);
a.push_back(2);
a.push_back(4);
a.push_back(7);
qs(a,0,a.size()-1);
for(int i=0;i<8; i++)
cout << a[i]<< " ";
return 0;
}
void qs(vector<int> &a, int l, int r)
{
if(l<r)
{
int s=partition(a,l,r);
qs(a, l, s - 1);
qs(a, s + 1, r);
}
}
int partition(vector <int> &a,int l,int r)
// Introduction to Algorithmes
// Cormen, Leiserson, Rivest
{
int x=a[r];
int i=l-1;
int j;
for (j=l; j<=r-1; ++j) {
if (a[j]<=x) {
i=i+1;
swap(a[i], a[j]);
}
}
swap(a[i+1], a[r]);
return i+1;
}