Начну с описания задачи. Вводим int в вектор, потом его сортируем. Сортируем методом merge sort. Сразу скажу, что готовый код этого способа мне не интересен, хочется самому сделать. Сейчас я дописал код и настало славное время дебаггинга. Получаю exception, outofrange. Я новичок, так что не могу нормально отследить, в какой момент она происходит и что именно в этих ячейках памяти. В связи с этим я добавлю сюда код. Также добавлю ссылку на файл Source.cpp с этим же кодом.
Если я что-то делаю неправильно, буду рад услышать, что именно. Если что то можно сделать лучше, буду рад выслушать, но имейте в виду, что я еще не совсем на ТЫ с языком. Ну и конечно буду рад услышать, в чем ошибка и как ее находить. Если требуется еще информация, спрашивайте.
Заранее спасибо.
#include <iostream>
#include <conio.h>
#include <vector>
using namespace std;
extern int merge(vector<int> *,vector<int> *,vector<int> *);
extern int divide(vector<int> *);
extern int input(vector<int> *);
int main()
{
vector<int> original; //input vector
input (&original); //write input to vector<int> original
divide(&original); //pass the vector
for(unsigned int i=0;i<original.size();i++)//output the results
cout<<original.at(i);
_getch();
return EXIT_SUCCESS;
}
int input(vector<int> *inVec) //read all input until non-integer
{
int tmp;
while (cin>>tmp)
inVec->push_back(tmp);
for(unsigned int i=0;i<inVec->size();i++)
cout<<inVec->at(i)<<endl;
_getch();
return EXIT_SUCCESS;
}
int divide(vector<int> *original)
{
int origL=original->size();
if(origL>1)
{
vector<int> first; //vectors for holding 2 halfs of "original"
vector<int> second; //
first.assign(original->begin(),original->begin()+origL/2);//1st half of "original"
second.assign(original->begin()+origL/2+1,original->end());//2nd half
divide(&first); //recursive call until "first" and
divide(&second); //"second" include only one number
merge(&first,&second,original);//merge first and second back into one vector
}
return EXIT_SUCCESS;
}
int merge(vector<int> *A,vector<int> *B,vector<int> *original)
{
//clear the original vector. we will use it to store sorted results.
original->erase(original->begin(),original->end());
unsigned int i=0,j=0;
//out the smallest number from A and B into
//original[0] and so on. This makes it a
//sorting algorithm.
for(i=0;i<A->size();i++)
{
if((A->at(i)<B->at(j))||(A->at(i)=B->at(j)))
original->push_back(A->at(i));
else{
original->push_back(B->at(j));
i--;j++;}
}
//the ABOVE loop scans all vector A.
//if there are still uncopied elements in
//vector B, then we check for them and
//push them into original.
if(A->size()+B->size()>original->size())
for(i=j;i<B->size();i++)
original->push_back(B->at(i));
return EXIT_SUCCESS;
}
ССЫЛКА НА .срр
https://docs.google.com/file/d/0ByVN9ccAyFY2LXpNMy1CNXBkSjA/edit
Примечание:
http://en.wikipedia.org/wiki/File:Merge-sort-example-300px.gif
Суть алгоритма показана тут.
Примечание:
Dmitro,
спасибо за ответ. Не питонист. Блоки кода можно не заключать в скобки, если там только одна строка, ибо она входит в цикл/условие по умолчанию. Скобки нужны, чтобы включить туда следующие строки.
Про больше ИЛИ равно я и сам заметил, посмеялся :)
С циклом while отличная идея, спасибо :)
Впрочем, ошибка остается и ловить ее я не умею. :(
Примечание:
Dmitro, пока писал, заметил, что не получится написать через while. Если у нас закончится вектор A раньше вектора B, то в условии if(A->at(i)<=B->at(j)) i будет указывать на ячейку после последней и сравнивать с ней значение в векторе В. А это очередной std::out_of_range. :(
Примечание:
Хех, я а ведь у меня та же проблема в моем for. Вопрос закрыт :) Лучшим ответом выберу dmitro.
RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.
Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.
Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.