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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 5.00
pelele
7 / 2 / 1
Регистрация: 08.10.2009
Сообщений: 45
16.06.2011, 22:59     Распределяющая сортировка #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/C++ FAQ :: Быстрая сортировка (сортировка Хоара) C++
Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива C++
2 сортировки: пирамидальная сортировка и сортировка слиянием C++
Быстрая сортировка (сортировка Хоара) для связных списков C++
C++ Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
C++ Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xAtom
 Аватар для xAtom
910 / 735 / 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     Распределяющая сортировка
Ответ Создать тему
Опции темы

Текущее время: 08:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru