|
Serwis Edukacyjny Nauczycieli w I-LO w Tarnowie
Materiały głownie dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2026 mgr Jerzy Wałaszek
|
Poczynając od tego rozdziału przechodzimy do opisu
algorytmów szybkich, tzn. takich, które posiadają klasę czasowej złożoności obliczeniowej równą
W informatyce zwykle obowiązuje zasada, iż prosty algorytm posiada dużą złożoność obliczeniową, natomiast algorytm zaawansowany posiada małą złożoność obliczeniową, ponieważ wykorzystuje on pewne własności, dzięki którym szybciej dochodzi do rozwiązania.
Wiele dobrych algorytmów sortujących korzysta z rekurencji, która powstaje wtedy, gdy do rozwiązania problemu algorytm wykorzystuje samego siebie ze zmienionym zestawem danych.
Przykład:
Jako przykład może posłużyć rekurencyjne obliczanie silni. Silnię liczby n należącej do zbioru liczb naturalnych definiujemy następująco:
n! = 1 × 2 × 3 × ... × (n - 1) × n
Na przykład:
5! = 1 × 2 × 3 × 4 × 5 = 120
| n | - liczba, której silnie liczymy na danym poziomie rekurencyjnym, n ∈ N |
| Wartość silni n! |
| K01: | Jeśli n < 2, to silnia(n) ← 1 i zakończ |
| K02: | silnia(n) ← n × silnia(n - 1) i zakończ |
// Rekurencyjne obliczanie silni
//------------------------------
// (C)2026 mgr Jerzy Wałaszek
// I LO w Tarnowie
#include <iostream>
using namespace std;
unsigned long long silnia(int n)
{
if(n < 2)
return 1;
else
return n * silnia(n - 1);
}
// Program główny
//---------------
int main()
{
int n;
cout << "Program oblicza rekurencyjnie silnie z liczby n\n"
"-----------------------------------------------\n"
" (C)2026 mgr Jerzy Walaszek I LO w Tarnowie\n\n"
"n (od 1 do 20) = "; cin >> n;
cout << endl << n << "! = " << silnia(n)
<< endl << endl
<< "Nacisnij Enter...";
system("pause");
return 0;
}
|
Pascal// Rekurencyjne obliczanie silni
//------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I LO w Tarnowie
program silnia_rek;
function silnia(n : cardinal) : qword;
begin
if n < 2 then
silnia := 1
else
silnia := n * silnia(n - 1);
end;
var
n : cardinal;
begin
writeln('Program oblicza rekurencyjnie silnie z liczby n');
writeln('-----------------------------------------------');
writeln(' (C)2005 mgr Jerzy Walaszek I LO w Tarnowie');
writeln;
write('n (od 1 do 20) = '); readln(n);
writeln;
writeln(n,'! = ',silnia(n));
writeln;
write('Nacisnij Enter...'); readln;
end.
|
Basic' Rekurencyjne obliczanie silni
'------------------------------
' (C)2026 mgr Jerzy Wałaszek
' I LO w Tarnowie
FUNCTION silnia(n AS INTEGER) AS ULONGINT
IF n < 2 THEN
RETURN 1
ELSE
RETURN n * silnia(n - 1)
END IF
END FUNCTION
' Program główny
'---------------
DIM AS INTEGER n
PRINT "Silnia z n"
PRINT "----------"
PRINT "(C)2026 mgr Jerzy Walaszek"
PRINT
INPUT "n (od 1 do 20) = "; n
PRINT
PRINT n; "! = "; silnia(n)
PRINT
PRINT
PRINT "Nacisnij Enter..."
SLEEP
END
|
Python
(dodatek)# Rekurencyjne obliczanie silni
#------------------------------
# (C)2026 mgr Jerzy Wałaszek
# I LO w Tarnowie
def silnia(n):
if n < 2:
return 1
else:
return n * silnia(n - 1)
# Program główny
#---------------
print("Program oblicza rekurencyjnie silnię z liczby n")
print("-----------------------------------------------")
print(" (C)2026 mgr Jerzy Wałaszek")
print()
n = int(input("n = "))
print()
print(n,"! = ",silnia(n),sep="")
print()
print()
input("Naciśnij Enter...")
|
| Wynik: |
| Program oblicza
rekurencyjnie silnię z liczby n ----------------------------------------------- (C)2026 mgr Jerzy Wałaszek n = 20 20! = 2432902008176640000 Naciśnij Enter... |
Dzięki rekurencji funkcja wyliczająca wartość silni staje się niezwykle
prosta. Najpierw sprawdzamy warunek zakończenia rekurencji, tzn. sytuację, gdy
wynik dla otrzymanego zestawu danych jest oczywisty. W przypadku silni sytuacja
taka wystąpi dla
Silnia rośnie bardzo szybko. Z tego powodu nasz program wylicza wartość silni tylko dla liczb całkowitych do 20. Silnia 21! wykracza już poza zakres liczb całkowitych 64-bitowych. Ograniczenie to nie dotyczy języka Python, który stosuje duże liczby całkowite.

Wynaleziony w 1945 roku przez Johna von Neumanna algorytm sortowania przez scalanie jest algorytmem rekurencyjnym. Wykorzystuje zasadę dziel i zwyciężaj (ang. divide and conquer), która polega na podziale zadania głównego na zadania mniejsze dotąd, aż rozwiązanie stanie się oczywiste. Algorytm sortujący dzieli porządkowany zbiór na kolejne połowy dopóki taki podział jest możliwy (tzn. podzbiór zawiera co najmniej dwa elementy). Następnie uzyskane w ten sposób części zbioru rekurencyjnie sortuje tym samym algorytmem. Posortowane części łączy ze sobą za pomocą scalania, tak aby wynikowy zbiór był posortowany.
Podstawową operacją algorytmu jest scalanie dwóch zbiorów uporządkowanych w jeden zbiór również uporządkowany. Operację scalania realizujemy wykorzystując pomocniczy zbiór, w którym będziemy tymczasowo odkładać scalane elementy dwóch zbiorów. Ogólna zasada jest następująca:
Przygotuj pusty zbiór tymczasowy
Dopóki żaden ze scalanych zbiorów nie jest pusty, porównuj ze sobą pierwsze elementy każdego z nich i w zbiorze tymczasowym umieszczaj mniejszy z elementów usuwając go jednocześnie ze scalanego zbioru.
W zbiorze tymczasowym umieść zawartość tego scalanego zbioru, który zawiera jeszcze elementy.
Zawartość zbioru tymczasowego przepisz do zbioru wynikowego i zakończ algorytm.
Przykład:
Połączmy za pomocą opisanego algorytmu dwa uporządkowane zbiory:
| Scalane zbiory |
Zbiór tymczasowy |
Opis wykonywanych działań |
[1] 3 6 7 9
2 3 4 6 8
|
|
Porównujemy ze sobą najmniejsze elementy scalanych zbiorów. Ponieważ zbiory te są już uporządkowane, to najmniejszymi elementami będą zawsze ich pierwsze elementy. |
3 6 7 9 2 3 4 6 8 |
[1] |
W zbiorze tymczasowym umieszczamy mniejszy element, w tym przypadku będzie to liczba 1. Jednocześnie element ten zostaje usunięty z pierwszego zbioru |
3 6 7 9 [2] 3 4 6 8 |
1
|
Porównujemy kolejne dwa elementy i mniejszy umieszczamy w zbiorze tymczasowym. |
[3] 6 7 9 3 4 6 8 |
1[2] |
Następne porównanie i w zbiorze tymczasowym umieszczamy liczbę 3. Ponieważ są to elementy równe, to nie ma znaczenia, z którego zbioru weźmiemy element 3. |
6 7 9 [3] 4 6 8 |
1 2[3] |
Teraz do zbioru tymczasowego trafi drugie 3. |
6 7 9 [4] 6 8 |
1 2 3[3] |
W zbiorze tymczasowym umieszczamy mniejszy z porównywanych elementów, czyli liczbę 4. |
[6] 7 9 6 8 |
1 2 3 3[4] |
Porównywane elementy są równe, zatem w zbiorze tymczasowym umieszczamy dowolny z nich. |
7 9 [6] 8 |
1 2 3 3 4[6] |
Teraz drugą liczbę 6. |
[7] 9 8 |
1 2 3 3 4 6[6] |
W zbiorze tymczasowym umieszczamy liczbę 7 |
9 [8] |
1 2 3 3 4 6 6[7] |
Teraz 8 |
[9] |
1 2 3 3 4 6 6 7[8] |
Drugi zbiór jest pusty. Od tego momentu już nie porównujemy, lecz wprowadzamy do zbioru tymczasowego wszystkie pozostałe elementy pierwszego zbioru, w tym przypadku będzie to liczba 9. |
|
|
1 2 3 3 4 6 6 7 8[9] |
Koniec scalania. Zbiór tymczasowy zawiera wszystkie elementy scalanych zbiorów i jest uporządkowany. Możemy w dalszej kolejności przepisać jego zawartość do zbioru docelowego. |
Z podanego przykładu możemy wyciągnąć wniosek, iż operacja scalania dwóch uporządkowanych zbiorów jest dosyć prosta. Diabeł jak zwykle tkwi w szczegółach.
Przed przystąpieniem do wyjaśniania sposobu łączenia dwóch zbiorów
uporządkowanych w jeden zbiór również uporządkowany musimy zastanowić się
nad sposobem reprezentacji danych. Przyjmijmy, iż elementy zbioru będą
przechowywane w jednej tablicy, którą oznaczymy literką d.
Każdy element w tej tablicy będzie posiadał swój numer, czyli
indeks z zakresu
Kolejnym zagadnieniem jest sposób reprezentacji scalanych zbiorów. W przypadku algorytmu sortowania przez scalanie zawsze będą to dwie przyległe połówki zbioru, który został przez ten algorytm podzielony. Co więcej, wynik scalenia ma być umieszczony z powrotem w tym samym zbiorze.
Przykład:
Prześledźmy prosty przykład. Mamy posortować zbiór o postaci:
| Sortowany zbiór | Opis wykonywanych operacji | |||||||
| d[1] | d[2] | d[3] | d[4] | d[5] | d[6] | d[7] | d[8] | |
| 6 | 5 | 4 | 1 | 3 | 7 | 9 | 2 | Zbiór wyjściowy. |
| 6 | 5 | 4 | 1 | 3 | 7 | 9 | 2 | Pierwszy podział. |
| 6 | 5 | 4 | 1 | 3 | 7 | 9 | 2 | Drugi podział |
| 6 | 5 | 4 | 1 | 3 | 7 | 9 | 2 | Trzeci podział. |
| 5 | 6 | 1 | 4 | 3 | 7 | 2 | 9 | Pierwsze scalanie. |
|
1 |
4 | 5 | 6 | 2 | 3 | 7 | 9 | Drugie scalanie. |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | Trzecie scalanie. Koniec. |
Ponieważ w opisywanym tutaj algorytmie sortującym scalane podzbiory są przyległymi do siebie częściami innego zbioru, zatem logiczne będzie użycie do ich definicji indeksów wybranych elementów tych podzbiorów:
| ip | - indeks pierwszego elementu w młodszym podzbiorze |
| is | - indeks pierwszego elementu w starszym podzbiorze |
| ik | - indeks ostatniego elementu w starszym podzbiorze |
Przez podzbiór młodszy rozumiemy podzbiór zawierający elementy o indeksach mniejszych niż indeksy elementów w podzbiorze starszym.
| pozostała część zbioru | ip | ... | is | ... | ik | pozostała część zbioru |
|
młodszy podzbiór |
starszy podzbiór |
|||||
Indeks końcowego elementu młodszej połówki zbioru z łatwością wyliczamy - będzie on o 1 mniejszy od indeksu pierwszego elementu starszej połówki.
Przykład:
|
Młodsza połówka |
Starsza połówka |
| ip = 1 | is = 5 |
| ik = 8 | |
| Młodsza połówka | Starsza połówka | ||
|
Młodsza ćwiartka |
Starsza ćwiartka |
Młodsza ćwiartka |
Starsza ćwiartka |
| ip = 1 | is = 3 | ip = 5 | is = 7 |
| ik = 4 | ik = 8 | ||
| d[ ] | - scalany zbiór |
| ip | - indeks pierwszego elementu w młodszym podzbiorze, ip ∈ N |
| is | - indeks pierwszego elementu w starszym podzbiorze, is ∈ N |
| ik | - indeks ostatniego elementu w starszym podzbiorze, ik ∈ N |
| d[ ] | - scalony zbiór |
| p[ ] | - zbiór pomocniczy, który zawiera tyle samo elementów, co zbiór d[ ]. |
| i1 | - indeks elementów w młodszej połówce zbioru d[ ], i1 ∈ N |
| i2 | - indeks elementów w starszej połówce zbioru d[ ], i2 ∈ N |
| i | - indeks elementów w zbiorze pomocniczym p[ ], i ∈ N |
| K01: | i1 ← ip; i2 ← is; i ← ip |
| K02: | Dla i = ip, ip
+ 1, ..., ik: jeśli (i1 = is) ∨ (i2 ≤ ik i d[i1] > d[i2]), to p[i] ← d[i2]; i2 ← i2 + 1 inaczej p[i] ← d[i1]; i1 ← i1 + 1 |
| K03: | Dla i = ip, ip
+ 1,...,ik: d[i] ← p[i] |
| K04: | Zakończ |
Operacja scalania dwóch podzbiorów wymaga dodatkowej pamięci o rozmiarze
równym sumie rozmiarów scalanych podzbiorów. Dla prostoty na potrzeby naszego
algorytmu zarezerwujemy tablicę p
o rozmiarze równym rozmiarowi zbioru
Parametrami wejściowymi do algorytmu są indeksy ip,
is oraz ik,
które jednoznacznie definiują położenie dwóch podzbiorów do scalenia w obrębie
tablicy
Zmienna i będzie zawierała indeksy elementów
wstawianych do tablicy
Wewnątrz pętli sprawdzamy, czy indeksy i1 i i2 wskazują elementy podzbiorów. Jeśli któryś z nich wyszedł poza dopuszczalny zakres, to dany podzbiór jest wyczerpany - w takim przypadku do tablicy p przepisujemy elementy drugiego podzbioru.
Jeśli żaden z podzbiorów nie jest wyczerpany, porównujemy kolejne elementy z
tych podzbiorów wg indeksów i1
i i2.
Do tablicy
Wtedy przechodzimy do końcowej pętli, która przepisuje ten obszar z tablicy
| d[ ] | - sortowany zbiór |
| ip | - indeks pierwszego elementu w młodszym podzbiorze, ip ∈ N |
| ik | - indeks ostatniego elementu w starszym podzbiorze, ik ∈ N |
| d[ ] | - posortowany zbiór |
| is | - indeks pierwszego elementu w starszym podzbiorze, is ∈ N |
| K01: | is ← (ip + ik + 1) div 2 |
| K02: | Jeśli is - ip > 1, to Sortuj(ip, is - 1) |
| K03: | Jeśli ik - is > 0, to Sortuj(is, ik) |
| K04: | Scalaj(ip, is, ik) |
| K05: | Zakończ |

