Zalety i wady sortowania bąbelkowego

Programiści, którzy przechodzą od rozwoju komputerów i stron internetowych do kodowania dla urządzeń mobilnych lub systemów wbudowanych, odkrywają, że więcej czasu spędza się na wybieraniu i kodowaniu własnych struktur danych i algorytmów. Przy mniejszej ilości pamięci i ograniczonej pamięci masowej, nie ma miejsca na gotowe biblioteki i frameworki. Tak więc dla tych, którzy muszą napisać własne procedury sortowania, oto kilka uwag na temat wyboru sortowania bąbelkowego.

Tło

Sortowanie bąbelkowe jest prostym algorytmem, który sortuje listę elementów w pamięci. Biorąc pod uwagę tablicę, kod wielokrotnie porównuje każdą parę sąsiednich elementów i zamienia je, jeśli nie są w kolejności. Proces powtarza się aż do momentu, gdy nie wystąpią już żadne zamiany. Gdyby możliwe było oglądanie tablicy w trakcie sortowania, niskie wartości "bąbelkowałyby" na górze, podczas gdy duże wartości opadałyby na dół. Oto odpowiedni kod w Visual Basic 2010:

• Sortowanie bąbelkowe jest prostym algorytmem, który sortuje listę elementów w pamięci.
  
• Gdyby można było przeglądać tablicę w trakcie sortowania, niskie wartości "bąbelkowałyby" na górze, podczas gdy duże wartości opadałyby na dół.

While swap = True

swap = False

For I = 0 To tbl.length - 2

 If tbl(i) > tbl(I + 1) Then tmp = tbl(i) tbl(I) = tbl(I + 1) tbl(I + 1) = tmp swap = True End If 

Next

End While

When to Choose the Bubble Sort

Algorytm ten ma kilka zalet. Jest prosty do napisania, łatwy do zrozumienia i zajmuje tylko kilka linii kodu. Dane są sortowane w miejscu, więc nie ma dużego narzutu na pamięć, a po posortowaniu dane są w pamięci, gotowe do przetwarzania. Główną wadą jest ilość czasu potrzebnego do sortowania. Średni czas wzrasta prawie wykładniczo wraz ze wzrostem liczby elementów tabeli. Dziesięciokrotnie większa liczba elementów sprawia, że sortowanie trwa prawie sto razy dłużej.

• Algorytm ten ma kilka zalet.
  
• Średni czas rośnie niemal wykładniczo wraz ze wzrostem liczby elementów tablicy.

Inne sortowanie tablic

Algorytmy sortowania różnią się złożonością, szybkością i narzutem. Sortowanie bąbelkowe jest najmniej złożone, ale także jednym z najwolniejszych. Inne sortowania oparte na tablicach, takie jak insertion sort i exchange sort są nieco szybsze, ale wymagają więcej kodu (patrz referencje poniżej). Główną zaletą sortowania opartego na tablicach jest to, że używają najmniej kodu i zajmują najmniejszą ilość pamięci roboczej. Rozważmy te sortowania dla prostych tablic z mniej niż kilkuset elementami.

• Algorytmy sortowania różnią się złożonością, szybkością i narzutem.
  
• Inne sortowania oparte na tablicach, takie jak sortowanie przez wstawianie i sortowanie przez zamianę, są nieco szybsze, ale wymagają więcej kodu (zobacz odnośniki poniżej).

Złożone algorytmy sortowania

Większe zbiory danych wymagają bardziej złożonego kodu i więcej pamięci. Szybkie sortowanie i sortowanie sterty dzielą i kopiują zbiory danych, aby zoptymalizować liczbę porównań. Szybkie sortowanie stale dzieli listę, a następnie ponownie składa ją w posortowanej kolejności. Sortowanie sterty kopiuje dane do struktury drzewiastej, a następnie przemierza drzewo, aby skopiować dane z powrotem do porządku. Oba są szybkie i wydajne, ale wymagają więcej kodu i znacznie więcej pamięci roboczej. Choose these algorithms for large data sets.

• Larger data sets require more complex code and more memory.
  
• The quick sort and heap sort both split and copy the data sets to optimise the number of comparisons.