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

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

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

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

Код

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++

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++

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++

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 будет)

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

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	08.01.2013, 18:11	2
	Сообщение от graynk Обычный алгоритм сортировки подсчетом, если верить вики, такой: Ссылку на статью в студию. 0

@Catstail Модератор 37299 / 20733 / 4272 Регистрация: 12.02.2012 Сообщений: 34,122 Записей в блоге: 14
	08.01.2013, 18:16	3
	Сообщение от graynk вот нормальный алгоритм: - гм... А разве сортировка подсчетом для строк применима? То, что у тебя, на сортировку подсчетом не похоже. 0

@graynk 0 / 0 / 0 Регистрация: 08.01.2013 Сообщений: 4
	08.01.2013, 18:24 [ТС]	4
	Сообщение от taras atavin Ссылку на статью в студию. http://ru.wikipedia.org/wiki/%... 0%BE%D0%BC Добавлено через 47 секунд Сообщение от Catstail - гм... А разве сортировка подсчетом для строк применима? То, что у тебя, на сортировку подсчетом не похоже. видимо применима, раз нам дали такое задание на лабораторной, и дали такой алгоритм на лекции. 0

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

@graynk 0 / 0 / 0 Регистрация: 08.01.2013 Сообщений: 4
	08.01.2013, 18:37 [ТС]	6
	Сообщение от Catstail Статья из Википедии правильная... Но, обрати внимание, она сплошь - о целых числах (отнюдь не о строках). и кусок с реализацией на с++ тоже правильный? он же алгоритму следует примерно никак. я и заметил, что она о целых числах. у меня-то задание про строки. не я ж задание придумал, преподаватели. собственно, они и дали ответ, просто не сразу этот алгоритм в лекциях нашел. может они живут в своей собственной вселенной, придумывают новые алгоритмы, и дают им имена уже существующих, черт их знает. 0

@Catstail Модератор 37299 / 20733 / 4272 Регистрация: 12.02.2012 Сообщений: 34,122 Записей в блоге: 14
	08.01.2013, 18:41	7
	Да, этот алгоритм будет работать... Но вся прелесть сортировки подсчетом состоит в том, что его производительность растет как N. А алгоритм, который вам дали на лекции, похоже, будет иметь производительность ~ N². Добавлено через 1 минуту Сообщение от graynk и кусок с реализацией на с++ тоже правильный? - да, но неполный (мне кажется). 1

@graynk 0 / 0 / 0 Регистрация: 08.01.2013 Сообщений: 4
	08.01.2013, 18:43 [ТС]	8
	Сообщение от Catstail Да, этот алгоритм будет работать... Но вся прелесть сортировки подсчетом состоит в том, что его производительность растет как N. А алгоритм, который вам дали на лекции, похоже, будет иметь производительность ~ N². да, в лекциях написано, что N² будет) 0

@Catstail Модератор 37299 / 20733 / 4272 Регистрация: 12.02.2012 Сообщений: 34,122 Записей в блоге: 14
	08.01.2013, 18:47	9
	Сообщение от graynk да, в лекциях написано, что N2 будет) - вот и я о том же... Единственное его преимущество в том, что пока формируются ключи, строки "лежат на своих местах", а не перемещаются (как это было бы при сортировке вставками, выбором, обменом и т.д.) 0