2

Имеется массив char с 14k русских слов. Необходимо отсортировать этот массив по алфавиту. Готовые решения (например, qsort()) использовать нельзя. Решил сам реализовать алгоритм быстрой сортировки. И возникла проблема в том, что массив сортируется не до конца. Т.е. в результате, например, сначала идут слова на букву 'а', потом на букву 'б', а затем снова на 'а'. И не могу понять, в чем ошибка / недоработка

Вот основной код:

const int N = 14000; // Количество слов
const int M = 30;    // Максимальное количество букв в слове

char words[N][M];    // Массив слов

int compare(const char *arg1, const char *arg2)
{
   int i = _strcmpi(arg1, arg2);

   // Решение проблем с букой ё при сортировке
   if ((i >= 40 && i <= 45) || (i <= -40 && i >= -45)) 
       i *= -1; 

   return i;
}

void sort(int begin, int end)
{
    char* m = words[(begin + end) / 2];
    int l = begin;
    int r = end;
    char temp[M];

    while (l <= r)
    {
        while (compare(words[l], m) < 0) l++;

        while (compare(words[r], m) > 0) r--;

        if (l <= r)
        {
            strcpy_s(temp, words[l]);
            strcpy_s(words[l], words[r]);
            strcpy_s(words[r], temp);
            l++;
            r--;
        }
    }

    if (l < end)
        sort(l, end);
    if (begin < r)
        sort(begin, r);
} 

int main()
{
    /*
        Считывание слов из файла
        ...
    */

    sort(0, N-1)
}
2
  • 2
    "Готовые решения (например, qsort()) использовать нельзя." - по какой причине, простите?
    – Kromster
    Commented 19 июн. 2017 в 10:40
  • Эта сортировка - часть курсового проекта. И преподаватель обязал реализовывать алгоритм самому Commented 19 июн. 2017 в 10:46

1 ответ 1

5

Я понял, в чём была проблема. Для получения серединного (опорного) элемента, мы использовали указатель на этот самый элемент. Но во время работы алгоритма значение опорного элемента может меняться.

Решением проблемы стала замена этого участка кода

char* m = words[(begin + end) / 2];

На этот

char m[M];
strcpy_s(m, mas[(begin + end) / 2]);

Спасибо всем, кто думал над моим вопросом.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.