W pracy z informacją najbardziej opłacalnymi sposobami jej przechowywania są struktury i tablice. Te ostatnie mogą zawierać wszelkiego rodzaju dane tego samego rodzaju, co jest wygodne do wykorzystania w pracy programu. Są często używane w sklepach internetowych i przy tworzeniu gier. Dlatego zawarte w nich dane są wielokrotnie sortowane i zmieniane miejscami, a nad nimi wykonywane są operacje logiczne lub matematyczne. Jednym ze sposobów ustawiania porządku w tablicy jest sortowanie bąbelkowe. Ta publikacja zbada swój kod programu w języku C i logikę permutacji.

Algorytm do sortowania macierzy

Techniczna złożoność programisty nie polega na sortowaniu bąbelkowym jednowymiarowej macierzy, chociaż jest rzadko używana ze względu na niską wydajność. Częściej jest uważany na etapie uczenia się za najprostszy. Jednak nie jest to najskuteczniejsze. Jego algorytm składa się z sekwencyjnego porównywania cyfr i odwrotnego przepisywania komórek, jeśli obserwowany jest warunek.

Opis sortowania krok po kroku

Przy pierwszej iteracji dwie sąsiednie liczby są stopniowo porównywane. Jeśli lewe jest większe, to jest ono zastępowane prawą. Warunki Minus 8 i 0 nie są spełnione. I dlatego miejsca się nie zmieniają. Zero i 5 również nie są odpowiednie. 5 i 3 - dopasowanie. Jednak przy takiej iteracji ramka odczytu nie mieści się w pierwszej piątce i przesuwa się w prawo, ponieważ 5 zostało porównane do zera. Oznacza to, że następna para miejsc została zmieniona - 3 i 9. NastępnieWszystkie substytucje są oferowane czytelnikowi do niezależnego przeglądania bez uwag autora i do badania algorytmu sortowania bąbelkowego.


W wyniku wszystkich iteracji, tablica jest stopniowo sortowana, a dzieje się to głównie w następujący sposób: duże liczby dodatnie szybko przesuwają się w prawo, podczas gdy mniejsze i ujemne powoli przesuwają się w lewo. Wygląda na to, że pęcherzyki gazu w cieczy szybko pojawiają się. Z powodu tej analogii algorytm nazwano sortowaniem bąbelkowym.

Oszacowanie złożoności obliczeniowej

Idealny algorytm sortowania powinien być możliwie jak najszybszy. W tym samym czasie powinien zabrać niewielką ilość zasobów procesora i pamięci. A taki proces, jak sortowanie bąbelkowe, nie może być najbardziej energooszczędny i opłacalny. Dlatego nie znalazł szerokiego zastosowania. Jeśli w tej chwili jest mniej pamięci, zasoby procesora powinny się martwić. Ponieważ tablice cyfrowe mogą nie tylko być duże, ale i ogromne, koszty zasobów komputerowych będą nieprzewidywalne. Jeśli sortowanie bąbelkowe z zasady szybko poradzi sobie z porządkowaniem zamówienia w stosunkowo małej tablicy, to w dużym może dojść do awarii z powodu nadmiernego wykorzystania zasobów. Oznacza to, że naruszona zostanie właściwość uniwersalności nieodłącznie związana z algorytmem. Co więcej, sortowanie bąbelkowe ma złożoność N-kwadratową i jest bardzo odległe od log złożoności N. Ponadto ryzyko niepowodzenia w przetwarzaniu dużej macierzy zwiększa szanse utraty danych z powodu przepisywania komórek. O wiele bardziej opłaca się wW tym planie będzie sortowanie wstawek lub algorytmu Schella.

Kod programu

Kod komputerowy dla języka C wymienionego poniżej w dodatku graficznym umożliwia sortowanie bąbelkowe. Wydawany jest jako oddzielna funkcja typu void. Nie zwraca żadnych wartości, ale użycie wskaźników zmienia miejsca w elementach w zależności od warunków sortowania. W tym przypadku kod rozwiązuje problem bąbelków sortowania tablicy liczb całkowitych w porządku rosnącym.
Aby wykonać tę funkcję, użytkownik musi utworzyć tablicę, która musi zostać wypełniona wymaganymi wartościami. Możesz to zrobić ręcznie, określając wymiar i liczbę elementów na początku programu. W tym samym czasie możesz wypełnić tablicę stałymi wartościami. Drugą opcją jest stworzenie uniwersalnego programu poprzez zadeklarowanie dużej jednowymiarowej tablicy 100 elementów.

Deklarowanie i inicjowanie tablicy

Ustawiając zmienną całkowitą i nadając jej wartość odczytaną z klawiatury, można ograniczyć liczbę komórek, które zostaną wypełnione. Możesz także zaimplementować funkcję wprowadzania elementów tablicy przez użytkownika z klawiatury za pomocą funkcji scanf ("% d" i wartość). W tym przykładzie "% d" jest ciągiem modyfikującym, który mówi kompilatorowi, że po skanowaniu zostanie uzyskana wartość całkowita. Wartość zmiennej przechowuje wartość, która jest wielkością jednowymiarowej tablicy całkowitej. Aby użyć algorytmu sortowania, nazwa tablicy i jej rozmiar muszą zostać przekazane do funkcji. W sytuacji przedstawionej w aplikacji graficznej wywołanie funkcjiSortowanie będzie wyglądać następująco: BubleSort (dataArray, sizeDataArray). Oczywiście na końcu wiersza po funkcji należy wstawić średnik zamiast kropki, zgodnie z regułami składni programu. A zatem dataArray to nazwa tablicy, którą chcesz posortować, a sizeDataArray to jej rozmiar. Przeniesienie tych parametrów do funkcji BubleSort () spowoduje, że zamiast używać sizeArray, jak widać na rysunku, operacje w rzeczywistym programie będą wykonywane z sizeDataArray. Oznacza to, że funkcja BubleSort () użyje tablicy całkowitej typu dataArray. Podobnie wywoływane są funkcje printArrayFunction () i ArrayIntegerInputFunction (). Pierwszy jest odpowiedzialny za drukowanie, czyli wysyłanie elementów do konsoli. Drugi jest potrzebny do wypełnienia go elementami wprowadzonymi przez użytkownika z klawiatury.
Ten styl programowania, gdy pojedyncze operacje wykonywane są jako funkcje, znacznie zwiększa czytelność kodu i przyspiesza jego rozwój. W takim programie jest osobno wypełniany tablicą z klawiatury, a drukowany jest ten sam sortowanie bąbelkowe. Te ostatnie można wykorzystać do uporządkowania danych lub jako funkcji drugorzędnej, która stara się znaleźć minimum i maksimum tablicy.

Sortowanie wkładek

Sortowanie metodą wstawiania zapewnia stopniowe porównywanie każdego elementu i budowę łańcucha już posortowanego zgodnie ze stanem elementów. W rezultacie wynikiem każdego kolejnego porównania jest wyszukiwanie komórki, która może być umieszczona w nowej wartości. Ale wstawienie każdego z nich odbywa się już posortowaną częścią tablicy. Takie przetwarzanie jest szybsze i ma mniejszą złożoność obliczeniową. Kod w języku C przedstawiono w dodatku graficznym. Jest on również przedstawiony w postaci funkcji, która jako argumenty przekazane do nazwy musi ułożyć tablicę i rozmiar tablicy. Tutaj możesz zobaczyć, jak powolne jest sortowanie bąbelkowe. Wkładki są podobne do pracy wykonywanej znacznie szybciej i mają zwarty kod programu.