Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Алгоритм Хоара? или сортировка массива :) 
:(
    Опции темы
Mpak
Дата 17.12.2006, 18:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 445
Регистрация: 12.11.2006

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


--------------------
В любой откомпилированной программе есть, по крайней мере, одна ошибка...
P.S. А у меня их минимум две...
PM MAIL ICQ   Вверх
Anark1
Дата 17.12.2006, 18:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 622
Регистрация: 15.12.2006
Где: RF -> Moscow

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


--------------------
Enjoy yourself, still you can...;)

user posted image

user posted image
PM MAIL ICQ   Вверх
Mpak
Дата 17.12.2006, 18:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 445
Регистрация: 12.11.2006

Репутация: нет
Всего: 7
Ок.  smile 
 Спасибо.
Теперь что такое рекурсия?

 smile 


--------------------
В любой откомпилированной программе есть, по крайней мере, одна ошибка...
P.S. А у меня их минимум две...
PM MAIL ICQ   Вверх
GIK
Дата 17.12.2006, 19:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Добрый человек
**


Профиль
Группа: Участник
Сообщений: 985
Регистрация: 3.6.2005
Где: я только не небыв ал

Репутация: 1
Всего: 14
Цитата

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

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


--------------------
Математика=>пиво=> програмирование, три вещи последовательны и совместимы !!!
Программирование - это не деятельнось! Программирование - это состояние души!
Бог - самый крутой программист.
PM MAIL ICQ   Вверх
Anark1
Дата 17.12.2006, 20:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 622
Регистрация: 15.12.2006
Где: RF -> Moscow

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


--------------------
Enjoy yourself, still you can...;)

user posted image

user posted image
PM MAIL ICQ   Вверх
GIK
Дата 17.12.2006, 20:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Добрый человек
**


Профиль
Группа: Участник
Сообщений: 985
Регистрация: 3.6.2005
Где: я только не небыв ал

Репутация: 1
Всего: 14
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 

Это сообщение отредактировал(а) GIK - 17.12.2006, 21:00


--------------------
Математика=>пиво=> програмирование, три вещи последовательны и совместимы !!!
Программирование - это не деятельнось! Программирование - это состояние души!
Бог - самый крутой программист.
PM MAIL ICQ   Вверх
Mpak
Дата 17.12.2006, 21:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 445
Регистрация: 12.11.2006

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


--------------------
В любой откомпилированной программе есть, по крайней мере, одна ошибка...
P.S. А у меня их минимум две...
PM MAIL ICQ   Вверх
GIK
Дата 17.12.2006, 21:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Добрый человек
**


Профиль
Группа: Участник
Сообщений: 985
Регистрация: 3.6.2005
Где: я только не небыв ал

Репутация: 1
Всего: 14
Цитата

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

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


--------------------
Математика=>пиво=> програмирование, три вещи последовательны и совместимы !!!
Программирование - это не деятельнось! Программирование - это состояние души!
Бог - самый крутой программист.
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0462 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.