C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream.h>
#include <string.h>
#include <conio.h>
 
const int bitsword = 32, bitsbyte = 8 ;
const int bytesword = bitsword/bitsbyte;
const int R = 2 << bitsbyte;
const int maxN = 100;
 
int digit(char *A, int B) { return A[B]; }
 
void radixLSD(char **a, int l, int r, int maxN)
{
    char **aux = new char *[maxN];
    for (int d=bytesword-1; d>=0; d--)
    {
        int i, j, count[R+1];
        for (j=0; j<R; j++) count[j] = 0;
        for (i=l; i<=r; i++) count[digit(a[i], d) + 1]++;
        for (j=1; j<R; j++) count[j] += count[j-1];
        for (i=l; i<=r; i++) aux[count[digit(a[i], d)]++] = a[i];
        for (i=l; i<=r; i++) a[i] = aux[i-l];
    }
    delete[] aux;
}
 
int main()
{
    int i, n;
    cout<<"Kolichestvo strok: "; cin>>n;
    char **strings = new char *[n * sizeof(char *)], buffer[30];
    
    for(i=0; i<n; i++)
    {
        cout<<"Vvedite "<<i+1<<" stroku: "; cin>>buffer;
        strings[i] = new char [strlen(buffer)+1];
        strcpy(strings[i], buffer);
    }
    radixLSD (strings, 0, n-1, n);
    
    for (i=0; i<n; i++) puts(strings[i]);
    getch();
    return 0;
}

maxon887 · 10.09.2013, 13:05

Так ты хоть описал бы, что эта штука должна делать.

@Cynacyn · 10.09.2013, 13:13

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

Так ты хоть описал бы, что эта штука должна делать.

Поразрядная сортировка

@Bellfator · 10.09.2013, 15:51 **[ТС]**

Пусть имеется N строк различный длины алфавита мощности M с заданным на них лексикографическим порядком [3,4,9,12]. Необходимо отсортировать их в соотвествии с этим порядком, то есть отсортировать, используя алгоритм лексикографической сортировки. Данная сортировка относится к классу распределяющих сортировк и имеет линейную трудоемкость относительно числа сортируемых строк при условии, что M<<N. Вот задача, нужно приписать комментарии к строкам моей программы.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

maxon887 12 / 12 / 7 Регистрация: 05.06.2012 Сообщений: 280
	10.09.2013, 13:05
	Так ты хоть описал бы, что эта штука должна делать. 0

@Bellfator 0 / 0 / 0 Регистрация: 15.04.2013 Сообщений: 22
	10.09.2013, 15:51 [ТС]
	Пусть имеется N строк различный длины алфавита мощности M с заданным на них лексикографическим порядком [3,4,9,12]. Необходимо отсортировать их в соотвествии с этим порядком, то есть отсортировать, используя алгоритм лексикографической сортировки. Данная сортировка относится к классу распределяющих сортировк и имеет линейную трудоемкость относительно числа сортируемых строк при условии, что M<<N. Вот задача, нужно приписать комментарии к строкам моей программы. 0

Комментарии