Wskaż algorytm sortowania, który nie jest stabilny?

Wyjaśnienie

Sortowanie szybkie (Quick Sort) to algorytm, który faktycznie nie jest stabilny w swojej podstawowej wersji. To znaczy, jeśli w kolekcji są dwa identyczne elementy pod względem klucza sortowania, po wykonaniu Quick Sort ich kolejność względem siebie może się zmienić. Z moich doświadczeń wynika, że to może mieć znaczenie, na przykład gdy sortujemy obiekty według jednego pola, ale chcemy zachować kolejność według innego – czasem w praktyce, np. przy obsłudze rekordów w bazach danych, stabilność sortowania gwarantuje spójność wyników. Quick Sort jest jednak bardzo popularny, bo ogólnie działa bardzo szybko i jest efektywny pamięciowo, stąd często go się używa tam, gdzie stabilność nie jest wymagana. W niektórych implementacjach można próbować uczynić Quick Sort stabilnym, ale wymaga to dodatkowych zabiegów i nie jest standardem – biblioteki standardowe (np. C++ std::sort) właśnie z tego powodu nie gwarantują stabilności Quick Sorta. W praktycznych projektach, jeśli zależy Ci na stabilności, lepiej użyć sortowania przez wstawianie lub przez zliczanie. Sortowanie bąbelkowe i przez wstawianie są wręcz typowe do nauki stabilnych algorytmów, a sortowanie przez zliczanie nawet dla dużych zbiorów cały czas pilnuje kolejności równych elementów. Quick Sort jest świetny, ale warto znać jego ograniczenia, szczególnie w aplikacjach biznesowych albo pracy z dużymi, złożonymi strukturami danych.