<bgdev />free

Вход Регистрация

Heap Sort vs Quick Sort vs Merge Sort за Array
4

0 1 2
#13215 (ツ) Courvoisier
Създадено на 30.09.2020, видяно: 965 пъти.

Кое според вас е по- удачно за сортиране на арей? Heap Sort или Quick/Merge Sort? Да речем, че ако правя хийпсорт на арей, то ще трябва да създам подареи, които харчат доста време. Отбелязвам, не говоря за линкд лист.

Това са простотии, с които се занимавам в свободното си време, за да не забравям алгоритми.

#13216 (ツ) Courvoisier
Последно редактирано на 30.09.2020 от Courvoisier, видяно: 964 пъти.

Примерна имплементация на хийпсорт:

        public void SortDownward(int[] array)
        {
            HeapifySiftDown(array);

            var index = array.Length - 1;
            while (index > 0)
            {
                Swap(array, index, 0);
                index--;
                SiftDown(array, 0, index);
            }
        }

        private void HeapifySiftDown(int[] array)
        {
            var index = array.Length - 1;

            while (index >= 0)
            {
                SiftDown(array, index, array.Length - 1);
                index--;
            }
        }

        private void SiftDown(int[] array, int start, int end)
        {
            var root = start;

            while (root <= end)
            {
                var child = root;
                var swap = root;

                if (array[swap] < array[child])
                    swap = child;

                // if there is a right child and it is greater
                if (child + 1 <= end && array[swap] < array[child + 1])
                    swap = child + 1;

                if (swap == root)
                    return;

                Swap(array, root, swap);
                root = swap;
            }
        }

        private static void Swap(int[] array, int x, int y)
        {
            var temp = array[x];
            array[x] = array[y];
            array[y] = temp;
        }

примерна имплементация на куиксорт


    /// <summary>
    /// Quicksort is a divide and conquer algorithm. An array is divided into two chunks - lower and
    /// higher sub-arrays. Then both two chunks are quicksorted recursively. Two approaches are
    /// available - Lomuto's and Hoare's approach.
    /// </summary>
    public class Quicksort
    {
        public void SortLomuto(int[] array)
        {
            Lomuto(array, 0, array.Length - 1);
        }

        public void SortHoare(int[] array)
        {
            Hoare(array, 0, array.Length - 1);
        }

        private void Lomuto(int[] array, int low, int high)
        {
            if (low < high)
            {
                var pivot = LomutoPartition(array, low, high);
                Lomuto(array, low, pivot - 1);
                Lomuto(array, pivot + 1, high);
            }
        }

        private void Hoare(int[] array, int low, int high)
        {
            if (low < high)
            {
                var pivot = HoarePartition(array, low, high);

                Hoare(array, low, pivot);
                Hoare(array, pivot + 1, high);
            }
        }

        private int LomutoPartition(int[] array, int low, int high)
        {
            var pivot = array[high];
            var index = low;
            for (var jIndex = low; jIndex < high; jIndex++)
            {
                if (array[jIndex] < pivot)
                {
                    Swap(array, index, jIndex);
                    index += 1;
                }
            }

            Swap(array, index, high);
            return index;
        }

        private int HoarePartition(int[] array, int low, int high)
        {
            var pivot = array[low + (high - low) / 2];
            var tempLow = low - 1;
            var tempHigh = high + 1;

            while (true)
            {
                do
                    tempLow++;
                while (array[tempLow] < pivot);

                do
                    tempHigh--;
                while (array[tempHigh] > pivot);

                if (tempLow >= tempHigh)
                    return tempHigh;

                Swap(array, tempLow, tempHigh);
            }
        }

    }

