POLITECHNIKA WARSZAWSKA
POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA KOMPUTERÓW
ZASADY PROGRAMOWANIA KOMPUTERÓW
Język programowania: C/C++
Język programowania: C/C++
Środowisko programistyczne: Builder C++ 6
Środowisko programistyczne: Builder C++ 6
Wykład 5 : Napisy. Algorytmy sortowania. Tablice
Wykład 5 : Napisy. Algorytmy sortowania. Tablice
dwuwymiarowe.
dwuwymiarowe.
Napisy (łańcuchy) i operacje na nich
Napisy (łańcuchy) i operacje na nich
A
ańcuchy definiuje się jako zmienne umownego typu (klasy) string. Aby
używać łańcuchów, należy dołączyć plik nagłówkowy .
" Do znaków w łańcuchu odwołujemy się jak do elementów tablicy, poprzez
indeksy, zaczynając od 0.
" Rozmiar łańcucha (liczbę znaków) można wyznaczyć za pomocą funkcji
size( ) lub (starszej) funkcji length( ). UWAGA: funkcje te nie mają
parametrów.
" A
ańcuchy można ze sobą łączyć za pomocą operatora +
3
2 4
1
0
#include  W  K
 I  T  E
string imie;
imie[0]
...
imie[4]
imie = "WITEK";
imie[1]
cout << imie[0]; // pierwszy znak imienia
cout << imie [imie.size( )-1]; // ostatni znak imienia
imie.size( ) jest tu równe 5
#include
...
string imie = "WITEK";
dwa sposoby inicjowania łańcuchów
string mama ("ASIA");
Algorytmy prostego sortowania
Algorytmy prostego sortowania
Algorytm 1  sortowanie przez wybieranie ( selection sort )
Algorytm 2  sortowanie przez wstawianie ( insertion sort )
Algorytm 3  sortowanie przez zamianę ( bubble sort )
UWAGA:
Algorytmy - celem porównania - zostaną zaprezentowane przy
założeniu, że sortujemy elementy o indeksach od 1 do n w tablicy
a[n+1]; element a[0] nie bierze udziału w sortowaniu, z wyjątkiem
algorytmu 2, gdzie pełni rolę pomocniczą.
4
7 3 6 9 5
1 2 ...
n
W typowych sytuacjach sortujemy wszystkie elementy w tablicy
a[n], o indeksach od 0 do n-1, i wówczas zaprezentowane
algorytmy muszą być odpowiednio zmodyfikowane.
Należy na to uważać !!!
4
7 3 6 9 5
...
0 1
n-1
Algorytm 1  sortowanie przez wybieranie ( selection sort )
Algorytm 1  sortowanie przez wybieranie ( selection sort )
Pierwszy krok iteracyjny:
for (i = 1; i< n; i++) {
" wybieramy element najmniejszy (znajdujemy indeks)
i_min = i;
" zamieniamy go z pierwszym elementem
Kolejne kroki:
for (j = i+1; j <= n; j++)
" z nieposortowanych elementów wybieramy element
if (a[ j ] < a[ i_min ])
najmniejszy
i_min = j;
" zamieniamy go z pierwszym elementem z ciągu
nieposortowanych elementów - odtąd będzie należał do
temp = a[ i ];
posortowanych
a[ i ] = a[ i_min ];
a[ i_min ] = temp;
" Ostatni krok to ewentualna zamiana ostatniego
elementu z przedostatnim
}
0 8 6
-3 -1 2 4 5 9 10 6 7
Sortujemy elementy o indeksach
... n
...
od 1 do n w tablicy a[n+1]; a[0] - 1 2 3
nie bierze udziału w sortowaniu
2 8 10
0 9 7
-3 -1 3 4 5
6
nieposortowane
posortowane
Algorytm 1  animacja
Algorytm 1  animacja
for (i = 1; i< n; i++) {
i_min = i;
for (j = i+1; j <= n; j++)
if (a[ j ] < a[ i_min ])
i_min = j;
temp = a[ i ];
a[ i ] = a[ i_min ];
a[ i_min ] = temp;
}
Sortujemy elementy o indeksach
od 1 do n w tablicy a[n+1]; a[0] -
nie bierze udziału w sortowaniu
Uwaga: tę animację najlepiej odtwarzać metodą krok po kroku.
Algorytm 2  sortowanie przez wstawianie ( insertion sort )
Algorytm 2  sortowanie przez wstawianie ( insertion sort )
" bierzemy pierwszy element z części
for (i = 1; i<=n; i++ ) {
nieposortowanej
j = i;
" porównujemy go kolejno z elementami
posortowanymi, idąc na lewo
temp = a[j];
" dopóki jest mniejszy od kolejnego
while (j>1 && temp < a[j-1]) {
elementu z grupy posortowanych,
a[ j ] = a[ j-1 ] ;
przesuwamy ten element w prawo
j=j-1 ;
" jeśli nie jest już mniejszy - wstawiamy
go na zwolnione miejsce (albo na
}
początek, jeśli inaczej się nie da)
a[ j ] = temp;
}
// 1..j-1 - posortowane
// j..n - nieposortowane
4 8
0 3 6 9 12 5 10 2 7
... n
...
1 2 3
Sortujemy elementy o indeksach
8 10
4 2 7
0 3 5 6 9
od 1 do n w tablicy a[n+1]; a[0] - 12
nie bierze udziału w sortowaniu
nieposortowane
posortowane
Algorytm 2a - wersja z wartownikiem
Algorytm 2a - wersja z wartownikiem
for (i = 1; i<=n; i++ ) {
" bierzemy pierwszy element z części
nieposortowanej
j = i;
" wstawiamy go jako wartownika do
temp = a[ j ];
 zerowego elementu
a[0] = temp;
" porównujemy go kolejno z elementami
while (temp < a[ j-1]) {
posortowanymi, idąc na lewo
a[ j ] = a[ j-1 ] ;
" dopóki jest mniejszy od kolejnego
elementu z grupy posortowanych,
j=j-1;
przesuwamy ten element w prawo
}
" jeśli nie jest już mniejszy - wstawiamy
a[ j ] = temp;
go na zwolnione miejsce.
}
wartownik
// 1..j-1 - posortowane
4 8
5 0 3 6 9 12 5 10 2 7
// j..n- nieposortowane
// a[0] - wartownik
8 10
2 7
5 4 5 6 9
0 3
12
... n
...
2
0 1
Sortujemy elementy o
nieposortowane
indeksach od 1 do n w tablicy
posortowane
a[n+1]; a[0] - pełni rolę
pomocniczą (wartownika)
Algorytm 3  sortowanie przez zamianę (tzw. bąbelkowe)
Algorytm 3  sortowanie przez zamianę (tzw. bąbelkowe)
bool byla_zamiana;
for (i = n; i>1; i--) {
Sortujemy elementy
o indeksach od 1 do
....
for (j = 1; j < i; j++)
n w tablicy a[n+1];
i=n;
if (a[ j ] > a[ j+1 ]) {
a[0] - nie bierze
udziału w sortowaniu
do {
temp = a[ j ];
była_zamiana=false;
a[ j ] = a[ j+1];
for (j = 1; j a[ j+1] = temp;
8
5 10 2 7
if (a[ j ] > a[ j+1 ]) {
}
8
5 2 7 10 temp = a[ j ];
}
a[ j ] = a[ j+1];
Pierwszy krok iteracyjny:
a[ j+1] = temp;
" zamieniamy dwa sąsiednie elementy, jeśli pierwszy
z nich jest większy od drugiego
była_zamiana=true;
" taką zamianę wykonujemy idąc po kolei wzdłuż całej
}
tablicy, od 1 do i=n
i -- ;
" w efekcie tego największy element znajdzie się na
końcu tablicy - jako a[n]
} while (byla_zamiana);
Kolejne kroki:
Wersja bardziej efektywna - przejście przez
" takie same zamiany sąsiadów wykonujemy w
tablicę i zamianę sąsiadów powtarzamy
obszarze od 1 do i, gdzie i maleje od n-1 aż do 2 -
tylko wtedy, jeśli w poprzednim
kolejny największy element znajdzie się w a[i]
kroku była choć jedna taka zamiana.
Porównanie algorytmów prostego sortowania
Porównanie algorytmów prostego sortowania
" Porównując metody sortowania analizuje się liczbę porównań elementów i liczbę
ich przesunięć w tablicy. Należy też uwzględnić przypadki najlepsze (tablica
posortowana lub prawie posortowana) i najgorsze (posortowana w kolejności
odwrotnej).
" Sortowanie przez zamianę (nawet w wersji ulepszonej) jest gorsze zarówno od
metody sortowania przez wstawianie, jak i od metody sortowania przez wybieranie.
Algorytm sortowania przez zamianę jest bardzo wrażliwy na konfiguracje danych i
tylko w przypadku elementów prawie posortowanych ma przewagę nad pozostałymi
metodami.
" Algorytm prostego wybierania jest przeważnie lepszy od prostego wstawiania
(które wymaga przesuwania elementów w tablicy) i tylko w przypadku elementów
prawie posortowanych proste wstawianie jest od niego nieco szybsze.
" Jednakże wszystkie zaprezentowane algorytmy prostego sortowania mają
złożoność obliczeniową O(n2), co można czytać jako  proporcjonalne do n2  , czyli
w przypadku b. dużych wartości n algorytmy te są mało efektywne.
UWAGA: zarówno 10n2 +100n, jak i n2/30 są rzędu O(n2).
" Metody szybkie, o mniejszej złożoności, konieczne do zastosowania w przypadku
wielkich wartości n, wymagają zastosowania zaawansowanych algorytmów (np.
algorytmu quicksort) lub zaawansowanych struktur danych (np. drzew binarnych).
" Dla małych i średnich wartości n algorytmy prostego sortowania są natomiast
całkowicie wystarczające, a wybierając któryś z nich należy przede wszystkim
kierować się czytelnością kodu i łatwością jego użycia.
Tablice dwuwymiarowe
Tablice dwuwymiarowe
Definicja TABLICY
typ_elementów nazwa_tablicy [ilosc_wierszy] [ilosc_kolumn] ;
lub:
typ_elementów nazwa_tablicy [ilosc_wierszy] [ilosc_kolumn] =
{...,...,..., ,...}; // inicjalizacja tablicy
wartości początkowe
Wartości początkowe w przypadku inicjalizacji tablicy wstawiane są do
kolejnych wierszy tablicy.
kolumny
Przykłady:
const n=4; const w=5; const k=7;
char Z[w] [k]; // tablica o nazwie Z i w wierszach oraz k
// kolumnach
int A[n] [n]= { 12,9,47,48,17,8,39,8,48,46,18,20,8,18,3,21 };
// tablica kwadratowa o n wierszach i n kolumnach
// - zobacz obok efekt inicjalizacji
Uwaga: wiersze i kolumny tablic dwuwymiarowych
wiersze
też numerowane są (indeksowane) od zera.
Tablice dwuwymiarowe - wczytywanie
Tablice dwuwymiarowe - wczytywanie
Przykład wczytywania danych do tablicy - wierszami
const int w=4, k=4;
int A[w][k]; // definicja tablicy A
...
...
for (int i = 0; i < w; i++) // dla każdego wiersza tablicy
for (int j = 0; j < k; j++) // przejdz
przez wszystkie kolumny
cin >> A[i] [j]; // wczytaj element o indeksach i, j
...
Tablice kwadratowe
Tablice kwadratowe
UWAGA: po przekątnych (a także po pojedynczych wierszach i kolumnach)
poruszamy się w pętli pojedynczej (!).
Przykład:
Zerujemy elementy głównej przekątnej: Zerujemy elementy drugiej przekątnej:
for (int i = 0; i < n; i++) for (int i = 0; i < n; i++)
A[i][i] =0; A[i][n-1-i] =0;
Tablica kwadratowa  wypełnianie nad główną przekątną
Tablica kwadratowa  wypełnianie nad główną przekątną
Pod i nad przekątnymi poruszamy się w pętli podwójnej, w której
zmienna sterująca pętli wewnętrznej zmienia się w sposób zależny od
wartości zmiennej sterującej pętli zewnętrznej ( j jest zależne od i ).
Generowanie liczb losowych
Generowanie liczb losowych
rand ( ) - funkcja standardowa bez parametrów, generuje liczbę losową
całkowitą o rozkładzie jednostajnym z przedziału <0, RAND_MAX),
gdzie RAND_MAX typu int jest stałą (zdefiniowaną w bibliotece cstdlib) (i równą 32767 w BC++6.0)
Jak używać funkcji rand( )
#include // plik nagłówkowy, który trzeba dołączyć
....
// instrukcja srand inicjuje generator liczb losowych wartością przypadkową,
// otrzymaną z zegara systemowego (jest to tzw. zarodek liczb losowych)
// dzięki temu za każdym razem program losuje inne liczby:
srand (time(0));
cout << rand( ); // generuje liczbę losową całkowitą z przedziału <0, RAND_MAX)
cout << rand( ) / double(RAND_MAX); // generuje liczbę losową double z przedziału <0, 1)
cout << A+(B-A)*(rand( )) / double(RAND_MAX); // generuje liczbę losową double z przedziału // Prościej jest użyć funkcji modulo, choć nie zapewnia to rozkładu w pełni jednostajnego:
cout << rand( )%100; // generuje liczbę losową całkowitą z przedziału <0, 100)
cout << A+ rand( )%(B-A); // generuje liczbę losową całkowitą z przedziału