Sortowanie - definicja, wymagania, złożoność, sposób porównywania elementów
Sortowanie - definicja
Czym jest sortowanie? Otóż sortowanie polega na uporządkowaniu pewnej grupy elementów względem danego kryterium. Kryterium tym może być np. wielkość (przy sortowaniu liczb), kolejność słownikowa (w przypadku sortowania ciągu znaków), wielkość pliku (przy sortowaniu plików).
Sortowanie jest bardzo ważną operacją zarówno w algorytmice, jak i przy codziennym użytkowaniu komputera. Wielu użytkowników komputera nawet nie zdaje sobie sprawy jak często korzysta się z algorytmu sortowania, aby ułatwić im życie.
Sortowanie - używasz tego na co dzień
Najprawdopodobniej używasz systemu operacyjnego z wbudowanym środowiskiem graficznym (windows, x-window w linux). Jeśli w jakimś folderze znajduje się bardzo wiele elementów, a Ty akurat chcesz coś znaleźć, co zazwyczaj robisz? Najprawdopodobniej wybierasz opcję rozmieść ikony i wybierasz kryterium np. według nazwy. Czy wiesz, że wybierając taką opcję, ikony są właśnie sortowane wg. nazwy?
Gdy przeglądasz różne dane tabelaryczne, np. notowania giełdowe, najczęściej masz możliwość ustawienia danych wg. pewnych kryterium. Możesz np. sprawdzić opłacalność pewnych akcji w przeciągu ostatnich 3,6 czy 12 miesięcy. Czy wiesz, że klikając w odpowiednie miejsce i ustawiając dane w zadanej przez Ciebie kolejności, znowu jest wykorzystywany algorytm sortowania?
Innym przykładem niech będzie zwykła wyszukiwarka internetowa. Jestem przekonany, że bardzo często używasz takiej wyszukiwarki, aby szybko odnaleźć informacje na interesujący Cię temat. Nie wiem czy wiesz, ale wyświetlone strony są przedstawione w określonym porządku. W niektórych serwisach nawet przy każdej wyświetlonej linii pisze np. "Trafność 80%". Najpierw we wszystkich stronach jest wyszukiwany podany przez Ciebie ciąg znaków, a następnie strony są właśnie sortowane względem trafności.
Korzystając z różnego typu baz danych w firmach, bez sortowania również ciężko by sobie było wyobrazić pracę. Podobnie, korzystają np. z książki adresowej, wyszukiwania w systemie operacyjnym, pośród wielu wpisów, znacznie łatwiej nam odnaleźć daną informację, jeśli informacje są w jakiś sposób ułożone.
Wszystkie te przykłady przytaczam tutaj, aby podkreślić, że sortowanie nie jest jakąś wymyśloną operacją, która jest sztuką dla sztuki. Wręcz przeciwnie - bez sortowania ciężko by nam było korzystać z zasobów komputera w dzisiejszych czasach, w czasach wręcz natłoku nowych informacji. Dlatego warto przyjrzeć się bliżej sortowaniu i poznać jego jak najbardziej efektywne metody.
