Autor Wątek: algorytmika. podstawy. mini artykuł #01 .2  (Przeczytany 1959 razy)

Offline lethern

  • Użytkownik

# Kwiecień 18, 2006, 21:56:29
Sortowanie

Dane: tablica n-elementowa [1..n] z losowymi elementami ( np. {4, 1, 6, 1, 7} )
Wynik: tablica [1..n], w której elementy tworzą ciąg niemalejący ( np. {1, 1, 4, 6, 7} )

Uwagi ogólne
A -tablica elementów (zbiór elementów)
n -ilość elementów w tablicy A
zbiór -pewien podzbiór naszej tablicy

Spis

1. Sortowanie przez wybór
2. Sortowanie przez wstawianie
3. Kod

Sortowanie przez wybór (selection sort)

Przebieg algorytmu:
-wyszukujemy najmniejszy element w zbiorze [1..n] i przenosimy go na początek (zamieniamy z pierwszym elementem).
-dzięki temu pierwszy element jest na swoim miejscu, pozostaje nam posortowanie reszty [2..n]
-wyszukujemy najmniejszy element w zbiorze [2..n] i przenosimy go na początek (tu: zamieniamy z elementem nr 2 (ponieważ on jest pierwszym w zbiorze [2..n] ) ).
-dzięki temu już dwa elementy są posortowane, pozostaje nam posortowanie reszty [3..n]
-powtarzamy, dopóki nie posortujemy całości

Algorytm:
-dla kolejnych zbiorów [1..n], [2..n], [3..n], [n] znajdź najmniejszy element i przenieś go
na początek zbioru

Pseudokod:
 for i = 1 to n do   // i to numer pierwszego elementu zbioru
    k = i      // k to aktualny najmniejszy element zbioru
   for j = i to n do   // j to kolejne elementy przeszukiwanego zbioru
     if A(j)<A(k) then   // jeżeli element j jest mniejszy, ustaw go najmniejszym
       k = j
   zamien( A(j), A(k) )   // element najmniejszy zamienia z elementem pierwszym w zbiorze

Uwagi:
1. zamien( a, b) -przykładowy kod
  tmp = a
  a = b
  b = tmp
2. pierwszą pętlę można skrócić do postaci '1 to n-1' -dzięki temu nie musimy przeszukiwać zbioru [n] (który zawiera tylko jeden element)
3. drugą pętlę można skrócić do postaci 'i+1 to n' -dzięki temu nie będziemy porówywać 'A(j)<A(k)' dla tych samych elementów ( j=i, k=i )
4. złożność algorytmu O(n^2)

Przykład:
tablica nieposortowana: { 4, 5, 1, 3, 2, 6 }; kolejne kroki algorytmu:
0) 4, 5, 1, 3, 2, 6
1) 1, 5, 4, 3, 2, 6
2) 1, 2, 4, 3, 5, 6
3) 1, 2, 3, 4, 5, 6
4) 1, 2, 3, 4, 5, 6,
wynik: { 1, 2, 3, 4, 5, 6 }

Sortowanie przez wstawianie (insertion sort)

Przebieg algorytmu:
-w tablicy rozróżniamy dwa zbiory: pierwszy posortowany ( początkowo tworzony przez jeden element tablicy: [1] -jako, że posiada jeden element, jest od razu posortowany ) oraz zbiór nieposortowany ( reszta tablicy: [2..n] )
-kolejne elementy ze zbioru nieposortowanego umieszczamy w zbiorze posortowanym, uzyskując ostatecznie posortowaną tablicę:
-bierzemy pierwszy element ze zbioru nieposortowanego [2]
-szukamy dla niego miejsca w posortowanym zbiorze, tzn. aby po wstawieniu zbiór pozostał posortowany
-rozsuwamy zbiór i wstawiamy nowy element
-uzyskujemy: zbiór posortowany (teraz dwu-elementowy [1..2]) i dalej zbiór nieposortowany [3..n])
-bierzemy pierwszy element ze zbioru nieposortowanego [3]
-szukamy dla niego odpowiedniego miejsca do wstawienia w posortowany zbiór
-rozsuwamy zbiór aby móc wstawić element
-powtarzamy, dopóki nie ułożymy wszystkich elementów nieposortowanych

Algorytm:
-przyjmij podział tablicy na: zbiór posortowany [1..(k-1)] i zbiór nieposortowany [k..n], początkowo k=2 (czyli [1] i [2..n])
-dla wszystkich elementów zbioru nieposortowanego powtarzaj:
  -zapamiętaj pierwszy element [k] zbioru nieposortowanego
  -znajdź w zbiorze posortowanym miejsce, w które należy wstawić (pamiętany) element, aby zachować porządek niemalejący
  -aby takie miejsce znaleźć, przeglądamy zbiór (posortowany) od końca i zatrzymujemy się na pierwszym elemencie mniejszym niż element pamiętany. Nasz element ma zostać wstawiony między mniejszy i większy, aby zbiór pozostał posortowany
  -aby móc wstawić element, przesuwamy wszystkie elementy większe od 'wybranego miejsca' o pozycję w prawo, dzięki czemu w roztęp wstawiamy (pamiętany) element
  -zwiększ k i powtórz dla kolejnego elementu zbioru nieposortowanego

