Algorytmy Sortujące - Sortowanie Głupie

Sortowanie głupie jest również bardzo złym algorytmem sortującym, lecz, w przeciwieństwie do opisanego w poprzednim rozdziale sortowania zwariowanego, daje zawsze poprawne wyniki. Zasada działania jest bardzo prosta:

Przeglądamy kolejne pary sąsiednich elementów sortowanego zbioru. Jeśli bieżąco przeglądana para elementów jest w złej kolejności, elementy pary zamieniamy miejscami i całą operację rozpoczynamy od początku zbioru. Jeśli przeglądniemy wszystkie pary i nie wystąpi zamiana, to zbiór będzie posortowany i algorytm może zakończyć działanie.

Naiwność (lub, jak wolą niektórzy, głupota) algorytmu wyraża się tym, iż po napotkaniu nieposortowanych elementów algorytm zamienia je miejscami, a następnie rozpoczyna całą pracę od początku zbioru. Złożoność obliczeniowa algorytmu przy sortowaniu zbioru nieuporządkowanego ma klasę O(n³). Sortowanie odbywa się w miejscu.

Algorytm sortowania głupiego występuje w dwóch wersjach - rekurencyjnej oraz iteracyjnej. Wersja rekurencyjna jest jeszcze gorsza od iteracyjnej, gdyż dodatkowo zajmuje pamięć na kolejne poziomy wywołań rekurencyjnych, dlatego nie będziemy się nią zajmować (zainteresowanych odsyłam do Wikipedii).

Na początek: podrozdziału strony

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	- zmienna sterująca pętli, i ∈ N

Lista kroków

K01:	Dla i = 1,2,...,n - 1: Wykonuj kroki K02...K04
K02:	Jeśli d[i] ≤ d[i + 1], to wykonaj następny obieg K01
K03:	d[i] ↔ d[i + 1]
K04:	Idź do kroku K01
K05:	Zakończ

Schemat blokowy

obrazek

Rozpoczynamy przeglądanie zbioru od pierwszego elementu - indeks i przyjmuje wartość 1. W pętli sprawdzamy kolejność elementu d[i] z elementem następnym d[i+1]. Ponieważ założyliśmy porządek rosnący, to w przypadku d[i] > d[i+1] elementy te są w złej kolejności (dla porządku malejącego należy zmienić relację większości na relację mniejszości). W takiej sytuacji zamieniamy miejscami elementy, indeks i ustawiamy z powrotem na 1 (powrót na sam początek algorytmu byłby nieco kłopotliwy do zrealizowania w językach programowania, stąd dla prostoty ustawiamy i na 1 za operacją zamiany elementów) i wracamy na początek pętli.

Jeśli porównywane elementy są w dobrej kolejności, zwiększamy indeks i o 1, sprawdzamy, czy osiągnął już wartość końcową n i, jeśli nie, wracamy na początek pętli. W przeciwnym razie kończymy - zbiór jest posortowany.

Na początek: podrozdziału strony

C++

// Sortowanie Głupie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

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

// Program główny
//---------------

int main()
{
  int d[N],i;
  
  cout << "  Sortowanie  glupie\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

  i = 0;
  do
  {
    if(d[i] > d[i+1]) // Porządek rosnący
    {
      swap(d[i], d[i+1]);
      i = 0;
      continue;
    }
    i++;
  } while(i < N-1);

// Wyświetlamy wynik sortowania

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;
  return 0;
}

Pascal

// Sortowanie Głupie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

program Stupid_Sort;

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

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

// Program główny
//---------------

var
  i,x : integer;
begin
  writeln('  Sortowanie  glupie  ');
  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

  i := 1;
  repeat
    if d[i] > d[i+1] then // Porządek rosnący
    begin
      x := d[i]; d[i] := d[i+1]; d[i+1] := x;
      i := 1;
      continue;
    end;
    inc(i);
  until i = N;

