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).

do podrozdziału do 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

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.

do podrozdziału do strony

C++

// Sortowanie Głupie
//---------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// 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 << 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 << endl;
  system("pause");
  return 0;
}

Pascal

// Sortowanie Głupie
//---------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// 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;
  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;
  writeln('Nacisnij Enter...');
  readln;
end.

Basic

' Sortowanie Głupie
'---------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' w Tarnowie

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
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
PRINT "Nacisnij Enter...";
SLEEP
END

Python (dodatek)

# Sortowanie Głupie
#---------------------------
# (C)2026 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# w Tarnowie

import random

n = 20 # Liczebność zbioru d[]

# sortowany zbiór
d = [random.randrange(100) for i in range(n)]

print("  Sortowanie  głupie  ")
print("----------------------")
print("(C)2026 Jerzy Wałaszek")
print()

# wyswietlamy zawartość d[]

for i in range(n):
    print("%4d" % (d[i]),end="")
print()
print()

# Sortujemy

i = 0
while i != n-1:
    if d[i] > d[i+1]: # Porządek rosnący
        d[i],d[i+1] = d[i+1],d[i]
        i = 0
        continue
    i = i + 1

# Wyświetlamy wynik sortowania

print("Po sortowaniu")
print()
for i in range(n):
    print("%4d" % (d[i]), end="")
print()
print()
input("Naciśnij Enter...")

Wynik:

  Sortowanie  głupie  
----------------------
(C)2026 Jerzy Wałaszek

  67  88  79  41  42  31  48  51  20   9   7  97  60  11  64  28   7   5  66  73

Po sortowaniu

   5   7   7   9  11  20  28  31  41  42  48  51  60  64  66  67  73  79  88  97

Naciśnij Enter...

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

do podrozdziału do strony

Cechy Algorytmu Sortowania Głupiego
klasa złożoności obliczeniowej optymistyczna	O(n)...O(n²)
klasa złożoności obliczeniowej typowa	O(n³)
klasa złożoności obliczeniowej pesymistyczna	O(n³)
Sortowanie w miejscu	TAK
Stabilność	TAK

do podrozdziału do 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

Podsumowanie

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

Podsumowanie

Głupie sortowanie bąbelkowe
Stupid Bubble Sort