5672969465

4.2. PROSTE ALGORYTMY SORTOWANIA TABLIC 10

Przykład. Funkcja wyznaczająca sumę wartości elementów z podanej tablicy.

double suma(double const* t, int n)

{    // dostęp do elementów t tylko do odczytu

assert(n > 0) ; double s = 0.0; for (int i=0; i<n; ++i) s += t [i] ; return s;

>

int main(void)

{

int ile = 10;

double* punkty = new double[ile]; for (int i=0; i<ile; ++i) cin >> punkty[i];

cout << suma (punkty, ile); // przekazanie tablicy do funkcji delete [] punkty; return 0;

}

Na marginesie, zauważmy, że funkcja suma O nie ma żadnych efektów ubocznych. Nie wypisuje nic na ekran ani o nic nie pyta się użytkownika. Wyznacza tylko wartość sumy elementów zawartych w tablicy — czyli tylko to, czego użytkownik (funkcja mainO) może się po niej spodziewać.

Ponadto zapis double const* zapewnia, że elementów danej tablicy nie można zmieniać. Jest to tzw. wskaźnik na wartości stałe.    ■

4.2. Proste algorytmy sortowania tablic

Rozważymy teraz problem sortowania tablic jednowymiarowych, który jest istotny w wielu zastosowaniach, zarówno teoretycznych jak i praktycznych. Dzięki odpowiedniemu uporządkowaniu elementów niektóre algorytmy (np. wyszukiwania) mogą działać szybciej, mogą być prostsze w napisaniu czy też można łatwiej formalnie udowodnić ich poprawność.

Wyobraź sobie, ile czasu zajęłoby Ci znalezienie hasła w słowniku (chodzi oczywiście o słownik książkowy), gdyby redaktorzy przyjęliby losową kolejność wyrazów. Przeanalizuj z jakiego „algorytmu” korzystasz wyszukując to, co Cię interesuje.

Co więcej, istnieje wcale niemało zagadnień, które wprost wymagają pewnego uporządkowania danych i które bez takiej operacji wcale nie mają sensu.

Przykładowo, rozważmy w jaki sposób wyszukujemy interesujące nas strony internetowe. Większość wyszukiwarek działa w następujący sposób.

Ostatnia aktualizacja: 5 grudnia 2012 r.