Сортировка массива строк методом подсчета

@graynk · Регистрация: 08.01.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте. Вкратце, задача такова - написать программу, упорядочивающую массив строк в алфавитном порядке методом сортировки подсчетом. Использовать указатели на строки.
Обычный алгоритм сортировки подсчетом, если верить вики, такой:

Code
1
2
3
4
5
6
7
8
9
10
SimpleCountingSort
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    b = 0;
    for j = 0 to k - 1
        for i = 0 to C[j] - 1
            A[b] = j;
            b = b + 1;

Но у меня-то массив из строк, т.е. C[A[i]] особо не сделаешь. Единственный способ, который у меня получается придумать - брать ASCII коды, но это явно будет очень громоздко, и вообще не так как задумывалось.
Если верить той же вики, реализация этого алгоритма на C++ такая:

C++
1
2
3
4
5
6
7
8
9
10
11
12
int a[q],b[q],i,j;
 
for (i = 0; i < q; i++)
{
    j = i;
    while (j > 0 && b[j-1] > a[i])
    {
        b[j] = b[j-1];
        j = j - 1;
    }
    b[j] = a[i];
}

Пользуясь этой реализацией, я сделал такое решение:

C++
1
2
3
4
5
6
7
8
9
10
for (i=0;i<size;i++)
    {  
        j=i;
        while (j>0 && strcmp(key[j-1],mas[i])>0)
        {
            strcpy(key[j],key[j-1]);
            j--;
        }
        strcpy(key[j],mas[i]);
    }

Оно работает, и работает корректно. НО. Во-первых, я ничего общего с алгоритмом сортировки в этой реализации не вижу, это вообще очень сильно напоминает сортировку вставками. А во-вторых по условию нужно пользоваться указателями, а этого здесь тоже нет. Подскажите, как сделать правильно?

Добавлено через 45 минут
Вопрос снят, вот нормальный алгоритм: http://cs421622.userapi.com/v4... e2Asog.jpg
Вот финальный код.

C++
1
2
3
4
5
6
7
8
9
10
for (i=0;i<size;i++)
    {
        gets(*(mas+i));
        *(key+i)=0;
    }
    for (i=size-1;i>0;i--)
        for (j=i-1;j>=0;j--)
            if (strcmp(*(mas+i),*(mas+j))<0) key[j]++;
            else key[i]++;
    for (j=0;j<size;j++) mas2[key[j]]=mas[j];

@taras atavin · 08.01.2013, 18:11

Сообщение от graynk

Обычный алгоритм сортировки подсчетом, если верить вики, такой:

Ссылку на статью в студию.

@Catstail · 08.01.2013, 18:16

Сообщение от graynk

вот нормальный алгоритм:

- гм... А разве сортировка подсчетом для строк применима? То, что у тебя, на сортировку подсчетом не похоже.

@graynk · 08.01.2013, 18:24 **[ТС]**

Сообщение от taras atavin

Ссылку на статью в студию.

http://ru.wikipedia.org/wiki/%... 0%BE%D0%BC

Добавлено через 47 секунд

Сообщение от Catstail

- гм... А разве сортировка подсчетом для строк применима? То, что у тебя, на сортировку подсчетом не похоже.

видимо применима, раз нам дали такое задание на лабораторной, и дали такой алгоритм на лекции.

@Catstail · 08.01.2013, 18:33

Статья из Википедии правильная... Но, обрати внимание, она сплошь - о целых числах (отнюдь не о строках).

@graynk · 08.01.2013, 18:37 **[ТС]**

Сообщение от Catstail

Статья из Википедии правильная... Но, обрати внимание, она сплошь - о целых числах (отнюдь не о строках).

и кусок с реализацией на с++ тоже правильный? он же алгоритму следует примерно никак.
я и заметил, что она о целых числах. у меня-то задание про строки. не я ж задание придумал, преподаватели. собственно, они и дали ответ, просто не сразу этот алгоритм в лекциях нашел. может они живут в своей собственной вселенной, придумывают новые алгоритмы, и дают им имена уже существующих, черт их знает.

@Catstail · 08.01.2013, 18:41

Да, этот алгоритм будет работать... Но вся прелесть сортировки подсчетом состоит в том, что его производительность растет как N. А алгоритм, который вам дали на лекции, похоже, будет иметь производительность ~ N².

Добавлено через 1 минуту

Сообщение от graynk

и кусок с реализацией на с++ тоже правильный?

- да, но неполный (мне кажется).

@graynk · 08.01.2013, 18:43 **[ТС]**

Сообщение от Catstail

Да, этот алгоритм будет работать... Но вся прелесть сортировки подсчетом состоит в том, что его производительность растет как N. А алгоритм, который вам дали на лекции, похоже, будет иметь производительность ~ N².

да, в лекциях написано, что N² будет)

@Catstail · 08.01.2013, 18:47

Сообщение от graynk

да, в лекциях написано, что N2 будет)

- вот и я о том же... Единственное его преимущество в том, что пока формируются ключи, строки "лежат на своих местах", а не перемещаются (как это было бы при сортировке вставками, выбором, обменом и т.д.)

Новые блоги и статьи Все статьи Все блоги /
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .

@Catstail Супер-модератор 38169 / 21104 / 4307 Регистрация: 12.02.2012 Сообщений: 34,693 Записей в блоге: 14
	08.01.2013, 18:33
	Статья из Википедии правильная... Но, обрати внимание, она сплошь - о целых числах (отнюдь не о строках). 0