Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Платформы Windows Mobile и Windows Embedded > Сортировка

Автор: KAPJICOH 7.6.2006, 00:09

Существует массив с отсортированными по имени элементами. При добавлении нового элемента, ищу его место(уже отсортированное) банальным сравнением, что занимает очень много времени. Может кто подскажет как ускорить этот процесс или может использовать вовсе другой алгоритм? Если надо могу приложить код функции поиска позиции. И еще программирую для WindowsMobile.

Автор: skyboy 7.6.2006, 01:02

KAPJICOH, бинарный поиск? У тебя ведь линейный список с данными?

Добавлено @ 01:07
Если не в курсе, вкратце обрисую алгоритм. У тебя есть отсортированный список значений и значений, которое необходимо вставить. Ты можешь определить, где в отсортированном списке находится место твоего элемента: до какого-то элемента или после, правильно? Ведь ты же знаешь, как отсортированы элементы... Так вот, берёшь элемент посередине массива и смотришь: "твой" элемент должен быть до этого "среднего" элемента или после. Если до - берёшь первую половину массива и снова смотришь "средний" в ней элемент. Если после - берёшь вторую половину массива. В худшем случае необходимо выполнить round(log2n) сравнений. Но это - в худшем случае smile

Автор: KAPJICOH 7.6.2006, 13:01

skyboy, в списке существует 2 вида элементов, которые сортируются индивидуально.

Получается для бинарного поиска мне надо создать переменную, хранящую количество элементов одного из вида и вычислять середину так: (all-size)/2+all, где all - размер списка, size - число элементов одного из вида. Правильно?

Автор: skyboy 7.6.2006, 14:19

KAPJICOH, ну, видимо. Откуда ж я могу знать, как эти два вида у тебя расположены - вперемешку или сначала одного типа, а затем уже - второго? Но если мухи - отдельно, котлеты - отдельно, тогда да - надо работать только с той частью, которая тебе нужна.

Автор: Snowy 7.6.2006, 14:24

Модератор: не забываем указывать компилятор

Автор: KAPJICOH 7.6.2006, 15:33

skyboy, спасиба за совет.

Автор: skyboy 7.6.2006, 15:40

KAPJICOH, а ведь Snowy прав smile

Представь ситуацию: ты ищешь, делаешь, исправляешь ошибки, а потом оказывается, что нужный тебе алгоритм реализован в стандартных библиотеках компилятора, как qsort функция в С. Не обидно будет? smile

Автор: KAPJICOH 7.6.2006, 18:25

skyboy, ничего, иногда полезно все самому написать.

Переписал я код для сортровки по этому алгоритму и у меня возникла новая проблема. Элементы у меня хранятся в TreeView, а для получения i элемента надо пройти все предыдущие (другого способа я не знаю). В результате этот процесс стал занимать еще больше времени. Можно ли получить i в TreeView без прохода предыдущих?

Компилятор eVC++ 4.0

Автор: Snowy 7.6.2006, 19:24

Построить список прямых указателей на ветки. И искать по нему.
А вообще зависит от критериев. Почему тебе нужна именно ветка i? Как ты это определяешь?

Автор: KAPJICOH 8.6.2006, 07:04

Snowy, в алгоритме бинарного поиска берется средней элемент списка - он и есть i.