Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących, ALGORYTMY


Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Można go potraktować jako ulepszenie opisanego w poprzednim rozdziale algorytmu sortowania głupiego. Zasada działania opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operację tę wykonujemy dotąd, aż cały zbiór zostanie posortowany.

Algorytm sortowania bąbelkowego przy porządkowaniu zbioru nieposortowanego ma klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.


 

0x01 graphic

Jako przykład działania algorytmu sortowania bąbelkowego posortujemy przy jego pomocy 5-cio elementowy zbiór liczb {5 4 3 2 1}, który wstępnie jest posortowany w kierunku odwrotnym, co możemy uznać za przypadek najbardziej niekorzystny, ponieważ wymaga przestawienia wszystkich elementów.

Obieg

Zbiór

Opis operacji

1

 5 4 3 2 1 

Rozpoczynamy od pierwszej pary, która wymaga wymiany elementów

 4 5 2 1 

Druga para też wymaga zamiany elementów

 4 3 5 2 

Wymagana wymiana elementów

 4 3 2 5 1 

Ostatnia para również wymaga wymiany elementów

 4 3 2 1 5 

Stan po pierwszym obiegu. Zwróć uwagę, iż najstarszy element (5) znalazł się na końcu zbioru, a najmłodszy (1) przesunął się o jedną pozycję w lewo.

2

 4 3 2 1 5 

Para wymaga wymiany

 3 4 2 1 5 

Para wymaga wymiany

 3 2 4 1 

Para wymaga wymiany

 3 2 1 4 5 

Elementy są w dobrej kolejności, zamiana nie jest konieczna.

 3 2 1 4 5 

Stan po drugim obiegu. Zwróć uwagę, iż najmniejszy element (1) znów przesunął się o jedną pozycję w lewo. Z obserwacji tych można wywnioskować, iż po każdym obiegu najmniejszy element wędruje o jedną pozycję ku początkowi zbioru. Najstarszy element zajmuje natomiast swe miejsce końcowe.

3

 3 2 1 4 5 

Para wymaga wymiany

 2 3 1 4 5 

Para wymaga wymiany

 2 1 3 4 

Dobra kolejność

 2 1 3 4 5 

Dobra kolejność

 2 1 3 4 5 

Stan po trzecim obiegu. Wnioski te same.

4

 2 1 3 4 5 

Para wymaga wymiany

 1 2 3 4 5 

Dobra kolejność

 1 2 3 4 

Dobra kolejność

 1 2 3 4 5 

Dobra kolejność

 1 2 3 4 5 

Zbiór jest posortowany. Koniec

Posortowanie naszego zbioru wymaga 4 obiegów. Jest to oczywiste: w przypadku najbardziej niekorzystnym najmniejszy element znajduje się na samym końcu zbioru wejściowego. Każdy obieg przesuwa go o jedną pozycję w kierunku początku zbioru. Takich przesunięć należy wykonać n - 1 (n - ilość elementów w zbiorze).

Algorytm sortowania bąbelkowego, w przeciwieństwie do algorytmu sortowania głupiego, nie przerywa porównywania par elementów po napotkaniu pary nie spełniającej założonego porządku. Po zamianie kolejności elementów sprawdzana jest kolejna para elementów sortowanego zbioru. Dzięki temu podejściu rośnie efektywność algorytmu oraz zmienia się klasa czasowej złożoności obliczeniowej z O(n3) na O(n2).

0x01 graphic

 

 

0x01 graphic

Algorytm sortowania bąbelkowego jest uważany za bardzo zły algorytm sortujący. Można go stosować tylko dla niewielkiej liczby elementów w sortowanym zbiorze (do około 5000). Przy większych zbiorach czas sortowania może być zbyt długi.

 

       Specyfikacja problemu

Dane wejściowe

n

- liczba elementów w sortowanym zbiorze, n  N

d[ ]

- zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.

Dane wyjściowe

d[ ]

- posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

Zmienne pomocnicze

i, j

- zmienne sterujące pętli, i, j  N

       Lista kroków

K01:

Dla j = 1,2,...,n - 1: wykonuj K02

K02:

    Dla i = 1,2,...,n - 1: jeśli d[i] > d[i + 1], to d[i] ↔ d[i + 1]

K03:

Zakończ algorytm

       Schemat blokowy

0x01 graphic

Sortowanie wykonywane jest w dwóch zagnieżdżonych pętlach. Pętla zewnętrzna nr 1 kontrolowana jest przez zmienną j. Wykonuje się ona n - 1 razy. Wewnątrz pętli nr 1 umieszczona jest pętla nr 2 sterowana przez zmienną i. Wykonuje się również n - 1 razy. W efekcie algorytm wykonuje w sumie:

T1(n) = (n - 1)2 = n2 - 2n + 1

obiegów pętli wewnętrznej, po których zakończeniu zbiór zostanie posortowany.

Sortowanie odbywa się wewnątrz pętli nr 2. Kolejno porównywany jest i-ty element z elementem następnym. Jeśli elementy te są w złej kolejności, to zostają zamienione miejscami. W tym miejscu jest najważniejsza różnica pomiędzy algorytmem sortowania bąbelkowego a algorytmem sortowania głupiego. Ten drugi w momencie napotkania elementów o złej kolejności zamienia je miejscami i rozpoczyna cały proces sortowania od początku. Algorytm sortowania bąbelkowego wymienia miejscami źle ułożone elementy sortowanego zbioru i przechodzi do następnej pary zwiększając indeks i o 1. Dzięki takiemu podejściu rośnie efektywność, co odzwierciedla klasa czasowej złożoności obliczeniowej:
Sortowanie głupie - O(n3); Sortowanie bąbelkowe - O(n2)


       Programy

0x01 graphic

 

 

0x01 graphic

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 

Efekt uruchomienia programu

Sortowanie babelkowe
WERSJA NR 1
----------------------
(C)2005 Jerzy Walaszek

Przed sortowaniem:

74 77 21 76 64 19 43 47 75 77 66 47 60 7 97 71 87 95 76 79

Po sortowaniu:

7 19 21 43 47 47 60 64 66 71 74 75 76 76 77 77 79 87 95 97

 

DevPascal

// Sortowanie Bąbelkowe - Wersja nr 1

//-------------------------------------------------

// (C)2005 mgr Jerzy Wałaszek

// I Liceum Ogólnokształcące

// im. K. Brodzińskiego

// w Tarnowie

//-------------------------------------------------

program Bubble_Sort_1;

const N = 20; // Liczebność zbioru.

var

d : array[1..N] of integer;

// Program główny

//---------------

var

i,j,x : integer;

begin

writeln(' Sortowanie babelkowe ');

writeln(' WERSJA NR 1 ');

writeln('----------------------');

writeln('(C)2005 Jerzy Walaszek');

writeln;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

// a następnie wyświetlamy jej zawartość

randomize;

for i := 1 to N do d[i] := random(100);

writeln('Przed sortowaniem:'); writeln;

for i := 1 to N do write(d[i] : 4);

writeln;

// Sortujemy

for j := 1 to N - 1 do

for i := 1 to N - 1 do

if d[i] > d[i+1] then // Porządek rosnący

begin

x := d[i]; d[i] := d[i+1]; d[i+1] := x;

end;

// Wyświetlamy wynik sortowania

writeln('Po sortowaniu:'); writeln;

for i := 1 to N do write(d[i] : 4);

writeln;

writeln('Nacisnij Enter...');

readln;

end.

DevC++

// Sortowanie Bąbelkowe - Wersja nr 1

//-------------------------------------------------

// (C)2005 mgr Jerzy Wałaszek

// I Liceum Ogólnokształcące

// im. K. Brodzińskiego

// w Tarnowie

//-------------------------------------------------

