Implementacja sortowania bąbelkowego w Javie

Istnieje dość duża liczba algorytmów sortowania, wiele z nich jest bardzo specyficznych i zostało opracowanych w celu rozwiązywania wąskiego zakresu problemów i pracy z określonymi typami danych. Jednak wśród całej tej różnorodności najprostszym algorytmem jest sortowanie bąbelkowe, które można zaimplementować w dowolnym języku programowania. Pomimo swojej prostoty leży u podstaw wielu dość złożonych algorytmów. Kolejną równie ważną zaletą jest jego prostota, dzięki czemu można go zapamiętać i wdrożyć od razu, bez konieczności posiadania przed sobą dodatkowej literatury.

Wstęp

Cały współczesny Internet składa się z ogromnej liczby różnego rodzaju struktur danych zgromadzonych w bazach danych. Przechowują wszelkiego rodzaju informacje, począwszy od danych osobowych użytkowników po rdzeń semantyczny wysoce inteligentnych zautomatyzowanych systemów. Nie trzeba dodawać, że sortowanie danych odgrywa niezwykle ważną rolę w tej ogromnej ilości uporządkowanych informacji. Sortowanie może być obowiązkowym krokiem przed wyszukaniem jakichkolwiek informacji w bazie danych, a znajomość algorytmów sortowania odgrywa bardzo ważną rolę w programowaniu.

Sortowanie oczami maszyn i oczu ludzi

Wyobraźmy sobie, że musisz posortować 5 kolumn o różnych wysokościach w kolejności rosnącej. Kolumny te mogą oznaczać dowolny rodzaj informacji (ceny akcji, przepustowość kanału komunikacyjnego itp.); możesz przedstawić kilka własnych wersji tego zadania, aby było bardziej przejrzyste. Cóż, jako przykład, posortujemy Avengersów według wzrostu: W odróżnieniu od programu komputerowego, sortowanie nie będzie dla Ciebie trudne, ponieważ zobaczysz cały obraz i od razu dowiesz się, którego bohatera trzeba gdzie przesunąć, aby sortowanie według wzrostu przebiegło pomyślnie. Prawdopodobnie już się domyśliłeś, że aby posortować tę strukturę danych w kolejności rosnącej, po prostu zamień miejscami Hulka i Iron Mana:

Zrobione!

To zakończy pomyślnie sortowanie. Jednak komputer, w przeciwieństwie do Ciebie, jest nieco głupi i nie widzi całej struktury danych jako całości. Jego program sterujący może porównać tylko dwie wartości jednocześnie. Aby rozwiązać ten problem, będzie musiała umieścić w swojej pamięci dwie liczby i przeprowadzić na nich operację porównania, a następnie przejść do kolejnej pary liczb i tak dalej, aż wszystkie dane zostaną przeanalizowane. Dlatego każdy algorytm sortowania można bardzo uprościć w postaci trzech kroków:

• Porównaj dwa elementy;
• Zamień lub skopiuj jeden z nich;
• Przejdź do następnego elementu;

Różne algorytmy mogą wykonywać te operacje na różne sposoby, ale przejdziemy do rozważenia, jak działa sortowanie bąbelkowe.

Algorytm sortowania bąbelkowego

Sortowanie bąbelkowe jest uważane za najprostsze, ale zanim opiszemy ten algorytm, wyobraźmy sobie, jak posortowałbyś Avengersów według wzrostu, gdybyś mógł niczym maszyna porównać ze sobą tylko dwóch bohaterów w jednym okresie czasu. Najprawdopodobniej wykonasz następujące czynności (najbardziej optymalnie):

• Przechodzisz do elementu zerowego naszej tablicy (Czarna Wdowa);
• Porównaj element zerowy (Czarna Wdowa) z pierwszym (Hulk);
• Jeśli element na pozycji zero jest wyższy, zamieniasz je;
• W przeciwnym wypadku, jeżeli element na pozycji zero jest mniejszy, pozostawiamy je na swoich miejscach;
• Przejdź na pozycję w prawo i powtórz porównanie (porównaj Hulka z Kapitanem)

Po przejrzeniu całej listy w jednym przebiegu z takim algorytmem sortowanie nie zostanie zakończone całkowicie. Z drugiej jednak strony największy element listy zostanie przesunięty maksymalnie na prawą pozycję. Tak będzie zawsze, bo gdy tylko znajdziesz największy element, będziesz ciągle zmieniać miejsca, aż przesuniesz go do samego końca. Oznacza to, że gdy tylko program „znajdzie” w tablicy Hulka, przeniesie go dalej na sam koniec listy: Dlatego też algorytm ten nazywany jest sortowaniem bąbelkowym, gdyż w wyniku jego działania największy element listy znajdzie się na samej górze tablicy, a wszystkie mniejsze elementy zostaną przesunięte o jedną pozycję w lewo: Aby zakończyć sortowanie, musisz wrócić na początek tablicy i powtórzyć pięć kroków opisanych powyżej, ponownie przechodząc od lewej do prawej, porównując i przesuwając elementy, jeśli to konieczne. Ale tym razem trzeba zatrzymać algorytm o jeden element przed końcem tablicy, bo wiemy już, że największy element (Hulk) jest absolutnie w skrajnej prawej pozycji: Zatem program musi mieć dwie pętle. Dla większej przejrzystości, zanim przejdziemy do przeglądu kodu programu, wizualizację działania sortowania bąbelkowego można zobaczyć pod tym linkiem: Wizualizacja działania sortowania bąbelkowego

Implementacja sortowania bąbelkowego w Javie

Aby zademonstrować, jak działa sortowanie w Javie, oto kod programu:

