У меня проблемы с реализацией быстрой сортировки для сортировки массива строк. Я также относительно новичок в c ++, поэтому все еще борюсь с некоторыми проблемами там. Прямо сейчас мой код правильно читает и создает массив строк, но у меня возникают проблемы, когда я пытаюсь использовать алгоритм быстрой сортировки. Первая проблема, с которой я сталкиваюсь, заключается в том, что я считаю, что рекурсия не останавливается, когда должна. Я получаю ошибку сегментации после небольшой работы быстрой сортировки.
Код (измененный):
#include "MyParser.h"
#include <iostream>
#include <fstream>
#include <string>
void resize(string*& words, int size)
{
string* newArray = new string[size*2];
for (int i = 0; (i < size)&&(i<size*2); i++)
newArray[i] = words[i];
for (int i = size; i < size*2; i++)
newArray[i] = "";
delete[] words;
words = newArray;
}
void partitionArray(string*& words, int& left, int& right, int pi)
{
int i = left;
int j = right;
string tmp;
string pivot = words[pi];
while (i < j) {
string str1 = words[i];
string str2 = words[j];
while ((str1.compare(pivot) < 0) && (i < right))
i++;
while ((str2.compare(pivot) >= 0) && (j > left))
j--;
if (i <= j)
{
tmp = words[i];
words[i] = words[j];
words[j] = tmp;
i++;
j--;
}
};
}
void quickSort(string*& words, int left, int right)
{
int i = left;
int j = right;
string tmp;
string pivot = words[(left + right) / 2];
/* partition */
int pivotIndex = (left + right) / 2;
pivotIndex = partitionArray(words, 0, right, pivotIndex);
cout << "start recursion" << endl;
/* recursion */
if (left < j)
quickSort(words, left, j);
if (i < right)
quickSort(words, i, right);
}
int main()
{
// define file reader
ofstream outData;
outData.open("logData.txt");
Parser* myParser = new Parser("testData.txt");
int sizeOfArray = 500;
string* words = new string[sizeOfArray];
int index = 0;
while(myParser->hasTokens())
{
if (index >= sizeOfArray)
{
resize(words, sizeOfArray);
sizeOfArray = sizeOfArray*2;
}
string currentWord = myParser->nextToken();
if (currentWord != "")
{
words[index] = currentWord;
index++;
}
}
int lastWordInArrayIndex = index;
quickSort(words, 0, lastWordInArrayIndex);
return 0;
}
Любая помощь по этому вопросу будет принята с благодарностью!
ОБНОВЛЕНО
прямо сейчас он правильно отсортирует следующие 11 элементов:
adfgh
btyui
dfghj
eerty
fqwre
kyuio
Verty
wwert
yrtyu
zbsdf
zsdfg
но при попытке отсортировать следующий проанализированный текст, свободный от всех разделителей, но хуже "like-this" с одним дефисом или словами с апострофом вроде "they", он не завершается:
Через три дня после ссоры князь Степан Аркадьич
Облонский - Стива, как его называли в модном мире
проснулся в свое обычное время, то есть в восемь часов
утром не в спальне жены, а на кожаном покрытии
диван в своем кабинете. Он перевернул свой толстый, ухоженный
человек на упругом диване, как будто он погружается в длинный
спать снова; он энергично обнял подушку с другой стороны
и уткнулся лицом в него; но вдруг он вскочил, сел
на диван и открыл глаза.
"Да, да, как это было сейчас?" подумал он, идя над своей мечтой.
«Теперь, как это было? Чтобы быть уверенным! Алабин обедал в
Дармштадт; нет, не Дармштадт, а что-то американское. Да, но
тогда Дармштадт был в Америке. Да, Алабин давал ужин
на стеклянных столах и пели столы, Il Mio Tesoro - не Il Mio
Тесоро, хотя, но что-то лучше, и были
маленькие графинчики на столе, и они тоже были женщинами, "он
вспомнил.
Опять же, любая помощь по этому вопросу будет принята с благодарностью!