Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Для новичков > Segmentation fault в Сортировке слиянием


Автор: ozeron 21.3.2012, 20:08
Всем доброго времени суток,
   Сейчас прохожу курс по https://www.coursera.org/algo/class. Собственно в первом разделе рассматривается сортировка слиянием, вот я и решил ее написать. Заранее извиняюсь, если у меня получился уж очень кривой велосипед)) Но при компиляции мне пишет в одном компиляторе: 
Скрытый текст
 Applications/Developer/TextMate.app/Contents/SharedSupport/Bundles/C.tmbundle/Support/bin/bootstrap.sh: line 7:  1721 Segmentation fault: 11  "$3".out

А в другом:
Скрытый текст
 warning: Unable to restore previously selected frame.
No memory available to program now: unsafe to call malloc
warning: Unable to restore previously selected frame. 


Вот собственно код программы:
Скрытый текст

Код

#include <fstream>
using namespace std;

void mergeSort(int arr[], int length);
void merge(int leftArr[], int rightArr[], int Arr[], int length);

int main()
{
    ifstream  in(" input.txt");
    ofstream out("output.txt");
    int length = 0;
    in>>length;
    int *arr = new int [length];
    for(int i=0; i<length; i++) in>>arr[i];
    mergeSort(arr, length);
    for (int i=0; i<length; i++) out<<arr[i];
    delete [] arr;
    return 0;    
}

void merge(int leftArr[], int rightArr[], int Arr[], int length)
{
    int lLength=length/2; int i = 0;
    int rLength=length-lLength; int j=0;
    for (int k=0; k<length; k++) {
        if((i<lLength) && (leftArr[i] < rightArr[j])) {Arr[k]=leftArr[i]; i++;} else
        if((j<rLength) && (leftArr[i] > rightArr[j])) {Arr[k]=rightArr[j]; j++;}
    }
}


void mergeSort(int arr[], int length)
{
    if (length != 1) {
    int lLength = length/2;
    int rLength = length - length/2;
    int *lArr = new int [lLength];
    int *rArr = new int [rLength];
    for (int i=0; i<lLength ; i++) lArr[i]=arr[i];
    for (int j=0; j<rLength; j++) rArr[j]=arr[lLength+j];
    
    mergeSort(lArr, lLength);
    mergeSort(rArr, rLength);
    merge(lArr,rArr,arr,length);
    
    delete [] lArr;
    delete [] rArr;
    } else ;
}




Походу где-то неакуратно у меня с дин. массивами, но не могу найти где( 
Помогите кто-нибудь пожалуйста!

Автор: ozeron 21.3.2012, 20:44
Нашел ошибку, осталось только алгоритм исправить:

 length != 1 >> length > 1 

Там даже ошибка была в том, что файл не находило и инициализоровали массивы.

Код

#include "stdafx.h"
#include <fstream>
#include <iostream>
using namespace std;

void mergeSort(int arr[], int length);
void merge(int leftArr[], int rightArr[], int Arr[], int length);

int main()
{
    ifstream  in(" input.txt");
    ofstream out("output.txt");
    int length = 0;
    cin>>length;
    int *arr = new int [length];
    for(int i=0; i<length; i++) cin>>arr[i];
    mergeSort(arr, length);
    for (int i=0; i<length; i++) cout<<arr[i];
    delete [] arr;
    cin.get();
    return 0;    
}

void merge(int leftArr[], int rightArr[], int Arr[], int length)
{
    int lLength=length/2; int i = 0;
    int rLength=length-lLength; int j=0;
    for (int k=0; k<length; k++) {
        if((i<lLength) && (leftArr[i] < rightArr[j])) {Arr[k]=leftArr[i]; i++;} else
        if((j<rLength) && (leftArr[i] > rightArr[j])) {Arr[k]=rightArr[j]; j++;}
    }
}


void mergeSort(int arr[], int length)
{
    if (length > 1) {
    int lLength = length/2;
    int rLength = length - length/2;
    int *lArr = new int [lLength];
    int *rArr = new int [rLength];
    for (int i=0; i<lLength ; i++) lArr[i]=arr[i];
    for (int j=0; j<rLength; j++) rArr[j]=arr[lLength+j];
    
    mergeSort(lArr, lLength);
    mergeSort(rArr, rLength);
    merge(lArr,rArr,arr,length);
    
    delete [] lArr;
    delete [] rArr;
    } else ;
}

Автор: borisbn 21.3.2012, 21:13
Честно говоря, неохота разбираться, но алгоритм, судя по всему, нерабочий (вернее реализация)
http://liveworkspace.org/code/737ce499975046e2e951340ad16def20

Добавлено через 2 минуты и 49 секунд
а в эту строчку
Цитата(ozeron @  21.3.2012,  20:44 Найти цитируемый пост)
length != 1 >> length > 1 

я дооооолго втыкал, пока не понял, что << это не оператор сдвига, а "нужно было заменить на"

Автор: ozeron 21.3.2012, 23:40

 Да алгоритм не работает %), буду думать.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)