Bead sort алгоритм сортировки

@SJEF · Регистрация: 03.07.2010

Студворк — интернет-сервис помощи студентам

Bead sort (алгоритм бусинной\бисерной сортировки). Довольно интересный алгоритм нашел о нем некоторую информацию, но к сожалению вся она на английском.
Знает ли кто-то книги, ссылки и т.д. об этом алгоритме на русском языке, чтобы уже полностью изучить этот алгоритм.
Bead Sort на википедии

@i8085 · 08.07.2010, 06:57

SJEF, напишите подпрограммку преобразования одного байта в последовательность единиц в 256 - разрядном слове, количество которых равно значению байта, расположенных подряд, начиная с левой границы, остаток 256-разрядного слова заполните нулями. Именно с таким представлением числа работает этот алгоритм. Посмотрите размер этой подпрограммки, прикиньте время её выполнения. Не забудьте, что после сортировки массив надо преобразовать обратно в байты.
А бывают ещё 16-ти, 32-х, 64-х разрядные числа, числа с плавающей точкой, строки и т.д., и т.п... Их тоже иногда требуется сортировать.

@Puporev · 08.07.2010, 10:04

Непрактичные алгоритмы сортировки

Bogosort — O(n·n!) в среднем. Произвольно перемешать массив, проверить порядок.
Сортировка перестановкой — O(n·n!) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.
Глупая сортировка (Stupid sort) — O(n3); рекурсивная версия требует дополнительно O(n2) памяти
Bead Sort — O(n) or O(√n), требуется специализированное аппаратное обеспечение
Блинная сортировка (Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение

Добавлено через 9 минут
Какая-то нерусская сортировка, здесь тоже на аглицком...
http://sawoy.mylivepage.com/file/526/5073

@SJEF · 12.07.2010, 20:50 **[ТС]**

Сообщение от i8085

SJEF, напишите подпрограммку преобразования одного байта в последовательность единиц в 256 - разрядном слове, количество которых равно значению байта, расположенных подряд, начиная с левой границы, остаток 256-разрядного слова заполните нулями. Именно с таким представлением числа работает этот алгоритм. Посмотрите размер этой подпрограммки, прикиньте время её выполнения. Не забудьте, что после сортировки массив надо преобразовать обратно в байты.
А бывают ещё 16-ти, 32-х, 64-х разрядные числа, числа с плавающей точкой, строки и т.д., и т.п... Их тоже иногда требуется сортировать.

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

@i8085 · 14.07.2010, 21:06

Сообщение от SJEF

...углубиться в него все равно было бы интересно.

Пожалуйста, углубляйтесь. Никто не может вам этого запретить. Недостаток знания английского можно компенсировать "он-лайн" переводчиком.

Моё личное мнение об "углублении" в этот алгоритм - это столь же полезно, как и изучить все приёмы рассчётов на компьютере "Abacus".

@i8085 3069 / 2245 / 517 Регистрация: 11.09.2009 Сообщений: 8,285
	08.07.2010, 06:57	2
	SJEF, напишите подпрограммку преобразования одного байта в последовательность единиц в 256 - разрядном слове, количество которых равно значению байта, расположенных подряд, начиная с левой границы, остаток 256-разрядного слова заполните нулями. Именно с таким представлением числа работает этот алгоритм. Посмотрите размер этой подпрограммки, прикиньте время её выполнения. Не забудьте, что после сортировки массив надо преобразовать обратно в байты. А бывают ещё 16-ти, 32-х, 64-х разрядные числа, числа с плавающей точкой, строки и т.д., и т.п... Их тоже иногда требуется сортировать. 0

@Puporev Почетный модератор 64291 / 47589 / 32740 Регистрация: 18.05.2008 Сообщений: 115,181
	08.07.2010, 10:04	3
	Непрактичные алгоритмы сортировки Bogosort — O(n·n!) в среднем. Произвольно перемешать массив, проверить порядок. Сортировка перестановкой — O(n·n!) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива. Глупая сортировка (Stupid sort) — O(n3); рекурсивная версия требует дополнительно O(n2) памяти Bead Sort — O(n) or O(√n), требуется специализированное аппаратное обеспечение Блинная сортировка (Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение Добавлено через 9 минут Какая-то нерусская сортировка, здесь тоже на аглицком... http://sawoy.mylivepage.com/file/526/5073 0

@SJEF 18 / 18 / 1 Регистрация: 03.07.2010 Сообщений: 35
	12.07.2010, 20:50 [ТС]	4
	Сообщение от i8085 SJEF, напишите подпрограммку преобразования одного байта в последовательность единиц в 256 - разрядном слове, количество которых равно значению байта, расположенных подряд, начиная с левой границы, остаток 256-разрядного слова заполните нулями. Именно с таким представлением числа работает этот алгоритм. Посмотрите размер этой подпрограммки, прикиньте время её выполнения. Не забудьте, что после сортировки массив надо преобразовать обратно в байты. А бывают ещё 16-ти, 32-х, 64-х разрядные числа, числа с плавающей точкой, строки и т.д., и т.п... Их тоже иногда требуется сортировать. Что данный алгоритм не практичен, понятно и изначально. Но ради увелечения своей компетентности, углубиться в него всеравно было бы интересно. 0

@i8085 3069 / 2245 / 517 Регистрация: 11.09.2009 Сообщений: 8,285
	14.07.2010, 21:06	5
	Сообщение от SJEF ...углубиться в него все равно было бы интересно. Пожалуйста, углубляйтесь. Никто не может вам этого запретить. Недостаток знания английского можно компенсировать "он-лайн" переводчиком. Моё личное мнение об "углублении" в этот алгоритм - это столь же полезно, как и изучить все приёмы рассчётов на компьютере "Abacus". 0

Опции темы