Poate sa imi explice si mie cineva, va rog frumos, cum functioneaza shell sort-ul?In principiu inteleg, si dupa ce am cautat o groaza pe google, am gasit ca cea mai buna explicatie este:
http://goanna.cs.rmit.edu.au/~stbird/Tutorials/ShellSort.html .In prinicipiu mi se pare destul de simplu, dar in introducere ei spun ca trebuie ales un n("pasul" care il folosesc la sortare), cat mai aproape de jumatatea numarului de elemente, astfel incat sa nu fie o putere a lui 2, iar dupa ce sortez elementele din n in n, sortez din n/2 in n/2, adica pasul se imparte la 2, etc...(pana cand pasul este mai mic sau egal cu 1).
Do not choose (for example) 16 as your first n, and then keep dividing by 2 until you reach 1. It has been mathematically proven that using only numbers from the power series {1, 2, 4, 8, 16, 32, ...} produces the worst sorting times. The fastest times are (on average) obtained by choosing an initial n somewhere close to the maximum allowed and continually dividing by 2.2 until you reach 1 or less.
Din pacate in exemplu dat ei folosesc n={3,2,1}, pentru un numar de 9 elemente, eu sincer nu prea inteleg cum au ajuns la asta, deoarece daca il impart pe 3 la 2, avand in vedere ca este int, el va fi trunchiat si devine automat 1.In alte locuri am gasit siruri "si mai interesante", si mai greu de inteles , de pasi folositi in sortare.Eu stiu o metoda simpla care face pasul pe rand de la n, la 1 (compar din n/2 in n/2, din n/3 in n/3, pana compar pe fiecare cu urmatorul), dar in comparatie cu asta mi se pare total ineficient, ei spun ca folosind aceea varianta ajung la o complexitate: O(n
3/2).Multumesc anticipat pentru ajutor!