Поразрядная сортировка подразумевает сортировку "по разрядам". Для имен файлов - это буквы. Начиная с последней. Т.к. у Вас названия файлов имеют разную длинну, то с последней начинать не стоит, т.к. может быть всего один файл с таким длинным именем. А надо хотя бы два. Вообщем, в статье написанно достатоно подробно и понятно.



Не вижу препятствий. Обьясните, плиз, чем не годится.

Слишком много обращений к данным. Несмотря на то, что не производятся сравнения самих данных, их значения очень интесивно читаются.

Точно, я уже даже сам догадался, что сравнивать надо не последовательно, а деля массив пополам...
Спасибо, возьму этот вариант за основу!
Будете в Тольятти - ящик с меня

Пожалуйста Мне кажется, это будет оптимальный вариант - 256 байт на индексы плюс буфера на текущее имя файла и буфер, в который будет читаться обрабатываемое имя файла.

Понятно дело, что ради одной буквы из имени в ФАТ лезть не стоит. Можно буферизировать по 5 букв из имени каждого файла. Или если буфер заранее задан, то в зависимоти от количества файлов. Тогда на всю сортировку будет не так и много обращений.

5 букв да на 256 файлов - не дофига ли ОЗУ надо И кстати, если все файлы с длиннючими именами, то очень скоро количество обращений превысит 1800 для моего алгоритма.

Согласен. Было бы неплохо этот алгоритм "развернуть". Т.е. начинать с первых букв, тогда можно не идти до конца имен, если перестановки закончились. Но это уже близко к бинарному дереву.

Да зачем? На таком малом количестве (до тысячи файлов) он точно будет хуже описанного мною бинарного поиска с последующей вставкой (обратите внимание на графики по Вашей ссылке, где поразрядная сортировка начинает обгонять quicksort, да еще и учтите, что STL - далеко не образец оптимизации по скорости). Либо по ОЗУ, либо по количеству считываний. Если хотите, реализуйте предложенный Вами алгоритм и устроим фаллосометрию. Для моего случая не более 1800 обращений к функции получения имени файла по индексу и 256 байт ОЗУ (2 буфера для строк не считаем, Вам они тоже понадобятся).

Пополам, не самый эффективный вариант - делить надо http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%...%BD%D0%B8%D1%8F

Для максимум-то восьми сравнений "отэтот гемморой"? Да ну нафиг

Тем более, получится больше считываний. Тут как раз BS рулит по полной.

Трудностей никаких и нет, а массивы не только размером 256 записей бывают, а индексный массив не только в RAM лежать может, но и на той-же файловой системе - лишние обращения никчему.

Я предпочитаю иметь детерминированное количество обращений (для BS - log2(n)), а для золотого сечения - еще зависит от входного набора данных (т.е. от поведения целевой функции). Часто это хуже, чем мифический выигрыш. Кстати, асимптотически и BS, и золотое сечение - O(log(n)).

Но это мы уже плавно переходим на обсуждение глобальных теорий... Ну его в сад

Кстати, по большому счету волшебные буквы "ARM" к обсуждаемой теме не имеют никакого отношения, и тему, по науке, надо бы перенести в раздел для обсуждения алгоритмов.

Нее. Спасибо. Думаю, Ваш алгоритм действительно "длинее"... В смысле лучше.

З.Ы. если разберусь с глюками своей поделки на str912 тоже буду делать плеер. Тогда, может, и попробую сравнить алгоритмы.

В принципе, вместо имени файла можно юзать ID3 тэги. Тут только придётся, кроме чтения имени из FAT, ещё и первый сектор файла читать...

Это даже более красиво с точки зрения интерфейса. Просто надо заменить список индексов в каталоге на список первых секторов. Кстати, заметно быстрее будет сортировка (все-таки чтение имени из каталога - весьма небыстрое занятие), но надо хачить работу с ФС - сделать функцию получения номера первого сектора файла.