примерна имплементация на мерджсорт

    public class Mergesort
    {
        public void SortTopDownWithSubArrays(ref int[] array)
        {
            var temp = TopDownSubArraysSort(array);
            array = temp;
        }

        public void SortTopDownWorkingCopy(int[] array)
        {
            var workingCopy = new int[array.Length];
            Array.Copy(array, 0, workingCopy, 0, array.Length);

            TopDownSplitMerge(workingCopy, array, 0, array.Length);
        }

        public void SortBottomUpWorkingCopy(int[] array)
        {
            var workingCopy = new int[array.Length];
            Array.Copy(array, 0, workingCopy, 0, array.Length);

            BottomUpMergeSort(array, workingCopy);
        }

        private int[] TopDownSubArraysSort(int[] array)
        {
            if (array.Length <= 1)
                return array;

            var leftLength = array.Length / 2;
            var left = new int[leftLength];
            var right = new int[array.Length - leftLength];

            Array.Copy(array, 0, left, 0, leftLength);
            Array.Copy(array, leftLength, right, 0, right.Length);

            left = TopDownSubArraysSort(left);
            right = TopDownSubArraysSort(right);

            return MergeSubArrays(left, right);
        }

        private int[] MergeSubArrays(int[] left, int[] right)
        {
            var result = new int[left.Length + right.Length];

            var leftIndex = 0;
            var rightIndex = 0;
            var index = 0;
            while (index < result.Length)
            {
                if (leftIndex < left.Length && rightIndex < right.Length)
                {
                    if (left[leftIndex] <= right[rightIndex])
                    {
                        result[index] = left[leftIndex];
                        index++;
                        leftIndex++;
                    }
                    else
                    {
                        result[index] = right[rightIndex];
                        index++;
                        rightIndex++;
                    }
                }
                else if (leftIndex < left.Length)
                {
                    result[index] = left[leftIndex];
                    index++;
                    leftIndex++;
                }
                else if (rightIndex < right.Length)
                {
                    result[index] = right[rightIndex];
                    index++;
                    rightIndex++;
                }
            }

            return result;
        }

        private void TopDownSplitMerge(int[] source, int[] destination, int start, int end)
        {
            if (end - start < 2) // if sorted
                return;

            var median = (end + start) / 2;

            TopDownSplitMerge(destination, source, start, median);
            TopDownSplitMerge(destination, source, median, end);

            TopDownMerge(source, destination, start, median, end);

        }

        private void TopDownMerge(int[] source, int[] destination, int start, int median, int end)
        {
            var indexStart = start;
            var indexMedian = median;

            for (int index = start; index < end; index++)
            {
                if (indexStart < median && (indexMedian >= end || source[indexStart] <= source[indexMedian]))
                {
                    destination[index] = source[indexStart];
                    indexStart++;
                }
                else
                {
                    destination[index] = source[indexMedian];
                    indexMedian++;
                }
            }
        }

        private void BottomUpMergeSort(int[] source, int[] destination)
        {
            for (int index = 1; index < source.Length; index *= 2)
            {
                for (int jIndex = 0; jIndex < source.Length; jIndex += 2 * index)
                {
                    BottomUpMerge(
                        source, 
                        destination, 
                        jIndex, 
                        Math.Min(index + jIndex, source.Length), 
                        Math.Min(jIndex + 2 * index, source.Length));
                }

                Array.Copy(destination, source, source.Length);
            }
        }

        private void BottomUpMerge(int[] source, int[] destination, int left, int right, int end)
        {
            var indexLeft = left;
            var indexRight = right;

            for (int index = left; index < end; index++)
            {
                if (indexLeft < right && (indexRight >= end || source[indexLeft] <= source[indexRight]))
                {
                    destination[index] = source[indexLeft];
                    indexLeft++;
                }
                else
                {
                    destination[index] = source[indexRight];
                    indexRight++;
                }
            }
        }
    }

и да речем, може да получа:


Dry run algorithms...
Generating int array with 10000 elements
Quicksort Lomuto: 00:00:00.0031586
Quicksort Hoare: 00:00:00.0029382
Mergesort Top-Down with Subarrays: 00:00:00.0053670
Mergesort Top-Down with Working Copy: 00:00:00.0032543
Mergesort Bottom-Up with Working Copy: 00:00:00.0041929
Heapsort SiftDown: 00:00:02.3419572

ПС: Не съм имплементирал още sift up на хийп сорта

#13217 (ツ) johnfound
Създадено на 30.09.2020, видяно: 962 пъти.

Ами в повечето случаи какво сортиране да се избере зависи от други фактори - например дали алгоритъма трябва да е устойчив, или няма значение.

Също, в сериозните случаи се използват комбинирани алгоритми - например QuickSort, но когато парчето стане съвсем малко, се сортира с insertion или buble...

Иначе, реално най-добре е, да не сортираш въобще, ако можеш да го избегнеш. ;-)

#13218 (ツ) Courvoisier
Създадено на 30.09.2020, видяно: 958 пъти.

Не, че ми се налага да го пиша, но понеже съм го учил преди 10-на години (малко повече) и имам тапия и го работя, се предполага, че пея алгоритми от сън да ме бутнат. Не че го правя rofl.

Всъщност, за 10 години ми се е налагало да имплементирам IComparable рядко. Последно ми се наложи когато трябваше да определя по accept header-а какво предпочита клиента за формат на отговор, xml, json, csv, don't ask why...

#13219 (ツ) Stilgar
Създадено на 30.09.2020, видяно: 933 пъти.

Бе квото каже Array.Sort

#13220 (ツ) synergie
Създадено на 30.09.2020, видяно: 932 пъти.

Съсипахте форумчето с тия технически теми Бат Рамбо не може да се включи.

@Courvoasier това за подареите и хийп сорта не го разбрах? Твоята имплементация също е in-place,

#13222 (ツ) Golden Gega
Създадено на 30.09.2020, видяно: 925 пъти.

order by

Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.

