Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

- zdjęcie

Mariusz M

Rejestracja: 11 Sep 2010
Offline Ostatnio: Apr 03 2018 03:20
*****

Moje tematy

Sortowanie Shella

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 


Otoczka wypukła

20.09.2017 - 10:20

	
		GRAHAM-SCAN(Q)
		1 let p0 be the point in Q with the minimum y-coordinate,
		        or the leftmost such point in case of a tie
		2  let <p1,p2,...,pm> be the remaining points in Q,
		          sorted by polar angle in counterclockwise order around p0
		          (if more than one point has the same angle, remove all but
		           the one that is farthest from p0)
		3  let S be an empty stack
		4  PUSH(p0,S)
		5  PUSH(p1,S)
		6  PUSH(p2,S)
		7  for i=3 to m
		8        while the angle formed by points NEXT-TO-TOP(S), TOP(S), and pi makes a nonleft turn
		9               POP(S)
		10      PUSH(pi,S)
		11 return S

 

 

Jak przetłumaczylibyście ten pseudokod na polski

 


Kulki

14.05.2017 - 09:26

Znalazłem u pewnego kolesia grę w kulki 
Brakuje w niej jednak sprawdzania ukośnych linii a także zapisu wyniku do pliku

 

http://www.wklej.org/id/3112539/
http://www.wklej.org/id/3112545/