Pawel@Kasprowski.pl Algorytmy i struktury danych
Algorytmy i
struktury danych
struktury danych
Wykład 2: Tablice, Sortowanie
Dr inż. Paweł Kasprowski
pawel@kasprowski.pl
Pawel@Kasprowski.pl Algorytmy i struktury danych
Przechowywanie obiektów w
Przechowywanie obiektów w
tablicy
tablicy
" Zmiany w programie
Tablica zawierać ma obiekty klasy Pracownik
Wyszukiwanie ma się odbywać według nazwisk
" Klasa Pracownik:
class Pracownik {
private String nazwisko;
...
}
Pawel@Kasprowski.pl Algorytmy i struktury danych
Klasa Pracownik
Klasa Pracownik
class Pracownik{
private String imie;
private String nazwisko;
private int wiek;
public Pracownik(String imie,String nazwisko,int wiek) {
this.imie = imie;
this.nazwisko = nazwisko;
this.wiek = wiek;
}
public String pokazPrac() {
return nazwisko+" "+imie+" "+wiek;
}
public String getNazwisko() {
return nazwisko;
}
Pracownik.java
}
1
Pawel@Kasprowski.pl Algorytmy i struktury danych
Klasa PracArray
Klasa PracArray
class PracArray {
int[] tablica;
int nElem;
public Array(int wielkosc) {
t bli i t[ i lk ]
tablica = new int[wielkosc];
nElem = 0;
}
public void wstaw(int wartosc) {
tablica[nElem]=wartosc;
nElem++;
}
Pawel@Kasprowski.pl Algorytmy i struktury danych
Klasa PracArray
Klasa PracArray
class PracArray {
Pracownik[] tablica;
int nElem;
public Array(int wielkosc) {
t bli P ik[ i lk ]
tablica = new Pracownik[wielkosc];
nElem = 0;
}
public void wstaw(Pracownik wartosc) {
tablica[nElem]=wartosc;
nElem++;
}
Pawel@Kasprowski.pl Algorytmy i struktury danych
Wyszukiwanie
Wyszukiwanie
public boolean szukaj(int klucz) {
int i=0;
while(i
&& bli [i]! kl )
&& tablica[i]!=klucz)
i++;
if(i==nElem)
return false;
else
return true;
2
Pawel@Kasprowski.pl Algorytmy i struktury danych
Wyszukiwanie
Wyszukiwanie
public boolean szukaj(String klucz) {
int i=0;
while(i&& ! bli [i] N i k () l (kl ))
&& !tablica[i].getNazwisko().equals(klucz))
i++;
if(i==nElem)
return false;
else
return true;
PracArray.java
Pawel@Kasprowski.pl Algorytmy i struktury danych
Użytkowanie tablicy
Użytkowanie tablicy
// wypełnienie tablicy
Array tab = new Array(20);
for(int i=0; i<10; i++)
tab.wstaw(100*i + 2);
tab.wstaw(505);
tab.pokazTablice();
// wyszukanie elementu
int klucz = 570;
if(tab.szukaj(klucz))
System.out.println("Znaleziono ");
else
System.out.println("Nie znaleziono");
Pawel@Kasprowski.pl Algorytmy i struktury danych
Użytkowanie tablicy
Użytkowanie tablicy
// wypełnienie tablicy
PracArray tab = new PracArray(20);
for(int i=0; i<10; i++)
tab.wstaw(new Pracownik("imie"+i,"nazw"+i,i));
tab.wstaw(new Pracownik("Adam","Kowalski",22));
tab.pokazTablice();
// wyszukanie elementu
String klucz = "nazw5";
if(tab.szukaj(klucz))
System.out.println("Znaleziono ");
else
System.out.println("Nie znaleziono");
PracArrayMain.java
3
Pawel@Kasprowski.pl Algorytmy i struktury danych
Tablica uporządkowana
Tablica uporządkowana
" Wolniejsze wstawianie
najczęściej w środek tablicy
konieczność "rozsuwania" elementów
" Szybsze wyszukiwanie
wyszukiwanie liniowe
" do znalezienia elementu równego lub większego od
szukanego
wyszukiwanie binarne
" podziały połówkowe
Pawel@Kasprowski.pl Algorytmy i struktury danych
Metoda wstaw
Metoda wstaw
public void wstaw(int wartosc) {
int i=0; // znajdz miejsce, gdzie wstawić element (od pierwszego)
while(tablica[i] <= wartosc && ii++;
i t j El // ń l t ó ( d t t i )
int j = nElem; // przesuń elementy w górę (od ostatniego)
while(j > i) {
tablica[j] = tablica[j-1];
j--;
}
tablica[i] = wartosc; // wstaw element w powstałe miejsce
nElem++;
}
Pawel@Kasprowski.pl Algorytmy i struktury danych
Wyszukiwanie liniowe
Wyszukiwanie liniowe
public boolean szukaj(int klucz) {
int i=0;
while(ii++;
;
if(i==nElem)
return false;
else
return true;
}
4
Pawel@Kasprowski.pl Algorytmy i struktury danych
Wyszukiwanie liniowe
Wyszukiwanie liniowe
public boolean szukaj(int klucz) {
int i=0;
while(ii++;
;
if(i==nElem)
return false;
else
return true;
}
Pawel@Kasprowski.pl Algorytmy i struktury danych
Wyszukiwanie liniowe
Wyszukiwanie liniowe
public boolean szukaj(int klucz) {
int i=0;
while(ii++;
;
if(i==nElem || tablica[i] != klucz)
return false;
else
return true;
}
Pawel@Kasprowski.pl Algorytmy i struktury danych
Wyszukiwanie binarne
Wyszukiwanie binarne
public boolean szukajBin(int klucz) {
int dolny = 0, gorny = nElem-1, akt;
boolean koniec = false, znaleziono = false;
while(!koniec && !znaleziono) {
akt = (gorny + dolny)/2;
if(tablica[akt]==klucz) znaleziono=true;
if(tablica[akt] < klucz) dolny = akt + 1;
if(tablica[akt] > klucz) gorny = akt - 1;
if(dolny>gorny) koniec=true;
}
return znaleziono;
}
OrdArray.java
5
Pawel@Kasprowski.pl Algorytmy i struktury danych
Czas wyszukiwania
Czas wyszukiwania
" Każde sprawdzenie eliminuje
połowę elementów
wielkość podziałów
" Wzór na liczbę koniecznych
1 0
podziałów (p) w zależności od
podziałów (p) w zależności od
2 1
wielkości tablicy (N):
4 2
10 4
100 7
p = log2(N)
1 000 10
10 000 14
100 000 17
1 000 000 20
10 000 000 24
Pawel@Kasprowski.pl Algorytmy i struktury danych
Obliczenie czasu działania
Obliczenie czasu działania
" Wstawianie do tablicy nieuporządkowanej
1 krok
czas=K (K stała zależna od szybkości komputera)
" Wstawianie do tablicy uporządkowanej
Wstawianie do tablicy uporządkowanej
minimalnie 1 krok
maksymalnie N kroków
średnio N/2 kroków
średni czas = K * N/2 = K/2 * N
" Interesuje nas zależność czasu od liczby elementów
" Eliminujemy stałe zależne od szybkości komputera
Pawel@Kasprowski.pl Algorytmy i struktury danych
Notacja O()
Notacja O()
" Wzór (funkcja) określająca złożoność algorytmu
" Wstawianie do tablicy nieuporządkowanej
złożoność rzędu O(1)
" Wstawianie do tablicy uporządkowanej
" Wstawianie do tablicy uporządkowanej
złożoność rzędu O(N)
" Usuwanie z tablicy nieuporządkowanej
złożoność rzędu O(N)
" Usuwanie z tablicy uporządkowanej
złożoność rzędu O(N)
6
Pawel@Kasprowski.pl Algorytmy i struktury danych
Złożoność wyszukiwania
Złożoność wyszukiwania
" Wyszukiwanie liniowe w tablicy nieuporządkowanej
złożoność rzędu O(N)
" Wyszukiwanie binarne w tablicy uporządkowanej
złożoność rzędu O(log N)
złożoność rzędu O(log N)
" Przy dużych zbiorach róznica jest ogromna (tabelka!)
" Dla 1 000 000 000 (miliarda) elementów
wyszukiwanie liniowe: 500 000 000 porównań
wyszukiwanie binarne: 30 porównań!
Pawel@Kasprowski.pl Algorytmy i struktury danych
Wyszukiwanie binarne
Wyszukiwanie binarne
" Znacznie szybsze niż liniowe
" Problem: działa tylko dla tablicy uporządkowanej
(posortowanej)
" Co zrobić gdy tablica nie jest uporządkowania
" Co zrobić, gdy tablica nie jest uporządkowania
(posortowana)?
" Odpowiedz: posortować!
Pawel@Kasprowski.pl Algorytmy i struktury danych
Sortowanie tablicy
Sortowanie tablicy
" Na początku elementy tablicy są wstawione w
kolejności losowej:
12, 1, 345, 23, 4, 7, 889, 2, 3, 44
" Po posortowaniu powinny być w tablicy ułożone w
Po posortowaniu powinny być w tablicy ułożone w
kolejności rosnącej (lub malejącej):
1, 2, 3, 4, 7, 12, 23, 44, 345, 889
" Istnieje wiele algorytmów sortujących
" Różnią się przede wszystkim:
szybkością działania
prostotą kodu
7
Pawel@Kasprowski.pl Algorytmy i struktury danych
Sortowanie bąbelkowe
Sortowanie bąbelkowe
" Algorytm (jedno przejście od 1 do N)
Porównaj element z następnym
Jeśli następny jest mniejszy zamień je miejscami
Przesuń się o 1 w prawo i powtórz porównanie
Przesuń się o 1 w prawo i powtórz porównanie
" Niezmiennik
Po pierwszym przejściu (porównaniu każdego sąsiada z
każdym) na końcu tablicy znajduje się element największy
" Powtórz przejścia N razy
Następne przejście można już robić do przedostatniego
elementu!
Pawel@Kasprowski.pl Algorytmy i struktury danych
Sortowanie bąbelkowe
Sortowanie bąbelkowe
public void sortBubble() {
for(int j=nElem-1;j>=1;j--) // j ostatni do posortowania
for(int i=0; iif( bli [i] bli [i 1])
if(tablica[i]>tablica[i+1])
zamien(i,i+1);
}
Array.java
Pawel@Kasprowski.pl Algorytmy i struktury danych
Funkcja zamien
Funkcja zamien
void zamien(int a,int b) {
int pom = tablica[a]; // przechowaj a
tablica[a] = tablica[b]; // zapisz b
tablica[b] = pom; // zapisz a
bli [b] // i
}
Array.java
8
Pawel@Kasprowski.pl Algorytmy i struktury danych
Złożoność sortowania
Złożoność sortowania
bąbelkowego
bąbelkowego
" Liczba porównań:
w pierwszym przebiegu N-1, w następnym N-2 itd. aż do 1
(N-1)+(N-2)+(N-3)+...+1 = N*(N-1)/2
" Liczba zamian:
średnio dla połowy porównań: N*(N-1)/4
" Rzeczywista liczba zamian (w przeciwieństwie do
liczby porównań!) jest uzależniona od danych
zero zamian dla tablicy już posortowaniej
N*(N-1)/2 zamian dla tablicy posortowanej malejąco
" Złożoność sortowania: rzędu O(N2)
dla 100 elementów: 10 000 porównań
Pawel@Kasprowski.pl Algorytmy i struktury danych
Sortowanie przez wybór
Sortowanie przez wybór
" Algorytm
Znajdz najmniejszy element
Zamień go z pierwszym
Powtórz operację N 1 razy
Powtórz operację N-1razy
" Niezmiennik
po każdym przejściu na początku tablicy przybywa
elementów posortowanych
" i-te przejście można zaczynać od i-tego elementu
Pawel@Kasprowski.pl Algorytmy i struktury danych
Szukanie minimum w tablicy
Szukanie minimum w tablicy
public int znajdzMinimum() {
int min = 0;
for(int i=1; iif( bli [i] bli [ i ])
if(tablica[i]min = i; // znalezione minimum
return min; // zwraca indeks z tablicy!
}
9
Pawel@Kasprowski.pl Algorytmy i struktury danych
Sortowanie przez wybór
Sortowanie przez wybór
public void sortSelect() {
for(int j=0;jint min = j;
f (i i j 1 i El i )
for(int i=j+1; iif(tablica[i]min = i; // znalezione minimum
zamien(j,min); // zamiana minimum z aktualnym
}
}
Array.java
Pawel@Kasprowski.pl Algorytmy i struktury danych
Złożoność sortowania przez
Złożoność sortowania przez
wybór
wybór
" Liczba porównań
N*(N-1)/2
" Liczba zamian
po jednej zamianie w każdym przebiegu
po jednej zamianie w każdym przebiegu
a więc maksymalnie N
" Algorytm wykonuje tyle samo porównań co
sortowanie bąbelkowe
" Liczba zamian jest zwykle mniejsza (i to dużo)
Pawel@Kasprowski.pl Algorytmy i struktury danych
Sortowanie przez wstawianie
Sortowanie przez wstawianie
" Posortuj pierwsze dwa elementy
" Wstaw trzeci element na właściwe miejsce
na początek jeśli mniejszy od obydwu
w środek (na drugą pozycję) jeśli większy od jednego
w środek (na drugą pozycję) jeśli większy od jednego
na koniec (na swoim miejscu) jeśli większy od obu
" Powtórz wstawianie dla czwartego i kolejnych
elementów do N
" Niezmiennik:
na lewo od aktualnego elementy są posortowane względem
siebie
10
Pawel@Kasprowski.pl Algorytmy i struktury danych
Wstawienie elementu do tablicy
Wstawienie elementu do tablicy
posortowanej
posortowanej
" Kod podobny do funkcji wstaw(int klucz)
int i = nElem; // nElem koniec posortowanej tablicy
while(i>0 && tablica[i-1] > klucz) { // dopóki elementy
hil (i 0 && bli [i 1] kl ) { // d óki l
większe niż klucz
tablica[i] = tablica[i-1]; // przesuń w górę
i--;
}
tablica[i] = klucz; // wpisz nowy element w powstałą "dziurę"
Pawel@Kasprowski.pl Algorytmy i struktury danych
Sortowanie przez wstawianie
Sortowanie przez wstawianie
for(int j=1;jint i = j;
int klucz = tablica[j];
while(i>0 && tablica[i-1] > klucz) {
hil (i 0 && bli [i 1] kl ) {
tablica[i] = tablica[i-1]; // przesuń w górę
i--;
}
tablica[i] = klucz; // wpisz element w powstałą "dziurę"
}
Array.java
Pawel@Kasprowski.pl Algorytmy i struktury danych
Złożoność sortowania przez
Złożoność sortowania przez
wstawianie
wstawianie
" Liczba porównań
N*(N-1)/4
" Liczba kopiowań (nie zamian!)
N (N 1)/4
N*(N-1)/4
" Algorytm wykonuje średnio dwa razy mniej porównań
niż sortowanie bąbelkowe
" Kopiowania są szybsze niż zamiany
zamiana 3 podstawienia
kopiowanie 1 podstawienie
11
Pawel@Kasprowski.pl Algorytmy i struktury danych
Jak ulepszyć algorytm
Jak ulepszyć algorytm
" Algorytm sortowania przez wstawianie działa
zdecydowanie szybciej gdy dane są "prawie"
posortowane tzn. gdy są blisko swoich docelowych
miejsc
j
" Gdy element jest daleko swojego docelowego
miejsce (np. mały element na końcu tablicy),
konieczne jest przesunięcie wielu rekordów
" Najlepiej byłoby najpierw "trochę" posortować dane
Pawel@Kasprowski.pl Algorytmy i struktury danych
Algorytm Shellsort
Algorytm Shellsort
" Wynalazca - Donald L. Shell (1959)
" Bazuje na sortowaniu przez wstawianie
" Najpierw sortuje elementy oddalone od siebie o h
" Stała h zmniejsza się aż do wartości 1
S ł h i j i d ś i 1
" Zwykle wartości h wyznacza się wg wzoru:
hn+1 = 3 * hn +1
Pawel@Kasprowski.pl Algorytmy i struktury danych
Algorytm Shellsort
Algorytm Shellsort
int h = 1; // przygotowanie pierwszego h
while(h <= nElem/3) h = h*3 + 1;
while(h>0) { // zmniejszaj h, aż do momentu gdy h=1
for(int j=h; jint temp = tablica[j]; // sortowanie o skoku h
i = j;
while(i > h-1 && tablica[i-h] >= temp) {
tablica[i] = tablica[i-h];
i = i - h;
}
tablica[i] = temp;
}
h = (h-1) / 3; // zmniejsz wartość h
Array.java
}
12
Pawel@Kasprowski.pl Algorytmy i struktury danych
Algorytm Shellsort
Algorytm Shellsort
int h = 1; // przygotowanie pierwszego h
while(h <= nElem/3) h = h*3 + 1;
while(h>0) { // zmniejszaj h, aż do momentu gdy h=1
for(int j=h; jint temp = tablica[j]; // sortowanie o skoku h
i = j;
while(i > h-1 && tablica[i-h] >= temp) {
tablica[i] = tablica[i-h];
i = i - h;
}
tablica[i] = temp;
}
h = (h-1) / 3; // zmniejsz wartość h
}
Pawel@Kasprowski.pl Algorytmy i struktury danych
Złożoność Shellsort
Złożoność Shellsort
" Nie obliczono tego teoretycznie
" W praktyce od O(n3/2) do O(n7/6)
elementów bąbelkowe shellmax shellmin
2432
10 100 32 15
20 400 89 33
100 10.000 1000 215
1000 1.000.000 31.623 3.162
10.000 100.000.000 1.000.000 46.416
Pawel@Kasprowski.pl Algorytmy i struktury danych
Podsumowanie
Podsumowanie
" Sortowanie bąbelkowe
najprostsze, najwolniejsze O(n2)
" Sortowanie przez wybór
szybsze ale także O(n2)
szybsze ale takżeO(n2)
" Sortowanie przez wstawianie
najlepsze z rzędu O(n2)
" Sortowanie Shella
bardzo szybkie - rzędu O(n3/2)
Są lepsze metody! poznamy je na następnym wykładzie
13
Pawel@Kasprowski.pl Algorytmy i struktury danych
Dziękuję za uwagę
Dziękuję za uwagę
Do zobaczenia...
materiały dostępne pod adresem:
www.kasprowski.pl
14
Wyszukiwarka
Podobne podstrony:
MB w2
ALG GEOM
zj w2
w2 2
SD przykłady do w2
23 eng alg
moje genetyczny alg
DROGI w2 w3 tyczenie
w2
W2?
metody numeryczne i w2
W2
W2 Opadanie czastek cial stalych w plynach
Alg S1
NB NST 10 W2 KORA MOZGOWA,?ekty uszkodzen
DROGI w2 w2 tyczenie
admin w2
więcej podobnych podstron