#include <cmath>

#include <iostream>

#include <iomanip>

using namespace std;

const int N = 20; // Liczebność zbioru.

// Program główny

//---------------

main()

{

int d[N],i,j;

cout << " Sortowanie babelkowe\n"

" WERSJA NR 1\n"

"----------------------\n"

"(C)2005 Jerzy Walaszek\n\n"

"Przed sortowaniem:\n\n";

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

// a następnie wyświetlamy jej zawartość

srand((unsigned)time(NULL));

for(i = 0; i < N; i++) d[i] = rand() % 100;

for(i = 0; i < N; i++) cout << setw(4) << d[i];

cout << endl;

// Sortujemy

for(j = 0; j < N - 1; j++)

for(i = 0; i < N - 1; i++)

if(d[i] > d[i + 1]) swap(d[i], d[i + 1]);

// Wyświetlamy wynik sortowania

cout << "Po sortowaniu:\n\n";

for(i = 0; i < N; i++) cout << setw(4) << d[i];

cout << endl;

system("PAUSE");

}

Free Basic

' Sortowanie Bąbelkowe - Wersja nr 1

'-------------------------------------------------

' (C)2005 mgr Jerzy Wałaszek

' I Liceum Ogólnokształcące

' im. K. Brodzińskiego

' w Tarnowie

'-------------------------------------------------

OPTION EXPLICIT

CONST N = 20 ' Liczebność zbioru.

DIM d(1 TO N) AS INTEGER, i AS INTEGER, j AS INTEGER

PRINT " Sortowanie babelkowe "

PRINT " WERSJA NR 1 "

PRINT "----------------------"

PRINT "(C)2005 Jerzy Walaszek"

PRINT

' Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

' a następnie wyświetlamy jej zawartość

RANDOMIZE TIMER

FOR i = 1 TO N: d(i) = INT(RND * 100): NEXT

PRINT "Przed sortowaniem:"

PRINT

FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT

PRINT

' Sortujemy

FOR j = 1 TO N - 1

FOR i = 1 TO N - 1

IF d(i) > d(i+1) THEN SWAP d(i), d(i+1)

NEXT

NEXT

' Wyświetlamy wynik sortowania

PRINT "Po sortowaniu:"

PRINT

FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT

PRINT

PRINT "Nacisnij Enter..."

SLEEP

END

JavaScript

<html>

<head>

</head>

<body>

<form style="BORDER-RIGHT: #ff9933 1px outset;

PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;

PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;

BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;

BORDER-BOTTOM: #ff9933 1px outset;

BACKGROUND-COLOR: #ffcc66" name="frmbubblesort">

<h3 style="text-align: center">Sortowanie Bąbelkowe - wersja nr 1</h3>

<p style="TEXT-ALIGN: center">

(C)2005 mgr Jerzy Wałaszek - I LO w Tarnowie

</p>

<hr>

<p style="TEXT-ALIGN: center">

<input onclick="main()" type="button" value="Sortuj" name="B1">

</p>

<p id="t_out" style="TEXT-ALIGN: center">...</p>

</form>

<script language=javascript>

// Sortowanie Bąbelkowe - wersja nr 1

//-------------------------------------------------

// (C)2005 mgr Jerzy Wałaszek

// I Liceum Ogólnokształcące

// im. K. Brodzińskiego

// w Tarnowie

//-------------------------------------------------

var N = 20; // Liczebność zbioru.

function main()

{

var d = new Array(N);

var i,j,x,t;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * 100);

t = "Przed sortowaniem:<BR><BR>";

for(i = 0; i < N; i++) t += d[i] + " ";

t += "<BR><BR>";

// Sortujemy

for(j = 0; j < N - 1; j++)

for(i = 0; i < N - 1; i++)

if(d[i] > d[i + 1])

{

x = d[i]; d[i] = d[i + 1]; d[i + 1] = x;

};

// Wyświetlamy wynik sortowania

