Merge sort c++. Надо найти ошибку.

Компьютеры программирование C++ cpp VS12

Начну с описания задачи. Вводим 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.
Ответы:
for(unsigned int i=0;i<original.size();i++) не хватает в конце ";" вроде
Константин, перед скобками точка с запятой не нужны
вы случаем не питонист? у вас как минимум три блока кода не заключены в скобки. должно быть вот так.
int main(){
......
for(unsigned int i=0;i<original.size();i++) {
cout<<original.at(i);
}
.....
}


12 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.