7 / 2 / 1
Регистрация: 08.10.2009
Сообщений: 45
1

Распределяющая сортировка

16.06.2011, 22:59. Показов 4763. Ответов 1
Метки нет (Все метки)

Разбираю данную сортировку из вот этого материала http://algolist.manual.ru/sort/faq/q11.php
и что-то я совсем запуталась... или уже крыша едет))

я правильно поняла, что байтовая, цифровая, радиксная или распределяющая сортировка это одно и тоже? просто разные названия?)) Если да, то объясните кто, пожалуйста, как понять, например, вот эту строку из кода сортировки :
C++
1
for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;
не понимаю что вот это: ((source[i])>>(byte*8))&0xff
Сам код сортировки из ссылке выше:
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
#include <iostream.h>
 #include <stdlib.h>
 #include <string.h>
 
 void radix (int byte, long N, long *source, long *dest)
 {
  // *source - входной массив,
  // *dest - отсортированный.
  long count[256];    // вообще говоря, можно обойтись 
  long index[256];    // одним массивом count[]
  
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;
  index[0]=0;
  for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
  for(i=0;i<N;i++) dest[index[((source[i])>>(byte*8))&0xff]++]=source[i];
 }
 
 void radixsort (long *source, long *temp, long N)
 {
  // Сортируем по всем 4 разрядам
  radix (0, N, source, temp);
  radix (1, N, temp, source);
  radix (2, N, source, temp);
  radix (3, N, temp, source);
 }
 
 void make_random (long *data, long N)
 {
  for ( int i=0; i < N; i++ ) data[i]=rand()|(rand()<<16);
 }
 
 long data[10000];
 long temp[10000];
 
 void main (void)
 {
  make_random(data, 10000);
  radixsort (data, temp, 10000);
  for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
 }
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.06.2011, 22:59
Ответы с готовыми решениями:

Распределяющая сортировка
Имею такой код #include &lt; iostream &gt; #include &lt; cstdlib &gt; #include &lt; ctime &gt; #include &lt;...

Стек и распределяющая память. Где лучше хранить? В чем различия?
Например: #include &quot;stdafx.h&quot; using namespace System; // Class representing a height value...

Сортировка выбором, сортировка вставкой, сортировка заменой, сортировка обменом ("пузырьковая" сортировка)
Создать класс, содержащий массив и реализующий алгоритмы сортировки и бинарного поиска в этом...

Блок схема.Сортировка «Пузырьком», Сортировка методом «Последовательных перестановок», Сортировка «Вставками»
Помогите, нужны блок схемы Сортировка «Вставками» Program Vstavka; uses dos; Type mass=array ...

1
933 / 758 / 299
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
17.06.2011, 08:20 2
Байтовая сортировка подразумевается диапазон от 0-255.
((source[i])>>(byte*8))&0xff едёт разделение двойных слов по байтам выражение (byte * 8) определяет на сколько сдвигов использовать от 1 - 4 байт так как двойное слово это 32 - бита то значение byte будет от 1 до 4, то есть сортировка по разряду по тетраде(байту), ok.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.06.2011, 08:20
Помогаю со студенческими работами здесь

Разработать программу сортировки: сортировка перестановкой, сортировка вставкой, быстрая сортировка
Задание: Разработать программу сортировки: - сортировка перестановкой - сортировка...

1)Бинарный поиск 2)Сортировка включением 3)Шейкерная сортировка 4)Сортировка разделением
1)В заданном массиве К(N) найти индексы элементов, которые кратны минимальному значению элемента...

Сортировка массива целых чисел A(n) по убыванию(используя метод обменная сортировка)
Помогите написать программу для сортировки массива целых чисел A(n) по убыванию(используя метод...

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется
Программа создает динамический массив с рандомным заполнением. Дальше выбор сортировок, пузырьком...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru