Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2017-12-12 | 215 |
5.00
из
|
Заказать работу |
|
|
В качестве интересного примера рассмотрим компьютерное представление целых беззнаковых чисел. На хранение каждого из базовых типов выделяется строго определенное количество байт. Как правило, распределение такое:
unsigned char - 1 байт,unsigned short int - 2 байта, unsigned long int - 4 байта.При этом большинство процессоров использует обратный порядок записи: от младшего байта к старшему. Так число типа short int i = 669110 = 0x1A23 непосредственно в памяти хранится так:
Если это число имеет тип long int, то под него выделяется 4 байта: long int i = 669110 = 0x00001A23.
В конце расположены ведущие нули. Таким образом, необходимо провести сортировку от начала числа к концу. Каждый байт может принимать в общем случае 256 значений: m=256.
// Создать счетчики.// data-сортируемый массив, counters-массив для счетчиков, N-число элементов в datatemplate<class T>void createCounters(T *data, long *counters, long N) { // i-й массив count расположен, начиная с адреса counters+256*i memset(counters, 0, 256*sizeof(T)*sizeof(long)); uchar *bp = (uchar*)data; uchar *dataEnd = (uchar*)(data + N); ushort i; while (bp!= dataEnd) { // увеличиваем количество байт со значением *bp // i - текущий массив счетчиков for (i=0; i<sizeof(T);i++) counters[256*i + *bp++]++; }} // Функция radixPass принимает в качестве параметров// номер байта Offset,// число элементов N, // исходный массив source, // массив dest, куда будут записываться числа, отсортированные по байту Offset// массив счетчиков count, соответствующий текущему проходу. template<class T>void radixPass (short Offset, long N, T *source, T *dest, long *count) { // временные переменные T *sp; long s, c, i, *cp; uchar *bp; // шаг 3 s = 0; // временная переменная, хранящая сумму на данный момент cp = count; for (i = 256; i > 0; --i, ++cp) { c = *cp; *cp = s; s += c; } // шаг 4 bp = (uchar *)source + Offset; sp = source; for (i = N; i > 0; --i, bp += sizeof(T), ++sp) { cp = count + *bp; dest[*cp] = *sp; ++(*cp); }}Процедура сортировки заключается в осуществлении sizeof(T) проходов по направлению от младшего байта к старшему.
|
Обратим внимание, что если число проходов нечетное(например, T=unsigned char), то из-за перестановки swap() реально уничтожается исходный массив, а указатель in приобретает адрес out. Об этом следует помнить, используя указатели на сортируемый массив во внешней программе.
Такая организация процедуры также является прототипом для сортировки строк: достаточно сделать проходы radixPass от последней буквы к первой.
Строка, помеченная (***) представляет собой небольшую оптимизацию. Бывает так, что сортируемые типы используются не полностью. Например, в переменных ulong хранятся числа до 65536(=2562) или до 16777216(=2563). При этом остается еще один или два старших разряда, которые всегда равны нулю. В переменной count[0] хранится общее количество нулевых байтов на текущей сортируемой позиции, и если оно равно общему количеству чисел, то сортировка по этому разряду не нужна. Так radixSort сама адаптируется к реальному промежутку, в котором лежат числа.
|
|
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!