Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Алгоритм Хоара?

Автор: Mpak 17.12.2006, 18:26

В результате выполнения алгоритма массив делится на два массива, которые сортируются этим же методом и снова делятся на два массива и так далее пока не разделится на части, в которых меньше 9 элементов.
Как организовать это ветвление(разбиение)? Посоветовали работать со стеком. Что это(стек) такое? И какие функции используются?
И если кто знает, что такое "Способ простой вставки" (тоже метод сортировки массива)?

Автор: Anark1 17.12.2006, 18:32

Писал 2 метода сортировки на паскале.
Стэк это работа с памятью по принципу - "первый вошел - последний вышел".
Хоара хорошо писать с помощью рекурсии. Каждый раз вызывается по две рекурсии. Первая от первого элемента до разделителя. Вторая - от разделителя до последнего. И ветвление до тех пор пока не получишь n массивов , в каждом из которых 1 элемент.

Автор: Mpak 17.12.2006, 18:43

Ок.

Спасибо.
Теперь что такое рекурсия?

smile

Автор: GIK 17.12.2006, 19:10

Цитата

Теперь что такое рекурсия?

Рекурсия-повторный вызов метода, при этом значения между вызовами хранятся в стеке.(по крайней мере так было в JS)
Щас покумекаю над алгоритмом.

Автор: Anark1 17.12.2006, 20:04

Пример рекурсии - подсчет двойки в степени N.
В теле функции n происходит вызов
n=(n-1) * 2.
Если прокрутишь в отладичке то поймешь что сначала функция проходит сама себя, а потом начинает собирать значения. Как бы с конца. Это и есть стэк. Сори если немножко коряво объяснил.

Автор: GIK 17.12.2006, 20:52

Mpak, вобщем тебе надо создать список из массивов. Кол-во массивов нужно как-то регулировать.
Вобщем вот пример который просто урезает массив.

Код


#include<iostream>
#include<vector>
using namespace std;

vector<int> fakOf(vector<int> vec);

vector<int> fakOf(vector<int> vec){
vector<int>::iterator p=vec.begin();
if(vec.size()>9){vec.erase(p+(vec.size()/2), p+(vec.size()));
return vec;
}
return vec;
}


int main(int argc, char* argv[])
{
 vector<int> vec(36);
 vector<int>:: iterator p;
 for(int i=0; i<vec.size(); i++){
 vec[i]=i+(i*2);
 }
 for(int i=0; i<vec.size(); i++){
 cout << vec[i]<< endl;
 }
 vec=fakOf(vec);   

 cout<< "О чудо, мы удалили эллементы" << endl;
 for(int i=0; i<vec.size(); i++){
 cout << vec[i]<< endl;
 }

 char ch;
 cin>>ch;
     return 0;

}

нужный вариант долго делать, но модера помогут, а я умываю руки smile

да ксатати, размер массива (вектора) можно изменять, и вообще вектор класная вешь, но жрет память...

Добавлено @ 20:59
Это конечно не алгоритм Хоара, но и уже не Хреново smile

Автор: Mpak 17.12.2006, 21:04

хм.... спасибо всем smile

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

Автор: GIK 17.12.2006, 21:09

Цитата

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

А чет тут разбиратся то smile

Если че не понятно, спрашивай, тебе помогут smile