t += "Po sortowaniu:<BR><BR>";

for(i = 0; i < N; i++) t += d[i] + " ";

document.getElementById("t_out").innerHTML = t;

}

</script>

</body>

</html>

Tutaj możesz przetestować działanie prezentowanego skryptu:

Idea algorytmu sortowania przez wybór jest bardzo prosta. Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. Zatem element najmniejszy powinien znaleźć się na pierwszej pozycji. Szukamy w zbiorze elementu najmniejszego i wymieniamy go z elementem na pierwszej pozycji. W ten sposób element najmniejszy znajdzie się na swojej docelowej pozycji.

W identyczny sposób postępujemy z resztą elementów należących do zbioru. Znów wyszukujemy element najmniejszy i zamieniamy go z elementem na drugiej pozycji. Otrzymamy dwa posortowane elementy. Procedurę kontynuujemy dla pozostałych elementów dotąd, aż wszystkie będą posortowane.

Algorytm sortowania przez wybór posiada klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.



0x01 graphic

Dla przykładu posortujmy tą metodą zbiór {4 7 2 9 3}. Kolorem zielonym oznaczyliśmy elementy zbioru, które są już posortowane.

Zbiór

Opis operacji

 4 7 2 9 3 

Wyszukujemy najmniejszy element w zbiorze. Jest nim liczba 2.

 2 7 4 9 3 

Znaleziony element minimalny wymieniamy z pierwszym elementem zbioru - liczbą 4

 2 7 4 9

Wśród pozostałych elementów wyszukujemy element najmniejszy. Jest nim liczba 3.

 2 3 4 9 7 

Znaleziony element minimalny wymieniamy z drugim elementem zbioru - liczbą 7.

 2 3 4 9 7 

Znajdujemy kolejny element minimalny - liczbę 4.

 2 3 4 9 7 

Wymieniamy go z samym sobą - element ten nie zmienia zatem swojej pozycji w zbiorze.

 2 3 4 9

Znajdujemy kolejny element minimalny

 2 3 4 7 9 

Wymieniamy go z liczbą 9

 2 3 4 7 9 

Ostatni element jest zawsze na właściwej pozycji. Sortowanie zakończone

Podana metoda sortuje zbiór rosnąco. Jeśli chcemy posortować zbiór malejąco, to zamiast elementu minimalnego poszukujemy elementu maksymalnego. Pozostała część procedury sortującej nie ulega zmianie.

       Specyfikacja problemu

Dane wejściowe

n

- liczba elementów w sortowanym zbiorze, n  N

d[ ]

- zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.

Dane wyjściowe

d[ ]

- posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

Zmienne pomocnicze

i, j

- zmienne sterujące pętli, i, j  N

pmin

- pozycja elementu minimalnego w zbiorze d[ ],  pmin  N

       Lista kroków

K01:

Dla j = 1, 2, ..., n - 1: wykonuj kroki K02...K04

K02:

    pmin ← j

K03:

    Dla i = j + 1,  j + 2, ..., n: jeśli d[i] < d[pmin], to pmin ← i

K04:

    d[j] ↔ d[pmin]

K05:

Zakończ algorytm

       Schemat blokowy

0x01 graphic

Pętla zewnętrzna sterowana zmienną j wyznacza kolejne elementy zbioru o indeksach od 1 do n - 1, w których zostaną umieszczone elementy minimalne. Na początku tej pętli zakładamy, iż elementem minimalnym jest element d[j] i zapamiętujemy jego indeks w zmiennej pmin.

W pętli numer 2 sterowanej zmienną i porównujemy pozostałe elementy zbioru z elementem d[pmin]. Jeśli element zbioru d[i] jest mniejszy od elementu d[pmin], to znaleźliśmy nowy element minimalny. W takim przypadku zapamiętujemy jego pozycję w pmin i kontynuujemy pętlę wewnętrzną.

