Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
graynk
0 / 0 / 0
Регистрация: 08.01.2013
Сообщений: 4
08.01.2013, 18:08     Сортировка массива строк методом подсчета #1
Здравствуйте. Вкратце, задача такова - написать программу, упорядочивающую массив строк в алфавитном порядке методом сортировки подсчетом. Использовать указатели на строки.
Обычный алгоритм сортировки подсчетом, если верить вики, такой:
Код
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/v4216227...Gg6ye2Asog.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];
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2013, 18:08     Сортировка массива строк методом подсчета
Посмотрите здесь:

Сортировка строк матрицы методом Шелла C++
Сортировка методом подсчета C++
C++ сортировка массива методом выбора в с++
Сортировка массива методом включения C++
C++ Сортировка массива методом пузырька
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
08.01.2013, 18:11     Сортировка массива строк методом подсчета #2
Цитата Сообщение от graynk Посмотреть сообщение
Обычный алгоритм сортировки подсчетом, если верить вики, такой:
Ссылку на статью в студию.
Catstail
Модератор
 Аватар для Catstail
21451 / 10236 / 1667
Регистрация: 12.02.2012
Сообщений: 17,108
08.01.2013, 18:16     Сортировка массива строк методом подсчета #3
Цитата Сообщение от graynk Посмотреть сообщение
вот нормальный алгоритм:
- гм... А разве сортировка подсчетом для строк применима? То, что у тебя, на сортировку подсчетом не похоже.
graynk
0 / 0 / 0
Регистрация: 08.01.2013
Сообщений: 4
08.01.2013, 18:24  [ТС]     Сортировка массива строк методом подсчета #4
Цитата Сообщение от taras atavin Посмотреть сообщение
Ссылку на статью в студию.
http://ru.wikipedia.org/wiki/%D0%A1%...82%D0%BE%D0%BC

Добавлено через 47 секунд
Цитата Сообщение от Catstail Посмотреть сообщение
- гм... А разве сортировка подсчетом для строк применима? То, что у тебя, на сортировку подсчетом не похоже.
видимо применима, раз нам дали такое задание на лабораторной, и дали такой алгоритм на лекции.
Catstail
Модератор
 Аватар для Catstail
21451 / 10236 / 1667
Регистрация: 12.02.2012
Сообщений: 17,108
08.01.2013, 18:33     Сортировка массива строк методом подсчета #5
Статья из Википедии правильная... Но, обрати внимание, она сплошь - о целых числах (отнюдь не о строках).
graynk
0 / 0 / 0
Регистрация: 08.01.2013
Сообщений: 4
08.01.2013, 18:37  [ТС]     Сортировка массива строк методом подсчета #6
Цитата Сообщение от Catstail Посмотреть сообщение
Статья из Википедии правильная... Но, обрати внимание, она сплошь - о целых числах (отнюдь не о строках).
и кусок с реализацией на с++ тоже правильный? он же алгоритму следует примерно никак.
я и заметил, что она о целых числах. у меня-то задание про строки. не я ж задание придумал, преподаватели. собственно, они и дали ответ, просто не сразу этот алгоритм в лекциях нашел. может они живут в своей собственной вселенной, придумывают новые алгоритмы, и дают им имена уже существующих, черт их знает.
Catstail
Модератор
 Аватар для Catstail
21451 / 10236 / 1667
Регистрация: 12.02.2012
Сообщений: 17,108
08.01.2013, 18:41     Сортировка массива строк методом подсчета #7
Да, этот алгоритм будет работать... Но вся прелесть сортировки подсчетом состоит в том, что его производительность растет как N. А алгоритм, который вам дали на лекции, похоже, будет иметь производительность ~ N2.

Добавлено через 1 минуту
Цитата Сообщение от graynk Посмотреть сообщение
и кусок с реализацией на с++ тоже правильный?
- да, но неполный (мне кажется).
graynk
0 / 0 / 0
Регистрация: 08.01.2013
Сообщений: 4
08.01.2013, 18:43  [ТС]     Сортировка массива строк методом подсчета #8
Цитата Сообщение от Catstail Посмотреть сообщение
Да, этот алгоритм будет работать... Но вся прелесть сортировки подсчетом состоит в том, что его производительность растет как N. А алгоритм, который вам дали на лекции, похоже, будет иметь производительность ~ N2.
да, в лекциях написано, что N2 будет)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.01.2013, 18:47     Сортировка массива строк методом подсчета
Еще ссылки по теме:

Сортировка массива методом пузырька C++
Сортировка массива пузырьковым методом и методом вставки C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Catstail
Модератор
 Аватар для Catstail
21451 / 10236 / 1667
Регистрация: 12.02.2012
Сообщений: 17,108
08.01.2013, 18:47     Сортировка массива строк методом подсчета #9
Цитата Сообщение от graynk Посмотреть сообщение
да, в лекциях написано, что N2 будет)
- вот и я о том же... Единственное его преимущество в том, что пока формируются ключи, строки "лежат на своих местах", а не перемещаются (как это было бы при сортировке вставками, выбором, обменом и т.д.)
Yandex
Объявления
08.01.2013, 18:47     Сортировка массива строк методом подсчета
Ответ Создать тему
Опции темы

Текущее время: 06:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru