Рекурсивный метод сортировки

← →
Мистер Блин (2009-01-08 17:34) [0]

Добрый день помогите пожалуйста реализовать рекурсивный методсортировки на C++(можно и на Delphi, но С++ предпочтительнее).

РЕКУРСИВНЫЙ МЕТОД (МЕТОД БЫСТРОЙ СОРТИРОВКИ)

Изложим идею метода. В исходном массиве А выбирается некоторый элемент Х(барьерный элемент). Нашей целью является запись Х "на свое место" k, такое что слева от Х находились бы элементы массива, меньшие или равные Х, а справа - элементы массива, большие Х, т.е. массив А будет иметь вид:
A[1],A[2],...,A[k-1], A[k]=X ,A[k+1],...,A[n].
В результате элемент A[k] оказвается на своем месте и исходный массив А делится на две неупорядоченные области, барьером между которыми является элемент A[k]. Дальнейшие действия очевидны - независимо сортировать полученные части таким образом до тех пор, пока не останутся части массива, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.
Пример:
Исходный массив состоит из 8 элементов:
8 12 3 7 19 11 4 16
В качестве барьерного элемента возьмем средний элемент массива - 7. ПРоизведя необходимые перестановки, получим:
(4 3) 7 (12 19 11 8 16)
элемент 7 находится на своем месте. Продолжаем сортировку.
Левая часть:
(3) 4 7 (12 19 11 8 16)
3 4 7 (12 19 11 8 16)
Правая часть:
3 4 7 (8) 11 (19 12 16)
3 4 7 8 11 (19 12 16)
3 4 7 8 11 12 (19 16)
3 4 7 8 11 12 (16) 19
3 4 7 8 11 12 16 19.

есть наработки
#include <iostream> #include <valarray> #include <cmath> using namespace std; int main() { int n,b,temp,d,g; cin>>n; valarray<int> mass(n); for(int i=0;i<n;i++){ cin>>b; mass[i]=b;} d= (n/2)-1; g=-1; for(int j=0; j<n;j++){ if(mass[j]<mass[d]){ g++; temp=mass[g]; mass[g]=mass[j]; mass[j]=temp; }} cout<<endl; for(int i=0;i<n;i++) cout<<mass[i]<<endl; }

← →
TUser © (2009-01-08 18:48) [1]

> можно и на Delphi

глять в генофонде - метод Sort у класса TList

а лучше нипиши сам

← →
test (2009-01-08 19:02) [2]

<твой программ файл>\<delphi твоя версия>\Demos\sorting
В тут есть

← →
Zeqfreed © (2009-01-08 19:04) [3]

И зачем алгоритмы заставляют реализовывать не прочитав предварительно курс декомпозиции, оформления кода и наименования переменных? :)

Чтобы сделать рекурсивный алгоритм необходимо наличие хотя бы одной функции, которую ты бы вызывал рекурсивно ;)

← →
Мистер Блин (2009-01-08 19:20) [4]

Я знаю, но проблема в том, чтоя хз, как это делать.

← →
test (2009-01-08 19:22) [5]

Мистер Блин (08.01.09 19:20) [4]
В Гугле забанили и не дают достпу даже на чтение в папку Демос Дельфи, сочуствую.

> Мистер Блин (08.01.09 19:20) [4]

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

static void swap(char *data, int a, int b)
{
/* Поменять значения a-того и b-того элементов */
}

static int rotate(char *data, int left, int right)
{
int pivotIdx = (right - left) / 2 + left;
char pivot = data[pivotIdx]; //Значение символа в опорной точке
swap(data, pivotIdx, right);

int insertionPoint = left;
int i;
for (/* Идем слева направо */) {
if (/* текущий символ меньше опорного? */) {
swap(data, i, insertionPoint);
/* Увеличиваем текущую позицию */
}
}

swap(data, insertionPoint, right);
/* Вернуть текущую точку вставки */
}

static void quicksort(char *data, int left, int right)
{
if (right <= left) return;

int midPoint = rotate(data, left, right);
quicksort(/* сортируем все, что слева от midPoint */);
quicksort(/* сортируем все, что справа от midPoint */);
}

int main(int argc, char **argv)
{
char *data = "144385795asdf2g7gd87fg58g5g2d7gd5hg6h478e6t4ui5o8637";
char *p = strdup(data);
quicksort(p, 0, strlen(data) - 1);

printf("%s\n", p);

return 0;
}

Ну, хотя бы так, чтоли :)

← →
Мистер Блин (2009-01-08 20:28) [7]

Сорри, но у меня ещё один вопрос. Вот то что у меня получилось
#include<iostream> #include <math.h> #include <valarray> using namespace std; template <class T> void Qsort(T *A, int a, int b){ int i, j, m; T c; if (a>=b) return; for (i=a, j=b, m=1; i<j; m>0?j--:i++){ if (A[i]>A[j]){ c = A[i]; A[i] = A[j]; A[j] = c; m = -m;}} Qsort(A, a, i-1); Qsort(A, i+1, b); return; } int main(){ int b; int A[8]; for (int i=0; i<8; i++){ // Заполнение массивов cin>>b; A[i] = b;} Qsort(A, 0, 7); for(int i=0;i<8;i++) cout<<A[i]<<endl; }
Почему когда я пытаюсь заменить
int a[8] на
int n; cin>>n; valarray<int> a[n];
Программа отказывается запускаться?!

← →
Канадец (2009-01-09 01:02) [8]

Почему когда я пытаюсь заменить
...
Программа отказывается запускаться?!

Потому что статических массивов произвольной длины в С++ не бывает, да они тебе и не нужны.

int n; cin>>n; valarray<int> a(n);

Рекурсивный метод сортировки Найти похожие ветки