Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
        LICEUM        

Sortowanie Shella



  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
Brak odpowiedzi do tego tematu

#1 Mariusz M

Mariusz M

    Wielki Analityk

  • Użytkownik
  • Redaktor
  • 901 postów
414
Instruktor II
  • Płeć:Mężczyzna

Napisano 01.04.2018 - 18:50

Przepisać kod sortowania przez wstawianie tak aby otrzymać sortowanie Shella 

 

Pseudokod z CLRS

 

Insertion-Sort(A)
   for j := 2 to length[A]
     do key := A[j]
          (* Wstaw A[j] w posortowany ciąg A[1..j - 1] *)
           i := j - 1
           while i > 0 and A[i] > key 
               do  A[i + 1] := A[i]
                      i := i - 1
           A[i + 1] := key

 

Dla tablic indeksowanych od zera jak w C 

 

void sortowanie_przez_wstawianie(int *tab,int n)
{
    for(int i=1;i<n;i++)
    {
        int j=i;
        int bufor=tab[j];
        while((j>0)&&(tab[j-1]>bufor))
        {
            tab[j]=tab[j-1];
            j--;
        }
        tab[j]=bufor;
    }
}

 

 

Ciągi takie jak Hibbarda czy Knutha stosunkowo łatwo wygenerować a ich wyrazów nie trzeba przechowywać w tablicy

 

Jeśli chodzi o ciąg zaproponowany przez Pratta to

trochę o nim jest na stronie https://oeis.org/A003586

Tutaj spostrzeżenie Roberta Wilsona pozwoli przesiać liczby z przedziału 1\ldots n

ale to jest zbyt wolny sposób 
Hai He i Gilbert Trau dają sposób który mógłby być wykorzystany 
Jeśli chodzi o ciąg Pratta to problemem może być obliczenie bądź oszacowanie liczby elementów w tym ciągu 
(musimy wiedzieć ile pamięci zaallokować na tablicę dla ciągu)

Sposób przedstawiony na tej stronce wymaga sporo operacji zmiennoprzecinkowych

 

 

Jak oszacować złożoność czasową sortowania Shella dla danego ciągu odstępów ?

 

Czy macie własny ciąg odstępów dla sortowania Shella 


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55