Приветствую всех. Помогите разобраться с сортировкой. Пытаюсь приспособить алгоритм quicksort для сортировки двумерного строкового массива. Работает быстро, но неточно. С первого раза не все элементы стоят как надо, приходится досортировывать. Иногда 7-8 раз прогоняю массив через процедуру, прежде чем всё утрясётся. Никак не пойму где грабли, уже устал наступать на них. Может кому интересно, попробуйте. Инструмент в аттаче (3 процедуры- сортировка, сравнение, перестановка).

304928242__Sort.asm

Здесь я приводил мою реализацию быстрой сортировки. Правда там отсутствуют коментарии, но зато нет передачи данных через стек. Если процедуре сравнения нужен какой-либо параметр, то добраться до него она может через регистр ebp. Результатом функции сравнения должен быть signed int. Хотя можно переделать чтобы функция сравнения флаги устанавливала. Вообщем вполне сгодится для медитации 8)

Есть у меня пример (сам делал когда-то) QSort'а, но там рекурсивная реализация. Могу дать, если надо..

Black_mirror
Видел этот топик, но не очень помогло.

n0p
А можно глянуть, что там?

двумерного строкового массива

Это как?

volodya
Примерно так:строка состоит из 5 zero-termenated подстрок. Сортировать можно по любой из них.

cresta
Ты не на словах объясни, а покажи пример не отсортированного и отсортированного двумерного строкового массива.

Вероятно, cresta делает BWT? :)

q_q

„двумерного строкового массива“
- это я так понимаю сортировку итемов virtual listview. В аттаче - ехе файл. Запусти и дави на икону с биноклем, далее разобраться можно.
Сейчас переделал процедуру поиска, сортирует правильно, но не быстро :(. Немного быстрее, чем методом простых вставок, т.е. O(n) ориентировочно О((n^2)*0.7) Видимо сбился с алгоритма quicksort.
Процедура сортировки тоже в аттаче.



_1087975206__Sort.zip

captain cobalt
„делает BWT?“
да просто virtual listview не имеет внутреннего метода сортировки, вот я и делаю ему свою :)
А что есть BWT?

cresta
На win98 даже не запускается, а
вообще, глядя на код, такое быстро не может работать только по реализации ;-)

cresta
w2ksp4 - "даже не запускается" (C) Asterix.
Не может зарегистрировать класс окна Float_Class - ERROR_INVALID_PARAMETER (00000057).
:( Зачем давать исполняемую программу, которая в реестре создает свой ключ, без исходного текста?

это я так понимаю сортировку итемов
Это называется сортировка строк.

просто virtual listview не имеет внутреннего метода сортировки
Зачем тогда используешь его?

cresta
Честно говоря я так и не смог понять твой алгоритм, уж слишком много там условий.

Вот quicksort взятый из книги "Алгоритмы построение и анализ"(авторы: Т.Кормен,Ч.Лейзерсон,Р.Ривест):

Сортируется участок массива A[p..r]

quicksort(A,p,r)
{
  if (p<r)
  {
    q=partition(A,p,r)
    quicksort(A,p,q)
    quicksort(A,q+1,p)
  }
}

Разбивает A[p..r] на два массива A[p..q]<=x и A[q+1..r]>=x

partition(A,p,r)
{
  x=A[p]
  i=p-1
  j=r+1
  while(1)
  {
    do{
      j--
    }while(A[j]>x)
    do{
      i++
    }while(A[i]<x)
    if(i<j)
      swap(A[i],A[j])
    else
      return j
  }
}

Для реализации quicksort'а я взял именно этот алгоритм, только заменил индексы на указатели, внедрил функцию partition внутрь quicksort'а, преобразовал ее(функции partition) внешний цикл, а также остаточную рекурсию quicksort'а.

q_q
„:( Зачем давать исполняемую программу, которая в реестре создает свой ключ, без исходного текста?“
в ключе ничего криминального нет, пардон, не предупредил
„Зачем тогда используешь его?“
мне показалось, что с ним поиск быстрее, не надо заполнять LV в процессе поиска, можно только на LVN_GETDISPINFO выдавать маленькие куски информации, не тратя время на передачу всего списка.
Asterix
Про 98 не могу ничего сказать, но на XP и w2k - проверял, в 98 не поддерживается только SetLayeredWindowAttributes, но она проверяется через LoadLibrary>GetProcAddress.

Black_mirror
„Честно говоря я так и не смог понять твой алгоритм“

Я к сожалению, в Си мало понимаю :( Вот это что может означать : while(1) ? Если в ассемблерном понятии это можно пропустить, то я действовал по аналогичному алгоритму. Просто для ускорения работы все разбиения, проверки, сравнения и пересылки вписал в одну процедуру, оттого она и кажется не очень понятной. И ещё: здесь, по моему ошибка:
x=A[p]
думаю, что должно быть так:
q=(p+r)\2
x=A[q]
и вот здесь
quicksort(A,q+1,p) должно быть quicksort(A,q+1,r)

P.S. Предвижу вопрос: если в Си не понимаю ничего, то что я здесь делаю. Заранее ответ: Это моё хобби, не более того :)

cresta
Все что в фигурных скобочках это составной оператор, а while(1) это бесконечный цикл. Здесь не совсем Си, так как я не расставил ;. А вообще в книге авторы используют какой-то свой псевдоязык чем-то похожий на паскаль, только без begin/end, их они заменяют отступами.
do{}while() это аналог repeat/until из паскаля, только в паскале в конце пишется условие окончания цикла, а в Си - условие продолжения. j-- это j=j-1. Ну а выбирать x по разному, можно взять первый или последний элемент, средний, элемент со случайным индексом, или выбрать средний из первого, последнего и элемента посередине, и еще кучей способов.

„quicksort(A,q+1,p) должно быть quicksort(A,q+1,r)“
А здесь у меня действительно ошибка.