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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Найти сумму элементов четных строк и произведение элементов нечетных строк массива http://www.cyberforum.ru/cpp-beginners/thread755838.html
дан двумерный массив динамический массив. Найти сумму элементов четных строк и произведение элементов нечетных строк. помогите пожалyйста!!!!!!!!!!!!!!!!!!
C++ Работа с двоичными файлами Всем привет.. пытаюсь понять один вопрос. допустим есть текстовый файл с таким содержанием 12345 67890 я хочу эту информацию переписать в двоичный файл для этого написала нехитрую программу, но она работает как то странно.. по идее она должна записать данные в двоичном виде, и она просто переписывает значения из текстового файла в таком же, текстовом, виде... т.е. на выходе файл такой... http://www.cyberforum.ru/cpp-beginners/thread755832.html
C++ Нужна простая програмка после нажатия на которую будет автоматически скажем в течении 2 мин нажимать ENTER
Нужна простая програмка после нажатия на которую будет автоматически скажем в течении 2 мин нажимать ENTER
Имеется таблица T, состоящая из U структур C++
Имеется таблица T, состоящая из U структур (U определить как константу). Считая, что в таблице структуры имеют разные ключи, описать и использовать в программе процедуру, упорядочивающую структуры таблицы по возрастанию их ключей. Срочно нужно написать прогу. Буду благодарен
C++ Из троичной системы счисления в 9-ю,не переводя все число в 10-ю http://www.cyberforum.ru/cpp-beginners/thread755815.html
Помогите пожалуйста написать программу в С++, которая переводит число из 3й системы счисления в 9ю,не переводя все число в 10ю. Если можно попроще,заранее спасибо
C++ Строки. Перевернуть первое слово. перевернуть первое слово в строке по С++. помогите, за 30 минут нужно сделать !!!(( подробнее

Показать сообщение отдельно
graynk
0 / 0 / 0
Регистрация: 08.01.2013
Сообщений: 4
08.01.2013, 18:08     Сортировка массива строк методом подсчета
Здравствуйте. Вкратце, задача такова - написать программу, упорядочивающую массив строк в алфавитном порядке методом сортировки подсчетом. Использовать указатели на строки.
Обычный алгоритм сортировки подсчетом, если верить вики, такой:
Код
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];
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 13:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru