Shell Sort

[•Mikeys]

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!

[•belgun_adrian]

http://en.wikipedia.org/wiki/Shell_sort#Gap_sequence

The best known sequence according to research by Marcin Ciura is 1, 4, 10, 23, 57, 132, 301, 701, 1750. This study also concluded that "comparisons rather than moves should be considered the dominant operation in Shellsort." A Shell sort using this sequence runs faster than an insertion sort or a heap sort, but even if it is faster than a quicksort for small arrays, it is slower for sufficiently big arrays. After 1750, gaps in geometric progression can be used, such as:

Cod:

nextgap = round(gap * 2.3) 

Another sequence which performs empirically well is the Fibonacci numbers (leaving out one of the starting 1's) to the power of two times the golden ratio, which gives the following sequence: 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713.

[•chera_lary]

Totusi iti recomand sa folosesti quickSort! Plus ca pentru quickSort nu e nevoie sa stii neaparat codul sursa al lui deoarece se afla deja in biblioteca c++, iar daca folosesti stl-ul o sa gasesti si mai multi alogritmi deja scrisi! Bafta !

[•toni2007]

Si daca omu' codeaza in pascal ?

[•Mikeys]

Multumesc mult! Nu folosesc pascal  (dar in gimnaziu am folosit  ) ..desi ideea ta o sustin deoarece acea sortare ma intereseaza sa o inteleg ca algoritm, de functii stiu si eu, dar in prinicipiu imi place sa inteleg cat mai multe, deoarece consider ca daca tu stii bine bazele, mai departe te descurci si singur.Si cunoscand mai multe ai o baza mai solida .