• tworzy tablicę składającą się z 5 elementów;
• przesyła do niego powstanie mścicieli;
• wyświetla zawartość tablicy;
• implementuje sortowanie bąbelkowe;
• ponownie wyświetla posortowaną tablicę.

Możesz wyświetlić poniższy kod, a nawet pobrać go do swojego ulubionego IntelliJ IDE. Zostanie to przeanalizowane poniżej:

class ArrayBubble{
    private long[] a;   // odwołanie do tablicy
    private int elems;  //liczba elementów w tablicy

    public ArrayBubble(int max){    //konstruktor klasy
        a = new long[max];          //utwórz tablicę o rozmiarze max
        elems = 0;                  //po utworzeniu tablica zawiera 0 elementów
    }

    public void into(long value){   // metoda wstawiania elementu do tablicy
        a[elems] = value;           // wstaw wartość do tablicy a
        elems++;                    //rozmiar tablicy wzrasta
    }

    public void printer(){          // metoda wyprowadzania tablicy do konsoli
        for (int i = 0; i < elems; i++){    //dla każdego elementu w tablicy
            System.out.print(a[i] + " ");   // wyjście do konsoli
            System.out.println("");         //nowy wiersz
        }
        System.out.println("----Wyjście tablicy końcowej----");
    }

    private void toSwap(int first, int second){ //metoda zamienia parę numerów tablicy
        long dummy = a[first];      // umieść pierwszy element w zmiennej tymczasowej
        a[first] = a[second];       // wstaw drugi element w miejsce pierwszego
        a[second] = dummy;          //zamiast drugiego elementu zapisz pierwszy z pamięci tymczasowej
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Pętla zewnętrzna
            for (int in = 0; in < out; in++){       //Pętla wewnętrzna
                if(a[in] > a[in + 1])               //Jeśli kolejność elementów jest nieprawidłowa
                    toSwap(in, in + 1);             // wywołanie metody zamiany
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Utwórz tablicę tablicową z 5 elementami

        array.into(163);       //wypełnij tablicę
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //wyświetl elementy przed sortowaniem
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // ponownie wydrukuj posortowaną listę
    }
}

Pomimo szczegółowych komentarzy w kodzie, podajemy opis niektórych metod zaprezentowanych w programie. Kluczowe metody wykonujące główną pracę w programie zapisane są w klasie ArrayBubble. Klasa zawiera konstruktor i kilka metod:

• into– sposób wstawiania elementów do tablicy;
• printer– wyświetla zawartość tablicy linia po linii;

• toSwap– w razie potrzeby przestawia elementy. W tym celu wykorzystywana jest zmienna tymczasowa dummy, do której zapisywana jest wartość pierwszej liczby, a w miejsce pierwszej liczby zapisywana jest wartość z drugiej liczby. Zawartość zmiennej tymczasowej jest następnie zapisywana do drugiej liczby. Jest to standardowa technika zamiany dwóch elementów;

  i wreszcie główna metoda:

• bubbleSorter– która wykonuje główną pracę i sortuje dane zapisane w tablicy, przedstawimy to jeszcze raz osobno:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Pętla zewnętrzna
          for (int in = 0; in < out; in++){       //Pętla wewnętrzna
              if(a[in] > a[in + 1])               //Jeśli kolejność elementów jest nieprawidłowa
                  toSwap(in, in + 1);             // wywołanie metody zamiany
          }
      }
  }

Tutaj należy zwrócić uwagę na dwa liczniki: zewnętrzny outi wewnętrzny in. Licznik zewnętrznyout zaczyna wyliczać wartości od końca tablicy i stopniowo zmniejsza się o jeden przy każdym kolejnym przebiegu. outZ każdym nowym przebiegiem zmienna jest przesuwana dalej w lewo, aby nie wpływać na wartości już posortowane do prawej strony tablicy. Wewnętrzny licznikin rozpoczyna wyliczanie wartości od początku tablicy i stopniowo zwiększa się o jeden przy każdym nowym przebiegu. Wzrost innastępuje aż do osiągnięcia out(ostatniego analizowanego elementu w bieżącym przebiegu). Wewnętrzna pętla inporównuje dwie sąsiednie komórki ini in+1. Jeśli inw elemencie przechowywana jest większa liczba niż in+1, wówczas wywoływana jest metoda toSwap, która zamienia miejscami te dwie liczby.

Wniosek

Algorytm sortowania bąbelkowego jest jednym z najwolniejszych. Jeżeli tablica składa się z N elementów, to w pierwszym przebiegu zostanie wykonanych N-1 porównań, w drugim N-2, następnie N-3 itd. Oznacza to, że zostanie wykonana całkowita liczba przejść: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Zatem podczas sortowania algorytm wykonuje około 0,5x(N ^2) porównań. Dla N = 5 liczba porównań wyniesie około 10, dla N = 10 liczba porównań wzrośnie do 45. Zatem wraz ze wzrostem liczby elementów złożoność sortowania znacznie wzrasta: Na szybkość algorytmu wpływa nie tylko liczba przejść, ale także liczba permutacji, które należy wykonać. W przypadku danych losowych średnia liczba permutacji (N^2) / 4, czyli około połowa liczby przejść. Jednak w najgorszym przypadku liczba permutacji może również wynosić N^2 / 2 - ma to miejsce w przypadku, gdy dane są początkowo posortowane w odwrotnej kolejności. Pomimo tego, że jest to dość powolny algorytm sortowania, dość ważne jest poznanie i zrozumienie jego działania, a jak wspomniano wcześniej, stanowi on podstawę dla bardziej złożonych algorytmów. Jgd!