[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();




Отговори



6

Здравейте!

Днес отделих известно време да напиша това домашно, не отнема много време. :) Та, ето моите решения на задачите: GitHub.

Имплементациите на сортиращите алгоритми са стандартни. По-интересен беше MergeSort използвам втори списък за сливането. Получи се и малко объркване, защото когато присвоим нова стойност на collection в метода Sort, то НЕ се променя колекцията, която сме подали. Затова използвам изчистване и наливане отново на елементите. 

Алгоритмите за търсене също са стандартни - линейно обхождане на колекцията и индикиране за наличие/неналичие на елемента и двоично търсене с итеративен вариант, като първо сортирам колекцията.

За Shuffle метода използвам алгоритъма на Fisher-Yates, като обхождам отзад напред, за да си спестя няколко излишни калкулации (събирания). Сложността е O(n), защото имаме едно обходане на колекцията.

Написах и тестове за сортиранията и търсенията - като при сортирането тествам сортирана, рандом и обърната колекции. Тестовете при търсенето са стандартни.

Ако имате забележки или съвети, моля споделете. :)

ПП Благодаря на Teodor Kurtev 1 за идеята за изчистването и наливането на колекцията отново! :)


от vlad_karamfilov (4595 точки)


0
Всичко изглежда супер, само мога да предложа смяната на елементите да е изнесена в отделен метод Swap() например :)

от gallumbits (2371 точки)

0
И така си е добре поне според мен :)



3

Решение - цък

Няма нищо различно от стандартните имплементации на тези алгоритми. Обособил съм операциите в колкото се може повече методи, за да са по-лесно четими. Спестявам предаването на масив в аргументите на рекурсията, като пазя референция в класа. Тестовете се намират в главната папка на проекта.


от georgi.ivanov (3261 точки)


7

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

Задачка.


от tankovski (2828 точки)


0
Аз смятам, че си се справил доста добре и много ми помогна да си подкарам собственото решение, което доста на подобяваше на твоето, тази разика че при мен pivot не е лист и бях объркала малко проверката. Благодаря.

от atodorova (1273 точки)

0
Хо-хо мерси. Надух се с една идея след коментара ти :).

от tankovski (2828 точки)


1

Алгоритъмът работи по следния начин:

  1. Намира най-малкия елемент в списъка
  2. Разменя го с елемента на първа позиция
  3. Повтаря горните две стъпки за остатъка от списъка
  4.  

http://pastebin.com/jgCWp5Ev




3

Hi,

Попаднах на няколко забавни клипчета на алгоритмите за сортиране, представени чрез народни хора at Sapientia University, Tirgu Mures (Marosvásárhely):

http://www.youtube.com/watch?v=Ns4TPTC8whw

http://www.youtube.com/watch?v=XaqR3G_NVoo

http://www.youtube.com/watch?v=ywWBy6J5gz8

и други......  smiley


от Sevda (97 точки)


0
Много са яки!



3

Може и аз да бъркам, но Fisher–Yates shuffle algorithm в лекцията гърми, защото рандом индекса става прекалено голям (който идва от рандом генератора и се събира с i от обхождащият цикъл) . Ще ми е интересно дали аз съм в грешка. За това използвам следният варянт (за други със същият проблем и наблюдения) :

public static void Shuffle<T>(this IList<T> list)  
{  
    Random rng = new Random();  
    int n = list.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }   

}  


от Al.polichronov (1567 точки)


0
rng.Random в скобите трябва да сложиш максимална и минимална стойност.


0
Пробвай и ще видиш, че работи коректно, иначе като не си му задал долна граница, метода връща положителни числа (не отрицателни, може и 0) http://msdn.microsoft.com/en-us/library/zd1bc8e5.aspx

от Al.polichronov (1567 точки)


1

И аз се справих с домашното: GitHub

Задачките работят тествал съм ги за int и string, ако някой намери някакви бъгове или грешна логика да ми пише.


от nencho83 (538 точки)


3
Да добавя само още една грешка в домашното - преди всяко сортиране трябва да сложим
collection = new SortableCollection

от stoyanov (2483 точки)


1

Благодаря на Teodor Kurtev и  g.stoyanov за съобщените грешки. Вече са оправени.

Поздрави,

Ники


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


1

Ето и моето решение.
За повечето сортиращи масиви не копирам елементите в нов слисък, а директно работя върху подадения и връщам него само че сортиран. За търсенията извиквам първо едно сортиране, с вече написания алгоритъм за сортиране и след това изпълнявам имплемтираното от мен търсене. За Sхuffle обхождам масива и подменям елементите му.


от AsenVal (3487 точки)