// Wyświetlamy wynik sortowania

  writeln('Po sortowaniu:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;
  writeln('Nacisnij Enter...');
  readln;
end.

Basic

' Sortowanie Głupie
'--------------------------------------------------------
' (C)2012 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

  PRINT "  Sortowanie  glupie  "
  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

  i = 1
  DO
    IF d(i) > d(i+1) THEN ' Porządek rosnący
      SWAP d(i), d(i+1)
      i = 1
      CONTINUE DO
    END IF
    i = i + 1
  LOOP UNTIL i = N

' 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="frmstupidsort">
      <h3 style="text-align: center">Sortowanie Głupie</h3>
      <p style="TEXT-ALIGN: center">
        (C)2012 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 Głupie
//--------------------------------------------------------
// (C)2012 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,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

  i = 0;
  do
  {
    if(d[i] > d[i+1]) // Porządek rosnący
    {
      x = d[i]; d[i] = d[i+1]; d[i+1] = x;
      i = 0;
      continue;
    }
    i++;
  } while(i < N-1);

  // 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>

Wynik:

Sortowanie glupie
----------------------
(C)2005 Jerzy Walaszek

Przed sortowaniem:

60 70 46 52 97 34 14 60 4 56 77 34 75 72 78 86 45 12 30 99

Po sortowaniu:

4 12 14 30 34 34 45 46 52 56 60 60 70 72 75 77 78 86 97 99

Na początek: podrozdziału strony

W celach badawczych testujemy czas wykonania algorytmu sortowania głupiego w środowisku opisanym we wstępie. Jednakże, ze względu na bardzo długi czas sortowania zbiorów o dużej liczbie elementów, ograniczyliśmy się jedynie do 8000 elementów. Program testujący jest następujący:

Pascal

// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie
//--------------------------------------

program TestCzasuSortowania;

uses Windows;

const
  NAZWA = 'Sortowanie Glupie - Stupid Sort';
  K1    = '----------------------------------------';
  K2    = '(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie';
  K3    = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
  K4    = '-------------------------------------------------------------------';
  MAX_LN = 4; // określa ostatnie LN
  LN : array[1..8] of integer = (1000,2000,4000,8000,16000,32000,64000,128000);

var
  D         : array[1..128000] of real; // sortowana tablica
  n         : integer;                  // liczba elementów
  qpf,tqpc  : int64;                    // dane dla pomiaru czasu
  qpc1,qpc2 : int64;

// Tutaj umieszczamy procedurę sortującą tablicę d
//-------------------------------------------------------
function Sort : extended;
var
  i : integer;
  x : real;
begin
  QueryPerformanceCounter(addr(qpc1));
  i := 1;
  repeat
    if d[i] > d[i+1] then // Porządek rosnący
    begin
      x := d[i]; d[i] := d[i+1]; d[i+1] := x;
      i := 1;
      continue;
    end;
    inc(i);
  until i = n;
  QueryPerformanceCounter(addr(qpc2));
  Sort := (qpc2 - qpc1 - tqpc) / qpf;
end;

// Program główny
//---------------
var
  i,j,k               : integer;
  tpo,tod,tpp,tpk,tnp : extended;
  f                   : Text;
begin
  if QueryPerformanceFrequency(addr(qpf)) then
  begin
    QueryPerformanceCounter(addr(qpc1));
    QueryPerformanceCounter(addr(qpc2));
    tqpc := qpc2 - qpc1;

    assignfile(f,'wyniki.txt'); rewrite(f);

// Wydruk na ekran

    writeln('Nazwa: ',NAZWA);
    writeln(K1);
    writeln(K2);
    writeln;
    writeln(K3);

// Wydruk do pliku

    writeln(f,'Nazwa: ',NAZWA);
    writeln(f,K1);
    writeln(f,K2);
    writeln(f,'');
    writeln(f,K3);
    for i := 1 to MAX_LN do
    begin
      n := LN[i];

// Czas sortowania zbioru posortowanego

      for j := 1 to n do d[j] := j;
      tpo := Sort;

// Czas sortowania zbioru posortowanego odwrotnie

      for j := 1 to n do d[j] := n - j;
      tod := Sort;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na początku - średnia z 10 obiegów

      tpp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[1] := random * n + 1;
        tpp += Sort;
      end;
      tpp /= 10;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na końcu - średnia z 10 obiegów

      tpk := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[n] := random * n + 1;
        tpk += Sort;
      end;
      tpk /= 10;

// Czas sortowania zbioru nieuporządkowanego - średnia z 10 obiegów

      tnp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := random;
        tnp += Sort;
      end;
      tnp /= 10;

      writeln(n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
      writeln(f,n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
    end;
    writeln(K4);
    writeln(f,K4);
    writeln(f,'Koniec');
    closefile(f);
    writeln;
    writeln('Koniec. Wyniki w pliku WYNIKI.TXT');
  end
  else writeln('Na tym komputerze program testowy nie pracuje !');
  writeln;
  write('Nacisnij klawisz ENTER...'); readln;
end.

Otrzymane wyniki są następujące (dla komputera o innych parametrach wyniki mogą się różnić co do wartości czasów wykonania, dlatego w celach porównawczych proponuję uruchomić podany program na komputerze czytelnika - najlepiej na noc):

Zawartość pliku wygenerowanego przez program

Nazwa: Sortowanie Glupie - Stupid Sort
----------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
   1000    0.000006    1.087045    0.001226    0.002302    0.676225
   2000    0.000012    7.998662    0.005473    0.010103    5.377530
   4000    0.000024   64.041837    0.020801    0.030448   43.222395
   8000    0.000050  513.938879    0.043996    0.087417  343.565348
-------------------------------------------------------------------
Koniec

Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):

n	-	ilość elementów w sortowanym zbiorze
t_po	-	czas sortowania zbioru posortowanego
t_od	-	czas sortowania zbioru posortowanego malejąco
t_pp	-	czas sortowania zbioru posortowanego z losowym elementem na początku
t_pk	-	czas sortowania zbioru posortowanego z losowym elementem na końcu
t_np	-	czas sortowania zbioru z losowym rozkładem elementów

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)

Na początek: podrozdziału strony

Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania głupiego wyciągamy następujące wnioski

Cechy Algorytmu Sortowania Głupiego
klasa złożoności obliczeniowej optymistyczna
klasa złożoności obliczeniowej typowa
klasa złożoności obliczeniowej pesymistyczna
Sortowanie w miejscu	TAK
Stabilność	TAK

Klasy złożoności obliczeniowej szacujemy następująco:

optymistyczna - dla zbiorów uporządkowanych (z niewielką liczbą elementów nie na swoich miejscach) - na podstawie czasów t_po, t_pp, t_pk
typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu t_np
pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu t_od.

Własności algorytmu
Algorytm	t_po	t_od	t_pp	t_pk	t_np
Sortowanie głupie
Sortowanie głupie

Dla zbioru już posortowanego klasa czasowej złożoności obliczeniowej wynosi O(n) - liniowa. Czas sortowania jest pomijalnie mały.
Dla zbioru posortowanego odwrotnie klasa czasowej złożoności obliczeniowej wynosi O(n³) - sześcienna, a czas sortowania jest najdłuższy z otrzymanych, jest to zatem przypadek najbardziej niekorzystny.
Dla zbioru posortowanego z losowym elementem na początku klasa czasowej złożoności obliczeniowej wynosi O(n²) - kwadratowa. Czas sortowania jest bardzo mały w porównaniu z czasem sortowania zbioru nieuporządkowanego.
Dla zbioru posortowanego z losowym elementem na końcu klasa czasowej złożoności obliczeniowej wynosi O(n²) - kwadratowa.
Dla zbioru o losowym rozkładzie elementów klasa czasowej złożoności obliczeniowej wynosi O(n³) - sześcienna. Czas sortowania jest krótszy w porównaniu z czasem sortowania zbioru uporządkowanego odwrotnie.

Na początek: podrozdziału strony

Z uwagi na bardzo długi czas pracy programu testującego musieliśmy ograniczyć do 8000 elementów badanie czasów sortowania dla algorytmu sortowania głupiego. Na podstawie wyników oszacuj przybliżone czasy dla 16000, 32000, 64000 oraz 128000 elementów (zadanie możesz rozwiązać pisząc odpowiedni program lub wykorzystując do obliczeń arkusz kalkulacyjny). Jak długo musiałby pracować nasz program testowy, aby zebrać wszystkie te wyniki? Wykorzystaj informację o ilości sortowań każdego typu wykonywanych w programie testującym.
Dlaczego czas t_po ma liniową czasową złożoność obliczeniową?
Uzasadnij, iż dla czasów t_pp i t_pk algorytm wykazuje kwadratową złożoność obliczeniową.

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Głupie sortowanie bąbelkowe
Stupid Bubble Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Głupie

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Głupie sortowanie bąbelkowe Stupid Bubble Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Głupie

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Głupie sortowanie bąbelkowe
Stupid Bubble Sort