Pseudokod:
 for k = 2 to n do // k to początek zbioru nieposortowanego
   element = A[k]
   i = k-1
   while( i>0 )and( A>element ) do //szukamy miejsca i tworzymy roztęp
     A[i+1] = A // przesuwamy elementy
     i = i-1
   a[i+1] = element //wstawiamy element tuz za mniejszym

Uwagi:
1. w pętli while przesuwamy elementy, dopóki są większe niż pamiętany element. Kiedy pętla się zakończy, wstawiamy pamiętany element w A[i+1] -będzie to miejsce po mniejszym i przed większym elementem, ewentualnie początek lub koniec (zbioru posortowanego [1..k])
2. złożność algorytmu O(n^2)

Przykład:
tablica nieposortowana: { 4, 5, 1, 3, 2, 6 };
k=1; zbiór posortowany: { 4 }; zbiór nieposortowany: {5, 1, 3, 2, 6};
kolejne kroki algorytmu:
1) { 4, 5, 1, 3, 2, 6 }
   a) zapamiętany element: 5
   b) aby zachować porządek niemalejący, element należy wstawić na końcu ( za elementem 4 ) zbioru posortowanego
   c) nie mamy elementów do rozsunięcia (w zbiorze posortowanym za elementem 4 nie ma więcej)
   d) wstawiamy element na pozycję 2
2) { 4, 5, 1, 3, 2, 6 }
   a) zapamiętany element: 1
   b) aby zachować porządek niemalejący, element należy wstawić przed elementem 4, na pozycji 1
   c) rozsuwamy zbiór: przesuwamy elementy na prawo od wybranej pozycji
   { 4, 4, 5,  3, 2, 6 }
   d) wstawiamy element na pozycji pierwszej
3) { 1, 4, 5, 3, 2, 6 }
   a) zapamiętany element: 3
   b) element należy wstawić: między elementami 1 a 4
   c) przesuwamy elementy w prawo od pozycji drugiej
   { 1, 4, 4, 5, 2, 6 }
   d) wstawiamy element
4) { 1, 3, 4, 5, 2, 6 }
   a) zapamiętany element: 2
   ) element należy wstawić: między elementami 3 a 4
   c) przesuwamy elementy w prawo od pozycji trzeciej
   { 1, 3, 3, 4, 5, 6 }
   d) wstawiamy element
5) { 1, 2, 3, 4, 5, 6 }
   a) zapamiętany element: 6
   b) element należy wstawić: na ostatniej pozycji
   c) nie ma elementów do przesunięcia
   d) wstawiamy element
6) {1, 2, 3, 4, 5, 6 }
   a) koniec zbioru nieposortowanego, tablica posortowana
wynik: { 1, 2, 3, 4, 5, 6 }


Kod

1. Sortowanie przez wybór
for i = 1 to n-1 do
  k = i
  for j = i+1 to n do
    if A(j)<A(k) then
      k = j
  zamien( A(j), A(k) )

2. Sortowanie przez wstawianiefor k = 2 to n do
  element = A[k]
  i = k-1
  while( i>0 )and( A[i]>element ) do
    A[i+1] = A[i]
    i = i-1
  a[i+1] = element

// EDIT by Q8 - dobrze, ale o co chodzi?
« Ostatnia zmiana: Kwiecień 18, 2006, 23:36:10 wysłana przez lethern »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Wyszo

  • Użytkownik

# Kwiecień 18, 2006, 22:21:20
@ Queight: jak to o co chodzi? Taka mała pomoc naukowa - słowem miniartykuł o metodach sortowaniea  :D

Problem polega na tym, że powyższy post powinien znaleźć się w dziale foosy, który jak wiemy nie istnieje. Dlatego podobne artykuły proponuję umieszczać tutaj, coby się nie zagubiły w forumowych odmętach: http://regedit.warsztat.gd/warsztat/articles.php?x=add  ;D

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Kwiecień 18, 2006, 22:23:41
jak to ma być na forum to TRZEBA dodać znaczniki [code/code]
i brakuje mojej ulubionej metody - kopcowania :D

Offline Hadrian W.

  • Użytkownik
    • Homepage

# Kwiecień 18, 2006, 22:25:50
Na to jak tu gdzies Regedit powiedzial jest miejsce: http://regedit.i365.pl/warsztat/tips.php

Offline lethern

  • Użytkownik

# Kwiecień 18, 2006, 22:27:05
Hmm :)
artykuł jako artykuł się nie nadaje, ponieważ (jeśli będzie mi dane i będę w stanie) mam zamiar dodawać kolejne elementy w formie edit.
Rozmawiałem troszku z g[R]eK'iem i miałem to tu wrzucić :)
z góry dzięki za konkretne komentarze.
@shyha -postaram się poprawić w niedalekie przyszłości

@Queight -rozumiem, że tam trafiają mini-arty :) ale nie wiem, czy można je edytować (przyda się). Poza tym, to nie jest związane z programowaniem gier :) /szczegół/
« Ostatnia zmiana: Kwiecień 18, 2006, 23:27:26 wysłana przez lethern »

Offline Hadrian W.

  • Użytkownik
    • Homepage

# Kwiecień 18, 2006, 22:38:50
Cytat: Porady
W tym dziale znajduje się zbiór krótkich artykułów z małymi poradami na temat programowania gier. To dział nawiązujący do tradycji pisania krótkich monograficznych artykułów, który dawniej nazywał się na Warsztacie "COTW" (Coś Of The Week) lub "Foosy".