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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
graynk
0 / 0 / 0
Регистрация: 08.01.2013
Сообщений: 4
#1

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

08.01.2013, 18:08. Просмотров 2170. Ответов 8
Метки нет (Все метки)

Здравствуйте. Вкратце, задача такова - написать программу, упорядочивающую массив строк в алфавитном порядке методом сортировки подсчетом. Использовать указатели на строки.
Обычный алгоритм сортировки подсчетом, если верить вики, такой:
Код
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];
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2013, 18:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка массива строк методом подсчета (C++):

Сортировка массива методом подсчета - C++
Здравствуйте, уважаемые форумчане. Недавно написал код для сортировки массива подсчетом. Программа работает, но не проходит тесты, кроме...

Сортировка массива в убывающем порядке по количеству появлений методом подсчета - C++
Добрый день!Мне нужно отсортировать одномерный массив в убывающем порядке по количеству появлений методом подсчета! Пример:3 1 1 3 1 7 9...

Сортировка массива строк методом пузырька - C++
заполнить заранее проинициализированный массив строк фамилиями своей групп. отсортировать во второй массив все фамилии, стоящие в журнале...

Сортировка методом подсчета - C++
Добрый вечер,ребята очень нужен алгоритм сортировки подсчетом.Спасибо заранее.Есть вот это Это простейший вариант алгоритма. Создать...

Сортировка массива пузырьковым методом и методом вставки - C++
нужно написать программу которая будет делать сортировку этими способами в массиве 3x10, две кнопки, таблица (3х10), собственно...

Сортировка строк матрицы методом Шелла - C++
Дана матрица размерности n*n отсортировать строки матрицы методом шелла по возрастанию=)

8
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
08.01.2013, 18:11 #2
Цитата Сообщение от graynk Посмотреть сообщение
Обычный алгоритм сортировки подсчетом, если верить вики, такой:
Ссылку на статью в студию.
0
Catstail
Модератор
22640 / 11009 / 1785
Регистрация: 12.02.2012
Сообщений: 18,173
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/%D0%A1%...82%D0%BE%D0%BC

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

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

Сортировка массива методом выбора - C++
Добрый вечер!!! В данном коде идет сортировка массива методом шелла Нужно переделать ее как сортировку методом выбора... Помогите...

Сортировка массива методом Шелла - C++
добрый день нужна помощь, есть код #include &lt;iostream&gt; using namespace std; int main() { // razmer massiva, //...

Сортировка массива методом включения - C++
Задание : сортировки массива методом включения. Размер массива 7. Направление сортировки по возрастанию. Массив вроде бы написал а...

Сортировка массива методом пузырька - C++
Нужно отсортировать массив &quot;B&quot; методом пузырька по возрастанию, но он некорректно работает, например, если ввести массив &quot;С&quot; 3x3: 4 4 4 ...


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

Или воспользуйтесь поиском по форуму:
9
Yandex
Объявления
08.01.2013, 18:47
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru