POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA STRUKTURALNEGO
(ZAP  zima 2013)
Język programowania: C/C++
Środowisko programistyczne: Qt
Wykład 3 : Tablice jednowymiarowe. Sortowanie.
Przykład pętli for  szukanie elementu największego w ciągu n liczb
2
int a, i, max, n; // max - element aktualnie największy, n  ilość elementów ciągu
cin >> n; // wczytanie ilości elementów
cin >> max; // początkowa wartość max - wartość pierwszego wczytanego elementu
for (i=2; i<=n; i++) { // w tej pętli wczytamy pozostałe n-1 liczb
cin >> a;
if ( a > max) max = a;
}
if (n>0) // jeśli był co najmniej jeden element ciągu
cout << max << endl; // drukowanie wartości maksymalnej
else
cout <<  ciag pusty  ;
// dla porównania  szukanie elementu największego w ciągu liczb niezerowych
zakończonych zerem (zero kończące nie należy do ciągu)
int a, max; // max - element aktualnie największy
cin >> a; // wczytanie pierwszej liczby - przed pętlą
max = a; // początkowa wartość max - wartość pierwszego elementu
while (a != 0) { // w tej pętli wczytamy pozostałe liczby
if ( a > max) max = a;
cin >> a;
}
if (max == 0) // jeśli pierwszy element był zerem
cout <<  nie było liczb niezerowych ;
else
cout << max << endl; // drukowanie wartości maksymalnej
3
Dygresja: porównanie a przypisanie - niebezpieczne pułapki
Nie wolno mylić operatorów porównania i przypisania:
= operator przypisania (wykonaj podstawienie)
== operator porównania (sprawdz
warunek równości)
Przykład:
x = 10 ; // instrukcja - przypisz wartość 10 zmiennej x (podstaw 10 pod x )
x = 10 // wyrażenie - ma wartość wyrażenia po prawej stronie znaku = ,
// czyli 10 (albo true - zależnie od kontekstu)
x = = 10 // wyrażenie - ma wartość true, jeśli x jest równe 10
Zatem UWAGA: załóżmy, że chcemy napisać instrukcję warunkową postaci:
jeśli x jest równe 10, to zrób coś tam...
if (x = =10) .... // zapis poprawny - instrukcja za nawiasem wykona się tylko
// wtedy, gdy x będzie równe 10
if (x = 10) ... // tu jest błąd - instrukcja za nawiasem wykona się zawsze,
// bo wyrażenie w nawiasie ma wartość true,
// taki bląd NIE B
DZIE jednak SYGNALIZOWANY !
4
Instrukcje przerywające wykonanie pętli
" Instrukcja break - przerywa działanie pętli (for, do, while), powoduje przejście
do pierwszej instrukcji znajdującej się za pętlą;
" Instrukcja continue - przerywa bieżącą iterację pętli (for, do, while), powoduje
przejście do następnego cyklu pętli.
do { do {
... ...
if (& ) break; if (& ) continue;
.... ....
} }
while (...); while (...);
..... .....
UWAGA: użycie break i continue nie jest zalecane, lepiej używać odpowiednich instrukcji if-else
wewnątrz pętli, chyba że jest to znacznie mniej czytelne.
5
Instrukcja goto
(do użytku tylko w wyjątkowych przypadkach !!!)
" Jeżeli wykonamy break w pętli umieszczonej wewnątrz innej pętli, to przerwiemy
działanie pętli wewnętrznej, ale pętla zewnętrzna będzie wykonywać się nadal.
" Jeśli więc musimy z pętli zagnieżdżonej wydostać się całkowicie  na zewnątrz ,
uzasadnione jest użycie instrukcji skoku goto (i tylko w takich przypadkach !). W
żadnym razie nie wolno instrukcji goto używać do zorganizowania pętli skacząc
wstecz.
for (. . . ) {
...
for (& ) {
...
if (& ) goto etykieta;
....
}
};
etykieta: .....
etykieta - dowolna nazwa, po niej musi być dwukropek.
6
Tablice jednowymiarowe (inaczej: wektory)
TABLICE pozwalają za pomocą jednej nazwy zapamiętać wiele elementów tego
samego typu.
Elementy przechowywane są jeden za drugim w pamięci komputera:
i rozróżniane za pomocą indeksów:
3
2 4
1
0
indeks
2
1 -3
7
12
zmienna indeksowana
a[0]
a[4]
a[1]
...
(element tablicy)
" Indeksowanie tablic zaczyna się zawsze od zera
" Indeks musi być wyrażeniem, które ma nieujemną wartość
całkowitą.
7
Tablice jednowymiarowe - definicje
Definicja TABLICY
typ_elementów nazwa_tablicy [rozmiar_tablicy ];
lub:
typ_elementów nazwa_tablicy [rozmiar_tablicy ]= {...,...,..., ,...};
można pominąć wartości początkowe
rozmiar_tablicy - ilość elementów - liczba, albo (lepiej!) stała całkowita
albo (ogólnie) wyrażenie o wartości nieujemnej (inaczej program się nie
skompiluje) dającej się policzyć na etapie kompilacji.
Przykłady:
const int N = 4; const int W = 5;
int a[N]; // tablica o nazwie a i N elementach całkowitych
// ostatni element ma więc indeks = N-1
char b[10]; // tablica o nazwie b i 10 elementach typu char; ostatni to b[9]
string naz[2*N-1]; // tablica o nazwie naz i 2*N-1 elementach typu string
int a[5] = { 2, 7, 1, -3, 12 }; // tablica o nazwie a i 5 elementach o podanych wartościach
char z[ ]= {'a', 'd', '?' , 'X', 'q', '!' }; // tablica z typu char o podanych wartościach
8
Tablice jednowymiarowe - odwołania
ELEMENT tablicy ( zmienna indeksowana )
nazwa_tablicy [ indeks]
Indeks musi być wyrażeniem, które ma nieujemną wartość
całkowitą, mniejszą (!) od rozmiaru tablicy.
const int N=4; const int W=5;
char z[N]; char p;
...
cout << z[0]; // wydrukuj pierwszy element tablicy z
p = z[1]; // podstaw drugi element tablicy z pod p
cout << z[N] // błąd (!) - nie ma elementu o indeksie=N
cout << z[N-1] // wydrukuj ostatni element tablicy z
UWAGA: Błąd przekroczenia zakresu tablicy nie jest sygnalizowany, co
może prowadzić do nieprzewidzianych skutków!
9
Przykład 1  szukanie elementu największego w tablicy
const N=10;
int a [N], i , max; // max - element aktualnie największy w tablicy a[N]
for (i=0; i cin >> a[i]; // wczytywanie danych do tablicy;
...
max = a[0]; // początkowa wartość max - wartość pierwszego elementu
for (i=1; i if (a[i] >max)
max =a[i];
cout << max << endl; // drukowanie wartości maksymalnej
// wersja bardziej ogólna - znajdziemy dodatkowo położenie elementu maksymalnego
const N=10;
int a [N], i , imax; // imax - indeks elementu aktualnie największego w tablicy a[N]
for (i=0; i cin >> a[i]; // wczytywanie danych do tablicy;
...
imax = 0; // początkowa wartość imax - indeks pierwszego elementu
for (i=1; i if ( a[i] > a[imax])
imax = i; // UWAGA: zmienna max wcale nie jest nam potrzebna
cout << a[imax] << endl; // drukowanie wartości maksymalnej
cout << imax << endl; // drukowanie indeksu elementu maksymalnego
// (lub indeksu pierwszego znalezionego elementu maksymalnego, jeśli jest ich kilka)
10
Przykład 2  przesunięcie cykliczne wektora w prawo
11
Algorytmy prostego sortowania
Algorytm 1  sortowanie przez wybieranie ( selection sort )
Algorytm 2  sortowanie przez wstawianie ( insertion sort )
Algorytm 3  sortowanie przez zamianę ( bubble sort )
4
7 3 6 9 5
...
0 1
N-1
12
Algorytm 1  sortowanie przez wybieranie ( selection sort )
Algorytm:
for (i = 0; i< N-1; i++) {
" z nieposortowanych elementów wybieramy element
najmniejszy (zapamiętujemy jego położenie)
i_min = i;
" zamieniamy go z pierwszym elementem z ciągu
for (j = i+1; j < N; j++)
nieposortowanych elementów - odtąd będzie należał do
posortowanych
if (a[ j ] < a[ i_min ])
Zatem:
i_min = j;
" W pierwszym kroku element najmniejszy w tablicy
temp = a[ i ];
zamieniamy z pierwszym
a[ i ] = a[ i_min ]; " Ostatni krok to ewentualna zamiana ostatniego
elementu z przedostatnim
a[ i_min ] = temp;
}
// 0..i-1  posortowane
// i..N-1 - nieposortowane
10
0 8 6
-3 -1 2 4 5 9 6 7
... N-1
...
0 1 2
2 8
0 9 7
-3 -1 3 4 5 10
6
nieposortowane
posortowane
13
Algorytm 2  sortowanie przez wstawianie ( insertion sort )
" bierzemy pierwszy element z części
for (i = 0; inieposortowanej
j = i;
" porównujemy go kolejno z elementami
posortowanymi, idąc na lewo
temp = a[j];
" dopóki jest mniejszy od kolejnego
while (j>0 && 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;
}
// 0..i-1 - posortowane
// i..N-1 - nieposortowane
4 8 10
0 3 6 9 12 5 2 7
...
... N-1
0 1 2
8 10
4 2 7
0 3 5 6 9
12
nieposortowane
posortowane
14
Algorytm 3  sortowanie przez zamianę (tzw. bąbelkowe)
bool byla_zamiana=true;
for (i = N-1; i>0; i--) {
i=N-1;
for (j = 0; j < i; j++)
while (byla_zamiana) {
if (a[ j ] > a[ j+1 ]) {
była_zamiana=false;
temp = a[ j ];
for (j = 0; j a[ j ] = a[ j+1];
if (a[ j ] > a[ j+1 ]) {
a[ j+1] = temp;
10
8
5 2 7
temp = a[ j ];
}
8
a[ j ] = a[ j+1];
5 2 7 10
}
a[ j+1] = temp;
Pierwszy przebieg :
była_zamiana=true;
" zamieniamy miejscami dwa pierwsze elementy, jeśli
pierwszy z nich jest większy od drugiego
}
" taką samą zamianę sąsiednich elementów wykonujemy
i=i-1 ;
idąc po kolei wzdłuż całej tablicy, od 0 do N-1 (for j)
}
" w efekcie tego największy element znajdzie się na końcu
tablicy - jako a[N-1]
Wersja bardziej efektywna - przejście przez
Kolejne przebiegi:
tablicę i zamianę sąsiadów powtarzamy
tylko wtedy, jeśli w poprzednim
" takie same zamiany sąsiadów wykonujemy w obszarze
kroku była choć jedna taka zamiana.
od 0 do i, gdzie i maleje od N-1 aż do 1 (pętla for i) -
kolejny największy element znajdzie się w a[i]
15
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ą wykorzystania 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.