#13223 (ツ) johnfound
Създадено на 30.09.2020, видяно: 920 пъти.
Golden Gega

order by

Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.

Всъщност, order by не е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.

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

#13225 (ツ) Courvoisier
Последно редактирано на 30.09.2020 от Courvoisier, видяно: 917 пъти.
synergie

Съсипахте форумчето с тия технически теми Бат Рамбо не може да се включи.

@Courvoasier това за подареите и хийп сорта не го разбрах? Твоята имплементация също е in-place,

Да... този код го бях писал преди година и се чудех за какво да вдигна тема rofl, и ето, на. Иначе го преписвах от Simple heap with heapsort. Но е по- бавен от останалите.

#13228 (ツ) Courvoisier
Последно редактирано на 30.09.2020 от Courvoisier, видяно: 914 пъти.
johnfound

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

Да речем следния сценарии. Трябва да върнеш отговор според accept-а. Може да връщаш xml, json, csv, html5, xhtml. Колекцията, която трябва да върнеш не е важна, но да речем е списък с геолокации и температури по целзий и фаренхайт и дата/час на измерването. Няма никакво значение колекцията, но да кажем, че от RDBMS-а е подредена по дата/час.

Правиш GET със Chrome. Той подава


accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.9

Като няма q=, то тогава q=1. Т.е.,


accept: text/html;q=1,application/xhtml+xml;q=1,application/xml;q=0.9,image/avif;q=1,image/webp;q=1,image/apng;q=1,*/*;q=0.8,application/signed-exchange;v=b3;q=0.9

Откъде знаеш какво предпочита? Може да вземеш първи елемент, но някой може да ти прати

text/xml;q=0.9,application/json

Т.е., не става да вземам първи, трябва да проверя.

Какво може да направиш?

Кийп ит ООП, правя си клас. Той ще държи Position : int, Quantity : int, MimeType : MimeType. Имплементира АйЕкуейтабъл и АйКомперабъл, вкарвам ги в лист, сортирам и си вземем първи елемент. Няма смисъл да ги вкарвам в истинска база. Though, мога да сложа in-memory база и да си правя заявки към нея. Но това на всеки рекуест мисля, че ще яде повече RAM, защото има повече обекти.

Как ще го сортира? Инсъртшън, хийп или куик сорт, според зависи.

Накрая трябва да получа:


accept: 

0: text/html;q=1
1: application/xhtml+xml;q=1
2: image/avif;q=1
3: image/webp;q=1
4: image/apng;q=1
5: application/xml;q=0.9
6: application/signed-exchange;v=b3;q=0.9
7: */*;q=0.8 // давай кот дооди

