Shellsort, wątpliwości.

0

Witam!
Uczę się sortowań i trafiłem na Shellsorta, staram się je pisać samemu i potem sprawdzać na stronie, ale Shellsort wyszedł mi inny i mam wątpliwości czy jest prawidłowo, sortuje poprawnie.

void shellsort(int a[], int n)
{
    int l,temp;
    for(int i=n/2;i>0;i/=2)
    {
        for(int j=0;j<i;j++)
        {
            for(int k=n-2*i+j;k>=0;k-=i)
            {
                temp=a[k];
                l=k+i;
                while(l<n&&temp>a[l])
                {
                    a[l-i]=a[l];
                    l+=i;
                }
                a[l-i]=temp;
            }
        }
    }
} 
0

Możesz rozwiać te wątpliwości dopisując trochę kodu testującego.

  • posortuj pusty zbiór
  • posortuj dane losowe
  • posortuj dane posortowane odwrotnie niż chcemy
  • posortuj dane posortowane tak jak chcemy
  • posortuj dane z duplikatami (np. tab[i] = i % 10 )

Do tego policz jaką masz złożoność obliczeniową (ile operacji / liczba elementów).

BTW, nie stosuj zmiennych o nazwie "l" (~1) oraz "O" (~0).

0

Testowałem trochę i sortuje poprawnie dla różnych danych, ale złożoność jest na pewno większa niż powinna być więc Sortowaniem Shell'a trudno to nazwać.

0

Implementację referencyjną masz w K&R
http://helion.pl/ksiazki/jezyk-ansi-c-programowanie-wydanie-ii-brian-w-kernighan-dennis-m-ritchie,jansic.htm

Ta implementacja ma dwie właściwości:

  • ciężko ją zrozumieć
  • nie da się tego sp...yć, chyba że się uprzesz
/* shellsort:  sort v[0]...v[n-1] into increasing order */ 
   void shellsort(int v[], int n) 
   { 
       int gap, i, j, temp; 

       for (gap = n/2; gap > 0; gap /= 2) 
           for (i = gap; i < n; i++) 
               for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) { 
                   temp = v[j]; 
                   v[j] = v[j+gap]; 
                   v[j+gap] = temp; 
               } 
   } 
0

Pisałem to na zasadzie że przeczytałem jak działa i dosłownie tak napisałem. Sprawdzałem czasy dla n=1000000 i czas był t=~0,330 s a dla n=2000000 czas był t= ~0,775. to O(n^2) to chyba nie jest.

0

Jeśli możesz to podaj źródło. O ile się nie myślę to Twój algorytm można przyspieszyć przez inny wybór początkowego 'i' oraz inny krok iteracyjny w najbardziej zewnętrznym forze.

0
lordlucifer napisał(a):

Pisałem to na zasadzie że przeczytałem jak działa i dosłownie tak napisałem. Sprawdzałem czasy dla n=1000000 i czas był t=~0,330 s a dla n=2000000 czas był t= ~0,775. to O(n^2) to chyba nie jest.

Złożoność shellsort to średnio N log N, więc z grubsza się zgadza.

http://pl.wikipedia.org/wiki/Sortowanie_Shella

0

To była strona jakiegoś liceum z Tarnowa i tam był inny dobór odległości między wyrazami wyliczany potem ale się nie skupiałem na tym tylko na samym zapisie na razie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1