Program C do sortowania bąbelków: Sortowanie bąbelków w C

Wstęp

Sortowanie tablicy ma ogromne znaczenie w informatyce. Jego użyteczność dostrzega się, gdy zachodzi potrzeba uporządkowania danych w określonej kolejności. Istnieją różne rodzaje algorytmów sortowania. Najpopularniejszym i najczęściej używanym algorytmem sortowania jest sortowanie bąbelkowe.

Sortowanie bąbelkowe w C

Technika używana do sortowania w sortowaniu bąbelkowym jest prosta i łatwa do zrozumienia. Wszystko, co robi, to porównuje bieżący element z następnym elementem i zamienia go, jeśli jest większy lub mniejszy, zgodnie z warunkiem. Algorytm jest bardzo dokładny. Za każdym razem, gdy element jest porównywany z innymi elementami, aż do znalezienia jego miejsca, nazywa się to przejściem.

Algorytm ten jest porównywalny z bąbelkami w wodzie, ponieważ filtruje górną część bąbelków przypominających tablicę. Spośród wszystkich algorytmów używanych do sortowania sortowanie bąbelkowe jest najłatwiejsze i najwolniejsze przy złożoności czasowej O(n^2). Jednak algorytm można zoptymalizować za pomocą zmiennej flagi, która opuszcza pętlę po zakończeniu wymiany. Najlepszym przypadkiem sortowania bąbelkowego może być O(n), gdy tablica jest sortowana.

Na przykład weźmy nieposortowaną tablicę pięciu liczb, jak podano poniżej

13, 32,26, 34,9

Sortowanie bąbelkowe zacznie brać pod uwagę pierwsze dwa elementy i porówna je, aby sprawdzić, który z nich jest większy. W tym przypadku 32 jest większe niż 13. Więc ta część jest już posortowana. Następnie porównujemy 32 z 26. Więc stwierdzamy, że 32 jest większe niż 26, więc muszą być zamienione. Nowa tablica będzie wyglądać jak

13, 26, 32,34,9

Następnie porównujemy 32 i 34. Wiemy, że są już posortowane. W ten sposób przechodzimy do dwóch ostatnich zmiennych 34 i 9. Ponieważ 34 jest większe niż 9, należy je zamienić.

Zamieniamy wartości i po pierwszej iteracji dochodzimy do końca tablicy. Teraz tablica będzie wyglądać tak

13, 26. 32,9,34

Po drugiej iteracji tablica będzie wyglądać tak:

13, 26, 9,32,34

Po trzeciej iteracji tablica stanie się

13,9,26,32,34

Po czwartej iteracji tablica zostanie całkowicie posortowana

9, 13,26,32,34

Trzeba przeczytać: Pomysły na projekty w C

Algorytm

Tutaj zakładamy, że tablica ma n elementów. Ponadto zakładamy, że funkcja wymiany wartości zamienia wszystkie wartości, aby uporządkować liczby w tablicy.

uruchom sortowanie bąbelkowe (tablica)

dla wszystkich elementów listy

jeśli tablica[i]> tablica[i+1]

zamień wartości(tablica[i], tablica[i+1] )

koniec jeśli

koniec dla

zwróć tablicę

koniec sortowania bąbelkowego

Przeczytaj: Sortowanie w strukturze danych: kategorie i typy

Pseudo kod

W powyższym algorytmie widać, że istnieje porównanie między każdą parą elementów tablicy, dopóki cała tablica nie zostanie posortowana w porządku rosnącym. Może to skutkować kilkoma problemami złożoności, takimi jak wynik algorytmu, gdy tablica jest już posortowana w kolejności rosnącej. Aby złagodzić ten problem, użyjemy jednej zmiennej flagi, która pozwoli nam zobaczyć, czy nastąpiła zamiana. Jeśli nie będzie już potrzebna zamiana, wyjdziemy z wewnętrznej pętli.

Pseudokod algorytmu BubbleSort można zapisać w następujący sposób

procedura BubbleSort (tablica: elementy tablicy)

iteracja= tablica.liczba;

dla k=0 do iteracji-1 wykonaj:

flaga= fałsz

dla l=0 do iteracji-1 wykonaj:

if (tablica[l]> tablica[l+1]) then

wartości wymiany(tablica[l], tablica [l+1])

flaga=prawda

koniec jeśli

koniec dla

Jeśli (nie zamienione), to

Zepsuć

Zakończ, jeśli

Koniec za

Zakończ procedurę zwracania tablicy

