Кое според вас е по- удачно за сортиране на арей? Heap Sort или Quick/Merge Sort? Да речем, че ако правя хийпсорт на арей, то ще трябва да създам подареи, които харчат доста време. Отбелязвам, не говоря за линкд лист.
Това са простотии, с които се занимавам в свободното си време, за да не забравям алгоритми.
Примерна имплементация на хийпсорт:
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 на хийп сорта
Ами в повечето случаи какво сортиране да се избере зависи от други фактори - например дали алгоритъма трябва да е устойчив, или няма значение.
Също, в сериозните случаи се използват комбинирани алгоритми - например QuickSort, но когато парчето стане съвсем малко, се сортира с insertion или buble...
Иначе, реално най-добре е, да не сортираш въобще, ако можеш да го избегнеш. 
Не, че ми се налага да го пиша, но понеже съм го учил преди 10-на години (малко повече) и имам тапия и го работя, се предполага, че пея алгоритми от сън да ме бутнат. Не че го правя 
.
Всъщност, за 10 години ми се е налагало да имплементирам IComparable рядко. Последно ми се наложи когато трябваше да определя по accept header-а какво предпочита клиента за формат на отговор, xml, json, csv, don't ask why...
Съсипахте форумчето с тия технически теми Бат Рамбо не може да се включи.
@Courvoasier това за подареите и хийп сорта не го разбрах? Твоята имплементация също е in-place,
order by
Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.
Golden Gega order by
Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.
Всъщност, order by не е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.
В края на краищата, данните в масива все отнякъде следва да са се взели. Обикновено елемент след елемент се натрупват в него. Ако толкова трябва тези елементи да са сортирани, то обикновено е по-изгодно да се организира двоично търсене на всеки постъпващ елемент и директно да се изгради и индекс на данните в нужният ни ред.
synergie Съсипахте форумчето с тия технически теми Бат Рамбо не може да се включи.
@Courvoasier това за подареите и хийп сорта не го разбрах? Твоята имплементация също е in-place,
Да... този код го бях писал преди година и се чудех за какво да вдигна тема , и ето, на. Иначе го преписвах от Simple heap with heapsort. Но е по- бавен от останалите.
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.
Хмм, май трябва да видя как са го писали в неткора...
Иначе това второто как бихте го решили? Прост вариант е да търся най- предпочитаното от клиента имам ли го, да речем го нямам. Почвам второто, имам ли го, не. Почвам третото, имам ли го, да, връщам него.
Golden Gega order by
Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.
Верно е това, обаче като ме питат тоя сортиращ алгоритъм как работи, или още по- лошо, как се имплементира, някак си, като погромист се подразбира, че ще знам такива неща. Е, никой не ме е питал как ще го имплементирам 
Но ми се е случвало да ме питат какво представлява. Реално, след 3-ти курс не ми се е налагало да имплементирам търсещ алгоритъм, ползвам си API-то. У нас си имплементирам глупости фор фън, защото явно имам професионални изкривявания. Гийкщина ли му викаха... имам една тениска I'm a proud geek, но тук не я нося.
Courvoisier Golden Gega order by
Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.
Верно е това, обаче като ме питат тоя сортиращ алгоритъм как работи, или още по- лошо, как се имплементира, някак си, като погромист се подразбира, че ще знам такива неща. Е, никой не ме е питал как ще го имплементирам
Еми като станеш архитектче или както там се вика няма да те питат, казваш авторитетно че данните са сортирани и това е
johnfound Golden Gega order by
Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.
Всъщност,
order byне е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.В края на краищата, данните в масива все отнякъде следва да са се взели. Обикновено елемент след елемент се натрупват в него. Ако толкова трябва тези елементи да са сортирани, то обикновено е по-изгодно да се организира двоично търсене на всеки постъпващ елемент и директно да се изгради и индекс на данните в нужният ни ред.
ставаше дума за SQL-ското order by
Golden Gega johnfound Golden Gega order by
Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.
Всъщност,
order byне е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.В края на краищата, данните в масива все отнякъде следва да са се взели. Обикновено елемент след елемент се натрупват в него. Ако толкова трябва тези елементи да са сортирани, то обикновено е по-изгодно да се организира двоично търсене на всеки постъпващ елемент и директно да се изгради и индекс на данните в нужният ни ред.
ставаше дума за SQL-ското order by
OrderBy може да сортира, аможе и да не сортира. Зависи от това какви индекси имаш.
ФейкПрофил Golden Gega johnfound Golden Gega order by
Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.
Всъщност,
order byне е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.В края на краищата, данните в масива все отнякъде следва да са се взели. Обикновено елемент след елемент се натрупват в него. Ако толкова трябва тези елементи да са сортирани, то обикновено е по-изгодно да се организира двоично търсене на всеки постъпващ елемент и директно да се изгради и индекс на данните в нужният ни ред.
ставаше дума за SQL-ското order by
OrderBy може да сортира, аможе и да не сортира. Зависи от това какви индекси имаш.
Това е супер интересно, я ми дай един пример дето имаш order by пък то не сортира по него
Golden Gega ФейкПрофил Golden Gega johnfound Golden Gega order by
Все пак пишем ламерски софтуер - бизнес системи основно, и ползваме, Боже опази!, релационни бази данни.
Всъщност,
order byне е сортиране в класическият вид. То реално именно това се получава в реалните проекти - данните по-скоро се събират в готов за употреба правилен ред и просто не възниква нужда да се сортират.В края на краищата, данните в масива все отнякъде следва да са се взели. Обикновено елемент след елемент се натрупват в него. Ако толкова трябва тези елементи да са сортирани, то обикновено е по-изгодно да се организира двоично търсене на всеки постъпващ елемент и директно да се изгради и индекс на данните в нужният ни ред.
ставаше дума за SQL-ското order by
OrderBy може да сортира, аможе и да не сортира. Зависи от това какви индекси имаш.
Това е супер интересно, я ми дай един пример дето имаш order by пък то не сортира по него
Само в нашият форум order by може да не сортира. Иначе в. нетя е възможно ако нямаш comparer. Верно сте безработни на заплата. За интервю ли да помним алгоритми за сортиране? Щото на нито едно не съм виждал да дават, ни я съм давал.
Гега, и в моя пост и след това, става въпрос, че SQL-ското "order by" не сортира масиви с класическите алгоритми за сортиране. Просто извлича данните в правилният ред, според някакъв индекс. Реално никъде нямаш масив и после сортиране.
Даже и в случай, че няма подходящ индекс - "order by" първо прави временен индекс и след това извлича данните в нужният ред.
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.
johnfound Гега, и в моя пост и след това, става въпрос, че SQL-ското "order by" не сортира масиви с класическите алгоритми за сортиране. Просто извлича данните в правилният ред, според някакъв индекс. Реално никъде нямаш масив и после сортиране.
Даже и в случай, че няма подходящ индекс - "order by" първо прави временен индекс и след това извлича данните в нужният ред.
Мисля че имаш абсолютно погрешна представа как работи select/order by. Казано в прости стъпки - първо select-a прави временен result set, после order by го сортира според колоните и начините които си задал, и накрая ти се връща подредения набор (result set). Индексите по отношение на сортирането не играя никаква роля.
И като цяло мисля че малко ти е грешна представата за индексите, поне ако говорим за релационни бази.