Софтуерно Инженерство
Loading...
+ Нов въпрос
v.krastev avatar v.krastev 54 Точки

Оригинална имплементация на QuickSort

Колеги, здравейте!

Ръчкам въпросния алгоритъм и на страничката в Wikipedia е изписан псевдокод на уж оригиналната имплементация на гн. Hoare (не знам на кирилица как да го изпиша). Това е въпросното нещо:

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

За да проверя до колко съм разбрал алгоритъма и къде най-вероятно греша - Защо i започва от lo - 1 ?? още при първия do while нещата умират (поне доколкото аз разбирам). Да вземем например 18, -6, 20, 3, 1, 20, 16 - числата са малко и в реалната имплементация съм сложил да се върти insertionSort-а, но да речем че ще използваме само рекурсиите на quicksort-а за примера.

Така - lo в началото е равно на 0, следователно i == -1. В първия do while, i става i + 1 което е 0, тоест става равно на lo, и при проверката A[ i ] < pivot (където pivot == lo) цикълът спира и левият индекс (въпросното i) остава на 18 и долу swap-а разменя 18 и 16, а не първото 20 и 16 както би трябвало да е. Защо си мисля, че i трябва да започва от lo(pivot), а не от 1 по-надолу. при i == lo, първото сравнение няма да е дали 18 < 18, а -6 <18 и тн  и в крайна сметка i ще стигне до 20. 

Аз ли бъркам някъде, или това i = lo - 1 е грешно?

Благодаря предварително за търпението и отговорите!

Поздрави!

Тагове:
v.krastev avatar v.krastev 54 Точки

Въпреки че още нямам отговор, ще доразширя въпроса си. Според мен са интересни неща и не чак толкова елементарни за да не заслужават малко дискусия.

1 - това ми е имплементацията на QuickSort3. Прегледах много обяснения и разисквания както и разлини имплементации на алгоритъма и в крайна сметка стигнах до това. Вижда се, че използвам basic shuffle алгоритъм (както на курса), после, при колекция под 6 елемента използвам insertion sort.

2 - осезаемо е, че някъде бъркам много сериозно - при просто сравнение с merge sort-a получавам следните резултати (всички тестове са с колекции от по 1 000 000 елемента, времето е милисекундите според C#-ския stopWatch):

Reversed Random Ordered Same element
merge - 35 merge - 503 merge - 36 merge - 272
quick3 - 617   quick3 - 577 quick3 - 95

ето и сравнение между обикновен QuickSort (имплементиран без 3-way-partitioning) и merge:

Reversed Random Ordered Same element
merge - 37 merge - 519 merge - 31 merge - 277
quick - 523 quick - 519 quick - 493 quick - 327

От тук няколко неща - 3-way-partitioning-а определено променя нещата за колекции с един и същ елемент (или с много малко на брой разлини елементи). Но нататък - merge-а просто премазва (!!)моята(!!) имплементация на QuickSort-а, независимо дали е Quick3 или без 3-way-partitioning-а. вижда се 15-ъти по-бавното справяне на QuickSort-а. И, не на последно място, без 3-way-partitioning-а, при колекции от по 1 000 000 рандом елемента, QuickSort-а дава същия резултат (с разлика от по няколко милисекунди +-) като merge-a, но Quick3 изобщо не връща сортиран алгоритъм (преди да принтирам изминалото време, проверявам дали масива реално е бил сортиран). да не говорим, че и при подредения или обърнатия масив, Quick3 се справя по-зле и от QuickSort. Защо!?!?! :D :D 

Простете за романа!

Поздрави!

ъпдейт: справих се с проблема Random да не връща нищо, погледнах пак кода и осъзнах че грешката е накрая когато правя средния partition (не знам той какво общо е имал и защо заради това алгоритъма не сортираше). остава си проблема защо имплементацията ми на Quick3 е толкова бавна? изведох merge-sort в отделен клас и това дори го направи още по-бърз, а QuickSort-а (със и без 3-way-partitioning) си изостава.

Reversed Random Ordered Same element
merge - 20 merge - 497 merge - 19 merge - 260
quick3 - 618 quick3 - 569 quick3 - 574 quick3 - 96

за обърнати и подредени слиза до 20..... разликата е огромна и сравнено само с 3-пъти по-бързото представяне на quick3 при еднакви елементи, merge-sort (поне при тези ми имплементации) си е безспорен победител... което противоречи на всичко изчетено в нета и на думите на лектора Симеон Шейтанов, че за трилион (?) елемента, quick се справя за 12 минути, а merge за 18. Идеи и предложения от някого?

0
28/08/2017 10:26:17