Algorytm sortowania przez scalanie jest algorytmem rekurencyjnym. Wywołuje
się go z zadanymi wartościami indeksów ip
oraz ik. Przy pierwszym wywołaniu indeksy
te powinny objąć cały zbiór d, zatem
Najpierw algorytm wyznacza indeks is, który wykorzystywany jest do podziału zbioru na dwie połówki:
Następnie sprawdzamy, czy dana połówka zbioru zawiera więcej niż jeden element. Jeśli tak, to rekurencyjnie sortujemy ją tym samym algorytmem.
Po posortowaniu obu połówek zbioru scalamy je za pomocą opisanej wcześniej procedury scalania podzbiorów uporządkowanych i kończymy algorytm. Zbiór jest posortowany.
W przykładowych programach procedurę scalania umieściliśmy bezpośrednio w kodzie algorytmu sortującego, aby zaoszczędzić na wywoływaniu.
C++// Sortowanie przez scalanie
//--------------------------
// (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.
int d[N],p[N];
// Procedura sortująca
//--------------------
void MergeSort(int i_p, int i_k)
{
int i_s,i1,i2,i;
i_s = (i_p + i_k + 1) / 2;
if(i_s - i_p > 1)
MergeSort(i_p, i_s - 1);
if(i_k - i_s > 0)
MergeSort(i_s, i_k);
i1 = i_p; i2 = i_s;
for(i = i_p; i <= i_k; i++)
p[i] = ((i1 == i_s) ||
((i2 <= i_k) &&
(d[i1] > d[i2])))
? d[i2++] : d[i1++];
for(i = i_p; i <= i_k; i++)
d[i] = p[i];
}
// Program główny
//---------------
int main()
{
int i;
cout << " Sortowanie przez scalanie\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
MergeSort(0,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 Przez Scalanie
//--------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie
program Merge_Sort;
const N = 20; // Liczebność zbioru.
var
d,p : array[1..N] of integer;
// Procedura sortująca
//--------------------
procedure MergeSort(i_p,i_k : integer);
var
i_s,i1,i2,i : integer;
begin
i_s := (i_p + i_k + 1) div 2;
if i_s - i_p > 1 then
MergeSort(i_p, i_s - 1);
if i_k - i_s > 0 then
MergeSort(i_s, i_k);
i1 := i_p; i2 := i_s;
for i := i_p to i_k do
if (i1 = i_s) or
((i2 <= i_k) and
(d[i1] > d[i2])) then
begin
p[i] := d[i2]; inc(i2);
end
else
begin
p[i] := d[i1]; inc(i1);
end;
for i := i_p to i_k do
d[i] := p[i];
end;
// Program główny
//---------------
var
i : integer;
begin
writeln(' Sortowanie przez scalanie ');
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
MergeSort(1,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 Przez Scalanie
'--------------------------
' (C)2012 Jerzy Wałaszek
' I Liceum Ogólnokształcące
' w Tarnowie
CONST N = 20 ' Liczebność zbioru.
DIM SHARED d(1 TO N) AS INTEGER
DIM SHARED p(1 TO N) AS INTEGER
DECLARE SUB MergeSort(_
BYVAL i_p AS INTEGER,_
BYVAL i_k AS INTEGER)
DIM i AS INTEGER
PRINT " Sortowanie przez scalanie "
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
MergeSort 1, 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
' Procedura sortująca
'--------------------
PUBLIC SUB MergeSort(_
BYVAL i_p AS INTEGER,_
BYVAL i_k AS INTEGER)
DIM AS INTEGER i_s,i1,i2,i
i_s = (i_p + i_k + 1) \ 2
IF i_s - i_p > 1 THEN
MergeSort i_p, i_s - 1
END IF
IF i_k - i_s > 0 THEN
MergeSort i_s, i_k
END IF
i1 = i_p: i2 = i_s
FOR i = i_p TO i_k
IF (i1 = i_s) OR _
((i2 <= i_k) AND _
(d(i1) > d(i2))) THEN
p(i) = d(i2)
i2 += 1
ELSE
p(i) = d(i1)
i1 += 1
END IF
NEXT
FOR i = i_p TO i_k
d(i) = p(i)
NEXT
END SUB
|
Python
(dodatek)# Sortowanie Przez Scalanie
#--------------------------
# (C)2026 Jerzy Wałaszek
import random
n = 20 # Liczebność zbioru.
d = [random.randrange(100) for i in range(n)]
p = [None] * n
# Procedura sortująca
#--------------------
def MergeSort(i_p,i_k):
i_s = (i_p + i_k + 1) // 2
if i_s - i_p > 1:
MergeSort(i_p, i_s - 1)
if i_k - i_s > 0:
MergeSort(i_s, i_k)
i1 = i_p
i2 = i_s
for i in range(i_p,i_k+1):
if (i1 == i_s) or \
((i2 <= i_k) and \
(d[i1] > d[i2])):
p[i] = d[i2]
i2 += 1
else:
p[i] = d[i1]
i1 += 1
for i in range(i_p,i_k+1):
d[i] = p[i]
# Program główny
#---------------
print(" Sortowanie przez scalanie ")
print("---------------------------")
print(" (C)2026 Jerzy Wałaszek ")
print()
print("Przed sortowaniem:")
print()
for i in range(n):
print("%4d" % (d[i]), end="")
print()
print()
# Sortujemy
MergeSort(0, n-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 przez scalanie --------------------------- (C)2026 Jerzy Wałaszek Przed sortowaniem: 93 70 61 77 76 46 11 87 27 52 58 9 62 94 33 24 32 41 73 28 Po sortowaniu: 9 11 24 27 28 32 33 41 46 52 58 61 62 70 73 76 77 87 93 94 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="frmmergesort">
<h3 style="text-align: center">Sortowanie Przez Scalanie</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 Scalanie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------
var N = 20; // Liczebność zbioru.
var d = new Array(N);
var p = new Array(N);
// Procedura sortująca
//--------------------
function MergeSort(i_p, i_k)
{
var i_s,i1,i2,i;
i_s = Math.floor((i_p + i_k + 1) / 2);
if(i_s - i_p > 1) MergeSort(i_p, i_s - 1);
if(i_k - i_s > 0) MergeSort(i_s, i_k);
i1 = i_p; i2 = i_s;
for(i = i_p; i <= i_k; i++)
p[i] = ((i1 == i_s) || ((i2 <= i_k) && (d[i1] > d[i2]))) ? d[i2++] : d[i1++];
for(i = i_p; i <= i_k; i++) d[i] = p[i];
}
function main()
{
var i,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
MergeSort(0,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> |
| Cechy Algorytmu Sortowania Przez Scalanie | |
| klasa złożoności obliczeniowej optymistyczna | O(n·log(n)) |
| klasa złożoności obliczeniowej typowa | |
| klasa złożoności obliczeniowej pesymistyczna | |
| Sortowanie w miejscu | NIE |
| Stabilność | TAK |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2026 mgr Jerzy Wałaszek |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.