ОК, клиента иска HTML, ще му върнем HTML5. Десериализираме (нека го наречем така) целия списък с температура като Ordered List в HTML (таблици e so old school). Ако пък е искал JSON, връщаме му JSON, защото на последно място клиента иска */*. A ако е искал PDF, Но ние не го поддържаме, тогава ние решаваме какво да върнем. Става една идея по- сложно. Ние пък, имаме същия списък с предпочитани от нас маймтайпове. Ние предпочитаме application/json, после xml, после csv, после HTML, после XHTML, и нататък не предпочитаме нищо. Но волята на клиента е от по- голямо значение, ако предпочита HTML на първо място, а ние на последно, трябва да върнем HTML. Ако предпочита кво да е, ние ще върнем каквото ние предпочитаме и това е application/json.

Хмм, май трябва да видя как са го писали в неткора...

Иначе това второто как бихте го решили? Прост вариант е да търся най- предпочитаното от клиента имам ли го, да речем го нямам. Почвам второто, имам ли го, не. Почвам третото, имам ли го, да, връщам него.

#13229 (ツ) Courvoisier
Последно редактирано на 30.09.2020 от Courvoisier, видяно: 907 пъти.
Golden Gega

order by

Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.

Верно е това, обаче като ме питат тоя сортиращ алгоритъм как работи, или още по- лошо, как се имплементира, някак си, като погромист се подразбира, че ще знам такива неща. Е, никой не ме е питал как ще го имплементирам :-) Но ми се е случвало да ме питат какво представлява. Реално, след 3-ти курс не ми се е налагало да имплементирам търсещ алгоритъм, ползвам си API-то. У нас си имплементирам глупости фор фън, защото явно имам професионални изкривявания. Гийкщина ли му викаха... имам една тениска I'm a proud geek, но тук не я нося.

#13230 (ツ) Golden Gega
Създадено на 30.09.2020, видяно: 897 пъти.
Courvoisier
Golden Gega

order by

Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.

Верно е това, обаче като ме питат тоя сортиращ алгоритъм как работи, или още по- лошо, как се имплементира, някак си, като погромист се подразбира, че ще знам такива неща. Е, никой не ме е питал как ще го имплементирам :-) Но ми се е случвало да ме питат какво представлява. Реално, след 3-ти курс не ми се е налагало да имплементирам търсещ алгоритъм, ползвам си API-то. У нас си имплементирам глупости фор фън, защото явно имам професионални изкривявания. Гийкщина ли му викаха... имам една тениска I'm a proud geek, но тук не я нося.

Еми като станеш архитектче или както там се вика няма да те питат, казваш авторитетно че данните са сортирани и това е

#13232 (ツ) Golden Gega
Създадено на 30.09.2020, видяно: 894 пъти.
johnfound
Golden Gega

order by

Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.

Всъщност, order by не е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.

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

ставаше дума за SQL-ското order by

#13246 (ツ) ФейкПрофил
Създадено на 30.09.2020, видяно: 884 пъти.
Golden Gega
johnfound
Golden Gega

order by

Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.

Всъщност, order by не е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.

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

ставаше дума за SQL-ското order by

OrderBy може да сортира, аможе и да не сортира. Зависи от това какви индекси имаш.

#13247 (ツ) Golden Gega
Създадено на 30.09.2020, видяно: 881 пъти.
ФейкПрофил
Golden Gega
johnfound
Golden Gega

order by

Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.

Всъщност, order by не е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.

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

ставаше дума за SQL-ското order by

OrderBy може да сортира, аможе и да не сортира. Зависи от това какви индекси имаш.

Това е супер интересно, я ми дай един пример дето имаш order by пък то не сортира по него

#13248 (ツ) Унуфри
Създадено на 30.09.2020, видяно: 878 пъти.
Golden Gega
ФейкПрофил
Golden Gega
johnfound
Golden Gega

order by

Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.

Всъщност, order by не е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.

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

ставаше дума за SQL-ското order by

OrderBy може да сортира, аможе и да не сортира. Зависи от това какви индекси имаш.

Това е супер интересно, я ми дай един пример дето имаш order by пък то не сортира по него

Само в нашият форум order by може да не сортира. Иначе в. нетя е възможно ако нямаш comparer. Верно сте безработни на заплата. За интервю ли да помним алгоритми за сортиране? Щото на нито едно не съм виждал да дават, ни я съм давал.

#13249 (ツ) johnfound
Създадено на 30.09.2020, видяно: 878 пъти.

Гега, и в моя пост и след това, става въпрос, че SQL-ското "order by" не сортира масиви с класическите алгоритми за сортиране. Просто извлича данните в правилният ред, според някакъв индекс. Реално никъде нямаш масив и после сортиране.

Даже и в случай, че няма подходящ индекс - "order by" първо прави временен индекс и след това извлича данните в нужният ред.

#13251 (ツ) ФейкПрофил
Последно редактирано на 30.09.2020 от ФейкПрофил, видяно: 874 пъти.
Golden Gega
ФейкПрофил
Golden Gega
johnfound
Golden Gega

order by

Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.

Всъщност, order by не е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.

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

ставаше дума за SQL-ското order by

OrderBy може да сортира, аможе и да не сортира. Зависи от това какви индекси имаш.

Това е супер интересно, я ми дай един пример дето имаш order by пък то не сортира по него

Нарича се pipelined order by: https://use-the-index-luke.com/sql/sorting-grouping/indexed-order-by

За рамбо, който не чете английски - общо взето обхождаш редовете в index order, като те там са вече сортирани - демек ходиш по един linked list.

#13252 (ツ) Golden Gega
Създадено на 30.09.2020, видяно: 871 пъти.
johnfound

Гега, и в моя пост и след това, става въпрос, че SQL-ското "order by" не сортира масиви с класическите алгоритми за сортиране. Просто извлича данните в правилният ред, според някакъв индекс. Реално никъде нямаш масив и после сортиране.

Даже и в случай, че няма подходящ индекс - "order by" първо прави временен индекс и след това извлича данните в нужният ред.

Мисля че имаш абсолютно погрешна представа как работи select/order by. Казано в прости стъпки - първо select-a прави временен result set, после order by го сортира според колоните и начините които си задал, и накрая ти се връща подредения набор (result set). Индексите по отношение на сортирането не играя никаква роля.

И като цяло мисля че малко ти е грешна представата за индексите, поне ако говорим за релационни бази.

#13253 (ツ) johnfound
Създадено на 30.09.2020, видяно: 869 пъти.
Golden Gega

първо select-a прави временен result set, после order by го сортира

Да бе, да. Сега остава да кажеш, че го прави в RAM-а и там го сортира. Естествено, че не работят така базите данни.

0 1 2

Heap Sort vs Quick Sort vs Merge Sort за Array
4

AsmBB v2.9 (check-in: 36c85c790bbb4625); SQLite v3.31.1 (check-in: 3bfa9cc97da10598);
©2016..2020 John Found; Licensed under EUPL. Powered by Assembly language Created with Fresh IDE