Po zakończeniu pętli wewnętrznej pmin zawiera indeks elementu minimalnego. Zamieniamy miejscami element d[j] z elementem d[pmin]. Dzięki tej operacji element minimalny znajduje się na swojej docelowej pozycji. Zwiększamy j przechodząc do kolejnego elementu zbioru i kontynuujemy pętlę zewnętrzną.


       Programy

0x01 graphic

 

 

0x01 graphic

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 

Efekt uruchomienia programu

Sortowanie przez wybor
------------------------
(C)2005 Jerzy Walaszek

Przed sortowaniem:

98 49 73 16 64 25 5 83 54 51 80 3 98 26 86 87 80 68 5 11

Po sortowaniu:

3 5 5 11 16 25 26 49 51 54 64 68 73 80 80 83 86 87 98 98

 

DevPascal

// Sortowanie Przez Wybór

//-------------------------------------------------

// (C)2005 mgr Jerzy Wałaszek

// I Liceum Ogólnokształcące

// im. K. Brodzińskiego

// w Tarnowie

//-------------------------------------------------

program Selection_Sort;

const N = 20; // Liczebność zbioru.

var

d : array[1..N] of integer;

// Program główny

//---------------

var

i,j,x,pmin : integer;

begin

writeln(' Sortowanie przez wybor ');

writeln('------------------------');

writeln(' (C)2005 Jerzy Walaszek ');

writeln;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

// a następnie wyświetlamy jej zawartość

randomize;

for i := 1 to N do d[i] := random(100);

writeln('Przed sortowaniem:'); writeln;

for i := 1 to N do write(d[i] : 4);

writeln;

// Sortujemy

for j := 1 to N - 1 do

begin

pmin := j;

for i := j + 1 to N do

if d[i] < d[pmin] then pmin := i;

x := d[pmin]; d[pmin] := d[j]; d[j] := x;

end;

// Wyświetlamy wynik sortowania

writeln('Po sortowaniu:'); writeln;

for i := 1 to N do write(d[i] : 4);

writeln;

writeln('Nacisnij Enter...');

readln;

end.

Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii. Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii. Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego). Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, ang. Insertion Sort). Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym końcu. Tak porządkujemy karty. A jak przenieść tę ideę do świata komputerów i zbiorów liczbowych?

Algorytm sortowania przez wstawianie będzie składał się z dwóch pętli. Pętla główna (zewnętrzna) symuluje pobieranie kart, czyli w tym wypadku elementów zbioru. Odpowiednikiem kart na ręce jest tzw. lista uporządkowana (ang. sorted list), którą sukcesywnie będziemy tworzyli na końcu zbioru (istnieje też odmiana algorytmu umieszczająca listę uporządkowaną na początku zbioru). Pętla sortująca (wewnętrzna) szuka dla pobranego elementu miejsca na liście uporządkowanej. Jeśli takie miejsce zostanie znalezione, to elementy listy są odpowiednio rozsuwane, aby tworzyć miejsce na nowy element i element wybrany przez pętlę główną trafia tam. W ten sposób lista uporządkowana rozrasta się. Jeśli na liście uporządkowanej nie ma elementu większego od wybranego, to element ten trafia na koniec listy. Sortowanie zakończymy, gdy pętla główna wybierze wszystkie elementy zbioru.

Algorytm sortowania przez wstawianie posiada klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.

Wstawianie elementu na listę uporządkowaną

Najważniejszą operacją w opisywanym algorytmie sortowania jest wstawianie wybranego elementu na listę uporządkowaną. Zasady są następujące:

  1. Na początku sortowania lista uporządkowana zawiera tylko jeden, ostatni element zbioru. Jednoelementowa lista jest zawsze uporządkowana.

  2. Ze zbioru zawsze wybieramy element leżący tuż przed listą uporządkowaną. Element ten zapamiętujemy w zewnętrznej zmiennej. Miejsce, które zajmował, możemy potraktować jak puste.

  3. Wybrany element porównujemy z kolejnymi elementami listy uporządkowanej.

  4. Jeśli natrafimy na koniec listy, element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.

  5. Jeśli element listy jest większy od wybranego, to element wybrany wstawiamy na puste miejsce - lista rozrasta się o nowy element.

  6. Jeśli element listy nie jest większy od wybranego, to element listy przesuwamy na puste miejsce. Dzięki tej operacji puste miejsce wędruje na liście przed kolejny element. Kontynuujemy porównywanie, aż wystąpi sytuacja z punktu 4 lub 5.

