[DSA] Домашно Sorting and Searching Algorithms


5

Та имам малкък проблем с QuickSort - по незнайни причини ми изяжда pivot елемента в крайния резултат, но като го дебъгвам всичко е наред. Ще съм благодарен, ако някой удари едно рамо :)

QuickSort кода: Gist

Оправих го. Като цяло бях омазал предването на стойности.

Едит: Има малка грешка в кода за домашното:

Console.WriteLine("Binary search 101:");
Console.WriteLine(collection.LinearSearch(101));
Console.WriteLine();

Трявбва да е:

Console.WriteLine("Binary search 101:");
Console.WriteLine(collection.BinarySearch(101));
Console.WriteLine();




Отговори



2

Забавен факт: дори алгоритъмът Fisher-Yates не гарантира статистическа случайност на разбъркването - това зависи до голяма степен и от генератора на числа. Например, едно тесте карти има 52! пермутации, докато генераторът на числа има 32 битов seed - де факто, можеш да видиш само 32^2/52! ~ 10^(-58) от всички пермутации (една десето-новемдецилионна!). Да не говорим колко предвидим е seed-а по подразбиране (Environment.TickCount). Има доста опарени от такива работи.

--
intelligence shared is intelligence squared


от staafl (5770 точки)


0
Абсолютно си прав. Има даже програми, които стартират твоята в определена милисекунда за да ти гарантират определен сийд.

от Nikolay.IT (39117 точки)


1

Здравейте,

Ето ги и моите решения.

Като упътване съм използвал wikipedia.

MergeSort и QuickSort са ми рекурсивни.

Binary search-a реших да го направя итеративен.

Притеснява ме факта, че за да върна новата колекция чистя подадената и я пълня наново, тоест хабя памет за още едно копие на колекцията.

Ще се радвам на всякакви препоръки и съвети.

Поздрави!


от nikolaikolarov (2177 точки)


0
днес 1 час въртях и се мъчих и аз - да го направя без нова колекция, ама не можах да го измисля. има вариант с ref, ама става много грозно и променяме малко интерфейса

от vlad0 (6103 точки)

0
И аз го направих така, иначе не се получава.



1

Здравейте,

В моето домашно съм използвал обясненията и псевдо кода от лекцията и уикипедия, като съм се опитал да напиша сортиранията по най-лесния начин. За BinarySearch съм ползвал итеративния подход, за Shuffle този от презентацията. Имах проблем с Quicksort първоначално бях го написал, както е в домашното, след, което реших да го направя с Partition и Swap, но не ми се получи и върнах предишното си решение, това е неработещото , малко го омазах  и не можах да разбера къде е проблемът, затова си върнах по-простото решение.

Поздрави




1
Здравейте ето и моето решение на домашното за сортирането се водех по псевдо кодовете които ни бяха дадени ,а търсещите алгоритми сам си ги направих, като по интересно е бинарното търсене (или поне на мен ми беше по-интересно
),него  съм го реализирал с рекурсия бях се вдъхновил от лекцията за рекурсиите :)
Ето ви и линк към цялото нещо:
https://github.com/KTsolev/SortringAlgoritmsHomework



2
За да не отварям нова тема,реших да питам тук - нормално ли е при подадени 10-ина хиляди елемента на Quick Sort да препълва стек-а? Какви ли имплементации не пробвах и най-много до 15 000 елемента го докарах да може да сортира без да гърми.

от stefanN (952 точки)


0
Не, не е нормално, постни кода.


0
То се оказа, че кода си е ок, а съм подавал на QuickSort вече сортираната от предишните алгоритми колекция - глупаво недоглеждане...и все пак, на сортирана колекция пак не ми се връзва- защо се препълва стек-а Иначе това е кода: http://pastebin.com/NT4AHZ4G, ще съм ти много благодарен ако имаш време да го погледнеш,че тепърва навлизам в алгоритмите:)

от stefanN (952 точки)



1

Решение

При quick и merge sort-a си правя нова променлива със сортиран лист, затривам оригиналната колекция и и добавям всички елементи от сортирания лист. За shuffle използвам описания тук начин. Unit тестовете са в отделен клас.


от dzhenko (3893 точки)


0
Аз си направих един клас да тествам performance на сортиращите алгоритми. Използва се много лесно:
 
PerformanceTester.Test(
    new SelectionSorter<int>(),
    new QuickSorter<int>(),
    new MergeSorter<int>());
 
Тества всеки ISorter с колекция от 10,000 случайни числа. Ето резултат от теста:
 
SelectionSorter:  792.90ms
QuickSorter    :    2.30ms
MergeSorter    :    3.60ms
 
 

от neutrino (3376 точки)