Алгоритм сортировки
sort -n $file
Сортировка вставками неплохо подходит для этой задачи.
к моему сожалению, 1) файл- это XML, 2)это винда...
Сортировка вставками неплохо подходит для этой задачи.Зависит от того как оно в памяти храниться. Иначе на перемещения много операций надо.
2)cygwin
Обычный массив, и прямая работа с памятью запрещена.
1) файл- это XML
Строки явлются положительными числами довольно широкого диапазона.
2)это винда...Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.
C:\Documents and Settings\boris>sort --help
Usage: sort [OPTION]... [FILE]...
Write sorted concatenation of all FILE(s) to standard output.
Это как?
Ну это не язык программирования, это кривая среда для визуального программирования специфической направленности, так что перемещать прямо куски памяти нельзя...
кривая среда для визуального программированияLV?
Ну я просто не хотел усложнять сразу задание, так как на выбор алгоритма это не влияет.
ENVOX... 
EVNOOX
А как ты хочешь реализовывать этот алгоритм? посредством возможностей этого визуального "программизма"?
Да. Там есть в принципе и циклы, и массивы, и переменные.
А у этой "кривой среды для визуального программирования специфической направленности" есть либа для работы с XML?
Угу, есть.
Ну так открой его как XML и отсортируй!
Данных вроде немного
Данных вроде немного
Там слишком тупая библиотека. Умеет только открывать документ, доставать оттуда ноды по порядку , дочерние-родительские ноды или искать по XSL-паттерну. Методов сортировки там нет
То есть ты как раз для нее и хочешь сортировку написать?
Не удивлюсь, если окажется, что можно написать сортирующий XSLT
искать по XSL-паттернуЭто штука вроде бы многое может.
Не удивлюсь, если окажется, что можно написать сортирующий XSLT
Нет, сортировка нужна для другой задачи. Мне на выходе нужен отсортированный массив из ~10000 элементов, чотбы по нему вести предиктивный поиск.
Если неизвестно, сколько будут занимать строки и сколько их будет, наиши Sorter, который имеет методы open (portions_name, portion_size push(element close. Этот классик сортирует часть данных в памяти и сбрасывает порцию на диск, когда размер становится больше максимального, потом закрывает все отсортированные файлики. Далее порции сливаются в один поток с помощью heap-итератора, который читает все файлики с помощью кучи.
десять тысяч данных - это мало для современных процов (т.к. даже алгоритмы O(n^2) летают поэтому можно брать любой метод.
раз среда какая-то убогая, то данные считать в массив, а потом сортировать.
для сортировки или портировать Quick Sort или закодить ту же сортировку прямого выбора
раз среда какая-то убогая, то данные считать в массив, а потом сортировать.
для сортировки или портировать Quick Sort или закодить ту же сортировку прямого выбора
Спасибо! Наверное попробую портировать Quick Sort.
Можешь взять бинарное дерево за основу.
Вставляй в него, потом пройдешься слева-направо по всем вершинам и будет у тебя сортированный список.
Если исходные данные достаточно рандомные, глубина дерева будет O(logN).
Если исходные данные по большей части отсортированы, возможно придется АВЛ-балансировку дерева сделать.
А проще всего считать весь массив в память и сортирнуть его QuickSort-ом.
Вставляй в него, потом пройдешься слева-направо по всем вершинам и будет у тебя сортированный список.
Если исходные данные достаточно рандомные, глубина дерева будет O(logN).
Если исходные данные по большей части отсортированы, возможно придется АВЛ-балансировку дерева сделать.
А проще всего считать весь массив в память и сортирнуть его QuickSort-ом.
XSL-паттерн — это что-то новое. Может XPath всё-таки?
Ну в целом да:
XSL pattern. The XSL Pattern get node option is used to specify a standard pattern used in - for example - XSL Transformations, which is a language used for transforming XML documents into other XML documents. The pattern specifies a set of conditions on a node, which must be satisfied in order to return the result node. The XSL Pattern is a subset of expression language XPath, XML Path Language.
merge sort наверное проще получится.
Квиксорт просто очень тяжело написать правильно. "Очень тяжело" не в смысле что полчасика подумать нужно, а в смысле что у Кнута в первых изданиях он был с ошибкой, например. Настолько "очень тяжело".
Квиксорт просто очень тяжело написать правильно. "Очень тяжело" не в смысле что полчасика подумать нужно, а в смысле что у Кнута в первых изданиях он был с ошибкой, например. Настолько "очень тяжело".
Очень тяжелодык его надо писать на "правильном" языке
C:\Documents and Settings\boris>sort --helpФотошоп!
Usage: sort [OPTION]... [FILE]...
В винде было бы sort/?
Оставить комментарий
Fragaria
Народ, подскажите, какой именно алгоритм сортировки оптимальнее всего использовать в моём случае?У меня есть некоторый файл, из которого я читаю строки. Строки явлются положительными числами довольно широкого диапазона. Часть из них - 4-значные, часть - 9-значные, часть - ещё какие-то. Таких строк будет примерно 5-10 тысяч. Нужно их упорядочить по возрастанию, лучше всего прямо в процессе считывания из файла, но если есть более эффективный алгоритм, работающий с уже заполненным несортированным массивом - то можно и сначала считать всё в несортированный массив, а потом уже отсортировать.