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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 5.00
pelele
7 / 2 / 1
Регистрация: 08.10.2009
Сообщений: 45
#1

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

16.06.2011, 22:59. Просмотров 1947. Ответов 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';
 }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.06.2011, 22:59     Распределяющая сортировка
Посмотрите здесь:

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

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

Блок схема.Сортировка «Пузырьком», Сортировка методом «Последовательных перестановок», Сортировка «Вставками» - Pascal
Помогите, нужны блок схемы Сортировка «Вставками» Program Vstavka; uses dos; Type mass=array of integer; Var i,b,n,j,a:...

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

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

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

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

Быстрая сортировка, ситуация, при которой сортировка работает не корректно - Turbo Pascal
Procedure sort(m, l: Integer); Var i, j, x, w: Integer; Begin i := m; j := l; x := ar; Repeat While...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include &lt;iostream&gt; ...

Быстрая сортировка (сортировка Хоара) для связных списков - C++
есть у кого готовый алгоритм? или подскажите как реализовать

Быстрая сортировка и Обменная сортировка - реализация API функции - C (СИ)
Всех приветствую! Делаю курсовой проект и появилась одна проблем-ка.... У меня есть готовые две программы(быстрая сортировка и Обменная...

Сортировка пирамидой: Вычислить сколько шагов сделала сортировка - PascalABC.NET
Есть код сортировки пирамидой, как теперь вычислить сколько шагов сделала сортировка прежде чем программа закончила работу, желательно с...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xAtom
914 / 739 / 60
Регистрация: 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.
Yandex
Объявления
17.06.2011, 08:20     Распределяющая сортировка
Ответ Создать тему
Опции темы

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