0x01 graphic

Dla przykładu wstawmy wg opisanej metody pierwszy element zbioru listę uporządkowaną utworzoną z pozostałych elementów {8 4 5 6 9}. Elementy listy uporządkowanej zaznaczyliśmy kolorem zielonym. Puste miejsce zaznaczyliśmy kolorem białym:

Zbiór

Opis operacji

 8  4  5  6  9 

Element 8 znajduje się tuż przed listą uporządkowaną.

 8 

    4  5  6  9 

Wybieramy ze zbioru element 8. Zajmowane przez niego miejsce staje się puste.

    8 

    5  6  9 

Porównujemy 8 z pierwszym elementem listy uporządkowanej, z liczbą 4.

    8 

<<< 5  6  9 

Ponieważ element 4 jest mniejszy od elementu wybranego 8, przesuwamy go na puste miejsce. Zwróć uwagę, iż puste miejsce wędruje w kierunku końca listy uporządkowanej.

       8 

    5  6  9 

Porównujemy 8 z kolejnym elementem listy uporządkowanej, z liczbą 5.

       8 

 5 <<< 6  9 

5 jest5 mniejsze od 8, zatem wędruje na puste miejsce, które przesuwa się przed kolejny element listy uporządkowanej, liczbę 6.

          8 

4  5     6  9 

Porównujemy 8 z 6.

          8 

4  5  6 <<< 9 

6 jest mniejsze od 8, wędruje na puste miejsce.

             8 

4  5  6     9 

Porównujemy 8 z 9.

4  5  6  8  9 

Tym razem element wybrany wędruje na puste miejsce, ponieważ jest mniejszy od elementu 9 listy uporządkowanej. Operacja wstawiania jest zakończona. Lista rozrasta się o jeden element.

0x01 graphic

Wykorzystajmy podane informacje do posortowania opisywaną metodą zbioru { 7 3 8 5 2 }.

 

Zbiór

Opis operacji

 7  3  8 5  2 

Ostatni element jest zalążkiem listy uporządkowanej.

          5 

 7  3  8    2 

Ze zbioru wybieramy element leżący tuż przed listą uporządkowaną.

             5 

 7  3  8    2 

Wybrany element porównujemy z elementem listy.

             5 

 7  3  8  2 <<<

Ponieważ element listy jest mniejszy od elementu wybranego, to przesuwamy go na puste miejsce.

 7  3  8  2 

Na liście nie ma już więcej elementów do porównania, więc element wybrany wstawiamy na puste miejsce. Lista uporządkowana zawiera już dwa elementy.

       8 

 7  3     2  5 

Ze zbioru wybieramy 8

          8 

 7  3     2 

8 porównujemy z 2

          8 

 7  3  2 <<<

2 jest mniejsze, zatem przesuwamy je na puste miejsce.

             8 

 7  3  2   

8 porównujemy z 5

             8 

 7  3  2 <<<

5 jest mniejsze, przesuwamy je na puste miejsce

 7  3  2  5  8

Lista nie zawiera więcej elementów, zatem 8 wstawiamy na puste miejsce. Na liście uporządkowanej mamy już trzy elementy.

    3 

 7     2  5  8

Ze zbioru wybieramy 3

       3 

 7     2  5  8

3 porównujemy z 2

       3 

 7  2 <<< 5  8

2 jest mniejsze, wędruje zatem na puste miejsce

          3 

 7  2     8

