Algorytmy Sortujące - Sortowanie przez kopcowanie

Jeśli przeczytałeś uważnie poprzednie dwa rozdziały, to zasadę sortowania przez kopcowanie zrozumiesz od razu - w zbiorze tworzymy kopiec, a następnie dokonujemy jego rozbioru. W wyniku wykonania tych dwóch operacji zbiór zostanie posortowany.

do podrozdziału do strony

Specyfikacja problemu

Dane wejściowe

d[ ]	- Zbiór zawierający elementy do posortowania, które są numerowane począwszy od 1.
n	- Ilość elementów w zbiorze, n ∈ N

Dane wyjściowe

d[ ]	- Zbiór zawierający elementy posortowane rosnąco

Zmienne pomocnicze i funkcje

Twórz_kopiec	-	procedura budująca kopiec z elementów zbioru d[ ]. Kopiec powstaje w zbiorze d[ ].
Rozbierz_kopiec	-	procedura dokonująca rozbioru kopca utworzonego w zbiorze d[ ]. Wynik rozbioru trafia z powrotem do zbioru d[ ].

Lista kroków

K01:	Twórz_kopiec
K02:	Rozbierz_kopiec
K03:	Zakończ algorytm

Ponieważ sortowanie przez kopcowanie składa się z dwóch następujących bezpośrednio po sobie operacji o klasie czasowej złożoności obliczeniowej O(n logn), to dla całego algorytmu klasa złożoności również będzie wynosić O(n logn).

do podrozdziału do strony

C++

// Sortowanie przez kopcowanie
//----------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie

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

using namespace std;

int main()
{
  const int N = 20;  // liczebność zbioru
  int d[N + 1],i,j,k,m,x;

  srand((unsigned)time(NULL));

  cout << " Sortowanie przez kopcowanie \n"
          "-----------------------------\n"
          "   (C)2005  Jerzy Walaszek\n\n"
          "Przed sortowaniem:\n\n";

// Wypełniamy tablicę liczbami
// pseudolosowymi i wyświetlamy je

  for(i = 1; i <= N; i++)
  {
    d[i] = rand() % 100;
    cout << setw(4) << d[i];
  }
  cout << endl;

// Budujemy kopiec

  for(i = 2; i <= N; i++)
  {
    j = i;
    k = j / 2;
    x = d[i];
    while((k > 0) && (d[k] < x))
    {
      d[j] = d[k];
      j = k;
      k = j / 2;
    }
    d[j] = x;
  }

// Rozbieramy kopiec

  for(i = N; i > 1; i--)
  {
    swap(d[1], d[i]);
    j = 1; k = 2;
    while(k < i)
    {
      if((k + 1 < i) && (d[k + 1] > d[k]))
        m = k + 1;
      else
        m = k;
      if(d[m] <= d[j]) break;
      swap(d[j], d[m]);
      j = m;
      k = j + j;
    }
  }

// Wyświetlamy wynik sortowania

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

Pascal

// Sortowanie przez kopcowanie
//----------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie

program heap_sort;

const N = 20;  // liczebność zbioru

var
  d         : array[1..N] of integer;
  i,j,k,m,x : integer;

begin
  writeln(' Sortowanie przez kopcowanie ');
  writeln('-----------------------------');
  writeln('   (C)2005  Jerzy Walaszek');
  writeln;
  writeln('Przed sortowaniem:');
  writeln;

// Wypełniamy tablicę liczbami
// pseudolosowymi i wyświetlamy je

  randomize;
  for i := 1 to N do
  begin
    d[i] := random(100);
    write(d[i] : 4);
  end;
  writeln;
  writeln;

// Budujemy kopiec

  for i := 2 to N do
  begin
    j := i;
    k := j div 2;
    x := d[i];
    while (k > 0) and (d[k] < x) do
    begin
      d[j] := d[k];
      j := k;
      k := j div 2;
    end;
    d[j] := x;
  end;

// Rozbieramy kopiec

  for i := N downto 2 do
  begin
    x := d[1];
    d[1] := d[i];
    d[i] := x;
    j := 1;
    k := 2;
    while k < i do
    begin
      if (k + 1 < i) and
         (d[k + 1] > d[k]) then
        m := k + 1
      else
        m := k;
      if d[m] <= d[j] then break;
      x := d[j];
      d[j] := d[m];
      d[m] := x;
      j := m;
      k := j + j;
    end;
  end;

// 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 przez kopcowanie
'----------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' w Tarnowie

CONST N = 20 ' liczebność zbioru

DIM AS INTEGER d(N),i,j,k,m,x

PRINT " Sortowanie przez kopcowanie"
PRINT "-----------------------------"
PRINT "   (C)2005  Jerzy Walaszek"
PRINT
PRINT "Przed sortowaniem:"
PRINT

' Wypełniamy tablicę liczbami
' pseudolosowymi i wyświetlamy je

RANDOMIZE
FOR i = 1 TO N
  d(i) = INT(RND * 100)
  PRINT USING "####";d(i);
NEXT
PRINT
PRINT

' Budujemy kopiec

FOR i = 2 TO N
  j = i
  k = j \ 2
  x = d(i)
  WHILE (k > 0) AND (d(k) < x)
    d(j) = d(k)
    j = k
    k = j / 2
  WEND
  d(j) = x
NEXT

' Rozbieramy kopiec

FOR i = N TO 2 STEP -1
  SWAP d(1), d(i)
  j = 1: k = 2
  WHILE k < i
    IF (k + 1 < i) AND _
       (d(k + 1) > d(k)) THEN
      m = k + 1
    ELSE
      m = k
    END IF
    IF d(m) <= d(j) THEN EXIT WHILE
    SWAP d(j), d(m)
    j = m
    k = j + j
  WEND
NEXT

' 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 przez kopcowanie
#----------------------------
# (C)2026 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# w Tarnowie

import random

n = 20 # liczebność zbioru

d = [random.randrange(100) for i in range(n+1)]

print(" Sortowanie przez kopcowanie")
print("-----------------------------")
print("   (C)2026  Jerzy Wałaszek")
print()
print("Przed sortowaniem:")
print()
for i in range(1,n + 1):
    print("%4d" % (d[i]),end="")
print()
print()

# Budujemy kopiec

for i in range(2,n+1):
    j = i
    k = j // 2
    x = d[i]
    while (k > 0) and (d[k] < x):
        d[j] = d[k]
        j = k
        k = j // 2
    d[j] = x

# Rozbieramy kopiec

for i in reversed(range(2,n +1)):
    d[1],d[i] = d[i],d[1]
    j = 1
    k = 2
    while k < i:
        if (k + 1 < i) and \
           (d[k + 1] > d[k]):
            m = k + 1
        else:
            m = k
        if d[m] <= d[j]: break
        d[j],d[m] = d[m],d[j]
        j = m
        k = j + j

# Wyświetlamy wynik sortowania

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

Wynik:

 Sortowanie przez kopcowanie
-----------------------------
   (C)2026  Jerzy Wałaszek

Przed sortowaniem:

  19  86  83   1  23  32   8  74   3  75  65  83  54  31  30  23  29  24  91  80

Po sortowaniu:

   1   3   8  19  23  23  24  29  30  31  32  54  65  74  75  80  83  83  86  91

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="frmheapsort">
      <h3 style="text-align: center">Sortowanie Przez Kopcowanie</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 Przez Kopcowanie
//----------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie

function main()
{
  var N = 20; // liczba elementów
  var d = new Array(N + 1);
  var i,j,k,x,t;

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

  for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * 100);
  t = "Przed sortowaniem:<BR><BR>";
  for(i = 1; i <= N; i++) t += d[i] + " ";
  t += "<BR><BR>";

// Budujemy kopiec

  for(i = 2; i <= N; i++)
  {
    j = i; k = Math.floor(j / 2);
    x = d[i];
    while((k > 0) && (d[k] < x))
    {
      d[j] = d[k];
      j = k; k = Math.floor(j / 2);
    }
    d[j] = x;
  }

// Rozbieramy kopiec

  for(i = N; i > 1; i--)
  {
    x = d[1]; d[1] = d[i]; d[i] = x;
    j = 1; k = 2;
    while(k < i)
    {
      if((k + 1 < i) && (d[k + 1] > d[k]))
        m = k + 1;
      else
        m = k;
      if(d[m] <= d[j]) break;
      x = d[j]; d[j] = d[m]; d[m] = x;
      j = m; k = j + j;
    }
  }

  // Wyświetlamy wynik sortowania

  t += "Po sortowaniu:<BR><BR>";
  for(i = 1; i <= N; i++) t += d[i] + " ";
  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

do podrozdziału do strony

Cechy Algorytmu Sortowania Przez Kopcowanie
klasa złożoności obliczeniowej optymistyczna	O(n logn)
klasa złożoności obliczeniowej typowa
klasa złożoności obliczeniowej pesymistyczna
Sortowanie w miejscu	TAK
Stabilność	NIE

do podrozdziału do strony

Co należy zmienić w podanym algorytmie, aby uzyskać sortowanie malejące?
Udowodnij, iż algorytm sortowania przez kopcowanie nie jest stabilny.
Uzasadnij, iż czas sortowania zbioru posortowanego odwrotnie jest najkrótszy.
Uzasadnij, iż klasa złożoności algorytmu sortowania przez kopcowanie wynosi O(n logn).

do podrozdziału do strony

Sortowanie stogowe
Heap Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze i funkcje

Lista kroków

Przykładowe programy

Sortowanie Przez Kopcowanie

Podsumowanie

Zadania dla ambitnych

Sortowanie stogowe Heap Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze i funkcje

Lista kroków

Przykładowe programy

Sortowanie Przez Kopcowanie

Podsumowanie

Zadania dla ambitnych

Sortowanie stogowe
Heap Sort