Wypróbujmy przykładowy program sortowania bąbelkowego w C :

# include<stdio.h>

nieważne główne

{

int tablica [10], i, j, num

dla (i=0; i<=9; i++)

{

scanf(„%d”, &tablica[i])

}

dla(i=0;i<=9;i++)

{

dla(j=0;j<=9-i;j++)

{

if(tablica[j]>tablica[j+1])

{

liczba= tablica[j];

tablica[j]=tablica[j+1];

tablica[j+1]=liczba;

}

}

}

printf("Posortowana tablica to /n");

dla(i=0;i<=9;i++)

{

printf(“%d ”,&tablica[i])

}

}

Jak pokazano w przykładzie, ten algorytm sortowania bąbelkowego akceptuje 10 liczb od użytkownika i przechowuje je w tablicy. W kolejnej części są dwie pętle for. Zewnętrzna pętla działa dla wartości I, równej zero do mniej niż równej dziewięciu. Funkcją pętli zewnętrznej jest zadbanie o wszystkie elementy wartości, które trzeba porównać z innymi elementami.

Wewnątrz zewnętrznej pętli znajduje się kolejna pętla. Zaczyna się od j=0 i biegnie, aż będzie mniejsze lub równe osiem. Wewnątrz znajduje się warunkowa instrukcja if, która porównuje i sprawdza, czy tablica[j] jest większa niż tablica [j+1]. Jeśli warunek jest spełniony, wartości array[j] i array [j+1] są zamieniane między sobą.

Służy do tego zmienna o nazwie num. Pierwsza tablica[j] jest przypisywana do liczby, następnie tablica[j+1] jest przypisywana do tablicy[j], a na końcu liczba jest przypisywana do tablicy[j+1]. Ten proces będzie kontynuowany, dopóki wszystkie elementy w tablicy nie zostaną posortowane w kolejności rosnącej. Następnie drukowana jest posortowana tablica.

Zoptymalizowana implementacja Bubble Sort

Mamy zoptymalizowany algorytm sortowania bąbelków w celu poprawy wyników. Optymalizacja odbywa się za pomocą zmiennej flagi. Zmienna flag będzie przechowywać 1, jeśli nastąpi zamiana, w przeciwnym razie wyrwie się z pętli. Poniżej znajduje się zoptymalizowany program sortowania bąbelkowego w C.

#include<stdio.h>

nieważne główne

{

int tablica [10], i, j, liczba, flaga=0;

dla (i=0; i<=9; i++)

{

scanf(„%d”, &tablica[i])

}

dla(i=0;i<=9;i++)

{

dla(j=0;j<=9-i;j++)

{

if(tablica[j]>tablica[j+1])

{

liczba= tablica[j];

tablica[j]=tablica[j+1];

tablica[j+1]=liczba;

flaga=1;

}

jeśli(! flaga)

{

zepsuć;

}

}

}

printf("Posortowana tablica to /n");

dla(i=0;i<=9;i++)

{

printf(“%d ”,&tablica[i])

}

}

Dany program działa w sposób podobny do normalnego programu sortowania bąbelkowego. Jedyną zmianą jest użycie zmiennej flag. Początkowo flaga jest ustawiona na 0. Jeśli jednak nastąpi zamiana, flaga wynosi 1. Oznacza to, że tablica nadal wymaga jeszcze jednego sprawdzenia. Z drugiej strony, jeśli flaga jest inna niż 1, co oznacza, że ​​zamiana nie miała miejsca, wychodzimy z wewnętrznej pętli, zakładając, że tablica jest już posortowana. Po wykonaniu otrzymamy ten sam wynik, co normalne sortowanie bąbelkowe.

Złożoność czasu

Najlepszą złożonością czasową dla sortowania bąbelkowego jest O(n). Dzieje się tak, gdy tablica jest już posortowana. Najgorszym przypadkiem jest O(n*n), gdy tablica nie została posortowana.

Przeczytaj: 12 najlepszych programów wzorcowych w Javie, które powinieneś sprawdzić dzisiaj

Co następne?

Jeśli chcesz dowiedzieć się więcej na temat Java, pełnego stosu oprogramowania, sprawdź upGrad i IIIT-B's PG Diploma in Full-stack Software Development, który jest przeznaczony dla pracujących profesjonalistów i oferuje ponad 500 godzin rygorystycznych szkoleń, ponad 9 projektów i zadania, status absolwentów IIIT-B, praktyczne praktyczne projekty zwieńczenia i pomoc w pracy z najlepszymi firmami.