3 porównujemy z 5.

 7  2  3  5  8

Tym razem mniejszy jest element wybrany. Znaleźliśmy jego miejsce na liście, więc wstawiamy go na puste miejsce. Lista zawiera już 4 elementy.

 7 

    2  3  5  8

Ze zbioru wybieramy ostatni element - liczbę 7.

    7 

    2  3  5  8

7 porównujemy z 2

    7 

 2 <<< 3  5  8

2 jest mniejsze, przesuwamy je na puste miejsce

       7 

 2     3  5  8

7 porównujemy z 3

       7 

 2  3 <<< 5  8

3 jest mniejsze, przesuwamy je na puste miejsce

          7 

 2  3     8

7 porównujemy z 5

          7 

 2  3 <<< 8

5 jest mniejsze, przesuwamy je na puste miejsce

             7 

 2  3  5     8

7 porównujemy z 8

 2  3  5  7  8

Element wybrany jest mniejszy, wstawiamy go na puste miejsce. Lista uporządkowana objęła już cały zbiór. Sortowanie jest zakończone.

       Specyfikacja problemu

Dane wejściowe

n

- liczba elementów w sortowanym zbiorze, n  N

d[ ]

- zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.

Dane wyjściowe

d[ ]

- posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

Zmienne pomocnicze

i, j

- zmienne sterujące pętli, i, j  N

x

- zawiera wybrany ze zbioru element.

       Lista kroków

K01:

Dla j = n - 1, n - 2, ..., 1: wykonuj kroki K02...K04

K02:

    x ← d[j];  i ← j + 1

K03:

    Dopóki ( i ≤ n )  i  ( x > d[i] ): wykonuj d[i - 1] ← d[i];  i ← i + 1

K04:

    d[i - 1] ← x

K05:

Zakończ algorytm

       Schemat blokowy

0x01 graphic

Pętlę główną rozpoczynamy od przedostatniej pozycji w zbiorze. Element na ostatniej pozycji jest zalążkiem listy uporządkowanej. Dlatego licznik pętli nr 1 przyjmuje wartość początkową j = n - 1.

Ze zbioru wybieramy element d[j] i umieszczamy go w zmiennej pomocniczej x. Miejsce zajmowane przez ten element staje się puste.

Uwaga techniczna

W rzeczywistości na pozycji j pozostaje dalej ten sam element. Jednakże zapamiętaliśmy jego wartość, zatem pozycja ta może być zapisana inną informacją - elementu nie utracimy, ponieważ przechowuje go zmienna x. Dlatego pozycję tę możemy potraktować jako pustą, tzn. z nieistotną zawartością.

Pętlę wewnętrzną rozpoczynamy od pozycji następnej w stosunku do j. Pozycja ta zawiera pierwszy element listy uporządkowanej, która tworzona jest na końcu sortowanego zbioru. Pętlę wewnętrzną przerywamy w dwóch przypadkach - gdy licznik pętli wyjdzie poza indeks ostatniego elementu w zbiorze lub gdy element wybrany, przechowywany w zmiennej pomocniczej x, jest mniejszy lub równy bieżąco testowanemu elementowi listy uporządkowanej (dla sortowania malejącego należy zastosować w tym miejscu relację większy lub równy). W obu przypadkach na puste miejsce ma trafić zawartość zmiennej x i pętla zewnętrzna jest kontynuowana. Zauważ, iż pozycja tego miejsca w zbiorze jest równa i - 1.

Jeśli żaden z warunków przerwania pętli wewnętrznej nr 2 nie wystąpi, to przesuwamy bieżący element listy na puste miejsce i kontynuujemy pętlę wewnętrzną.

Podsumowując: pętla zewnętrzna wybiera ze zbioru kolejne elementy o indeksach od n - 1 do 1, pętla wewnętrzna szuka dla wybranych elementów miejsca wstawienia na liście uporządkowanej, po znalezieniu którego pętla zewnętrzna wstawia wybrany element na listę. Gdy pętla zewnętrzna przebiegnie wszystkie elementy o indeksach od n - 1 do 1, zbiór będzie posortowany.

