Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 30.05.2018, 18:46   #1
leksus315
Новичок
Джуниор
 
Регистрация: 30.05.2018
Сообщений: 2
По умолчанию может кто дать полно разьяснеение по сартировке как происходит итд зачем digit

Код:
#include <iostream>
#include <fstream>

#include <ctime>
using namespace std;
ofstream out("output.txt");

int digit(int n, int k, int N, int M) {
	return (n >> (N * k) & (M - 1));
}
void _radixsort(int* l, int* r, int N) {//O(k * M)
	int k = (32 + N - 1) / N;
	int M = 1 << N;
	int sz = r - l;
	int* b = new int[sz];
	int* c = new int[M];
	for (int i = 0; i < k; i++) {//O(k * M)
		for (int j = 0; j < M; j++)//O(M)
			c[j] = 0;
		for (int* j = l; j < r; j++)//O(N)
			c[digit(*j, i, N, M)]++;
		for (int j = 1; j < M; j++)//O(M)
			c[j] += c[j - 1];
		for (int* j = r - 1; j >= l; j--)//O(N)
			b[--c[digit(*j, i, N, M)]] = *j;
		int cur = 0;
		for (int* j = l; j < r; j++)//O(N)
			*j = b[cur++];
	}
	delete b;
	delete c;
}
void radixsort(int* l, int* r) {//O(k * M)
	_radixsort(l, r, 8);//O(k * M)
}


int main()
{
	int n;
	cout << "n = ";
	cin >> n;
	int*arr;

	arr = new int[n];
	srand(time(0));
	for (int i = 0; i < n; i++) {
		arr[i] = rand() % n;
	}

	radixsort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		out << arr[i] << endl;
	}
	system("pause");
	return 0;
}
_____
Код программы нужно выделять (форматировать) тегами [CODE] (читать FAQ)
Модератор

Последний раз редактировалось Serge_Bliznykov; 31.05.2018 в 08:25.
leksus315 вне форума Ответить с цитированием
Старый 30.05.2018, 18:55   #2
leksus315
Новичок
Джуниор
 
Регистрация: 30.05.2018
Сообщений: 2
По умолчанию

как бы я не селен в С++ но мне над отчитыватся понему и времени маловато ребят поготите с обьяснением всего этого дела
leksus315 вне форума Ответить с цитированием
Старый 31.05.2018, 08:27   #3
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

это "Поразрядная сортировка" ((англ. radix sort) ) - читать статью на Википедии - ТЫЦ
Serge_Bliznykov вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Может кто объяснить что происходит в этих двух строках. pompiduskus Общие вопросы C/C++ 7 01.11.2015 00:42
Как может быть, что событие DataChange происходит раньше чем DBAfterConnect? EVOSandru6 C++ Builder 2 29.05.2015 19:14
Где и как скачать программу Delphi. Может кто нибудь может помочь мне - без скачивания из интернета. IZOPGRAM Общие вопросы Delphi 4 16.06.2012 18:12
Ко всем кто может хоть как-то подсказать как решить проблему porfonya Microsoft Office Access 1 26.05.2009 17:38
Кто сможет разъяснить как и зачем использовать виртуальные функции в C++? Dunhil Помощь студентам 5 20.12.2007 14:19