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
    19 июн 2017 в 10:40
  • Эта сортировка - часть курсового проекта. И преподаватель обязал реализовывать алгоритм самому 19 июн 2017 в 10:46

1 ответ 1

5

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

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

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

На этот

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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