Algorytm posiada klasę czasowej złożoności obliczeniowej równą O(n2). Sortowanie odbywa się w miejscu.

       Programy

0x01 graphic

 

 

0x01 graphic

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 

Efekt uruchomienia programu

Sortowanie przez wstawianie
-----------------------------
(C)2005 Jerzy Walaszek

Przed sortowaniem:

56 5 18 74 83 24 13 4 50 74 63 83 65 65 63 40 81 69 60 84

Po sortowaniu:

4 5 13 18 24 40 50 56 60 63 63 65 65 69 74 74 81 83 83 84

 

DevPascal

// Sortowanie Przez Wstawianie

//-------------------------------------------------

// (C)2005 mgr Jerzy Wałaszek

// I Liceum Ogólnokształcące

// im. K. Brodzińskiego

// w Tarnowie

//-------------------------------------------------

program Insertion_Sort;

const N = 20; // Liczebność zbioru.

var

d : array[1..N] of integer;

// Program główny

//---------------

var

i,j,x : integer;

begin

writeln(' Sortowanie przez wstawianie ');

writeln('-----------------------------');

writeln(' (C)2005 Jerzy Walaszek ');

writeln;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

// a następnie wyświetlamy jej zawartość

randomize;

for i := 1 to N do d[i] := random(100);

writeln('Przed sortowaniem:'); writeln;

for i := 1 to N do write(d[i] : 4);

writeln;

// Sortujemy

for j := N - 1 downto 1 do

begin

x := d[j];

i := j + 1;

while (i <= N) and (x > d[i]) do

begin

d[i - 1] := d[i];

inc(i);

end;

d[i - 1] := x;

end;

// Wyświetlamy wynik sortowania

writeln('Po sortowaniu:'); writeln;

for i := 1 to N do write(d[i] : 4);

writeln;

writeln('Nacisnij Enter...');

readln;

end.



Wyszukiwarka

Podobne podstrony:
ALS - 009-000 - Zajęcia - Sortowanie bąbelkowe, Informatyka - uczelnia, WWSI i WAT, wwsi, SEM II, Al
Sortowanie bąbelkowe
Oko jest jednym z najważniejszych narządów zmysłów
Sławomir Mrożek - Tango Opracowanie, Tango Sławomira Mrożka jest jednym z najbardziej znanych na świ
prawo18, Tworzenie prawa jest jednym z elementów nadbudowy, czyli wytworu bazy, tj
Chiny, Kultura chińska jest jedna z najstarszych kultur świata
Historia wychowania, Uniwersytet jest to najstarszy wielo wydzialowy typ szkoly wyzszej, Uniwersytet
Historia wychowania, Uniwersytet jest to najstarszy wielo wydzialowy typ szkoly wyzszej, Uniwersytet
historiafilozofii9[1].0 nowozytnosc, Problem dualizmu psychofizycznego jest jednym z centralnych tem
Antropologia filozoficzna jest jednym z dzia, pedagogika i praca socjalna
jak wykonac sortowanie babelkowealgorytm bubble sort, PHP Skrypty
materiały politologia semestry I-IV, sciaga+polityka społ-gosp, Polityka pieniężna jest jednym z pod
20030828120340, Transport jest jednym z najważniejszych czynników determinujących rozwój gospodarczy
stelmach od patrycji, 1.System polityczny, System polityczny- jest jednym z trzech systemów obok spo
Motyw wędrówki jest jednym
wszystkie Imiona żeńskie, Z, Zuzanna - Spośród używanych dziś w Polsce imion, imię Zuzanna jest z pe
Alkoholizm jest jednym z nałogów młodzieży licealnej
28 Sortowanie bąbelkowe

więcej podobnych podstron