Sortowanie przez scalanie – algorytm i implementacje

Czyżby nadszedł ten najbardziej wyczekiwany dzień tygodnia? Jak sami wiecie, wraz z nim obowiązkowo pojawia się kolejna część „Piątku z sortowaniem”. Po małym „spinoffie” z prezentacją gotowych metod sortowania w C++ i Javie, wracamy do klasyki. Tym razem dowiemy się czym jest sortowanie przez scalanie (merge sort). Jesteście gotowi?

Sortowanie przez scalanie – algorytm

Algorytm sortowania przez scalanie, to kolejny już z algorytmów, który opiera się na zasadzie „dziel i zwyciężaj”. Można wręcz powiedzieć, że wykorzystuje ją w dość bezpośrednim rozumieniu. Główna zasada działania polega na rekurencyjnym dzieleniu tablicy na podtablice. Dzielenie kończymy, w którym, każda z podtablic w danej grupie jest tablicą jednoelementową. Łączymy je kolejno porównując wartości ich elementów. Dokładny przebieg algorytmu wygląda następująco:

Jeśli indeks prawej części tablicy (r) jest większy od indeksu lewej (l) części tablicy wykonaj następujące kroki:

Znajdź środkowy indeks tablicy (m), ze wzoru m=(l+r)/2 (resztę z dzielenia zaokrąglamy w dół)
Wywołaj sortowanie przez scalanie dla podtablicy o indeksach od l do m
Wywołaj sortowanie przez scalanie dla podtablicy o indeksach od m+1 do r
Połącz podtablicę l – m i m+1 – r, przyrównując przy tym ich elementy – Jeśli element lewej tablicy na aktualnej pozycji jest mniejszy od tego na prawej, wstaw go do tablicy docelowej i zwiększ indeks lewej tablicy. W przeciwnym przypadku, wykonaj analogiczne działanie dla prawej tablicy.

O wielu innych, równie przydatnych algorytmach, przeczytasz w tej książce

Sortowanie przez scalanie – przykład

Aby lepiej zwizualizować sobie zasadę działania algorytmu, prześledźmy prosty przykład. Weźmy zbiór { 4, 2, 8, 6, 5, 1 }. W pierwszej kolejności wyznaczamy indeksy l,r i m:

l = 0
r = 5
m = 2

Następnie dzielimy zbiór wejściowy na dwie podtablice:

L = { 4, 2, 8 } P = { 6, 5, 1 }

Ponownie wykonujemy kolejne podziały lewej podtablicy, do momentu otrzymania następujących zbiorów:

L = ({ 4 }, { 2 }, { 8 }) P = { 6, 5, 1 }

Łączymy elementy lewej części podzbiorów, ustawiając je w porządku rosnącym:

L = { 2,4,8 } P = { 6, 5, 1 }

Wykonujemy podział dla prawej podtablicy:

L = { 2,4,8 } P = ({ 6 }, { 5 }, { 1 })

Łączymy elementy prawej części podtablicy:

L = { 2,4,8 } P = { 1, 5, 6 }

Łączymy obie podtablice:

{1, 2, 4, 5, 6, 8}

W taki sposób otrzymujemy posortowany zbiór wejściowy. By w pełni zrozumieć zasadę działania algorytmu, spójrzcie na poniższą animację:G

Sortowanie przez scalanie – implementacje

C++

//program do sortowania n-elementowej tablicy
//przy pomocy algorytmu sortowania przez scalanie 
//Jan Żwirek

#include &lt;iostream&gt;
using namespace std;

void printTab(int* tab, int n);

void merge(int* tab, int l, int m, int r)
{
	int lSize = m - l + 1;
	int rSize = r - m;

	//Tablice pomocnicze
	int* tabL = new int&#91;lSize];
	int* tabR = new int&#91;rSize];

	// Kopiowanie danych do tablic pomocniczych
	for (int x = 0; x &lt; lSize; x++)
		tabL&#91;x] = tab&#91;l + x];
	for (int y = 0; y &lt; rSize; y++)
		tabR&#91;y] = tab&#91;m + 1 + y];

	int indexL = 0;
	int indexR = 0;
	int currIndex;

	//Łączenie tablic R i L
	for (currIndex = l; indexL &lt; lSize &amp;&amp; indexR &lt; rSize; currIndex++)
	{
		if (tabL&#91;indexL] &lt;= tabR&#91;indexR])
			tab&#91;currIndex] = tabL&#91;indexL++];
		else
			tab&#91;currIndex] = tabR&#91;indexR++];
	}

	//Jeśli w tablicy tabL pozostały jeszcze jakieś elementy
	//kopiujemy je
	while (indexL &lt; lSize)
		tab&#91;currIndex++] = tabL&#91;indexL++];

	//Jeśli w tablicy tabR pozostały jeszcze jakieś elementy
	//kopiujemy je
	while (indexR &lt; rSize)
		tab&#91;currIndex++] = tabR&#91;indexR++];

	delete&#91;] tabL;
	delete&#91;] tabR;
}


void mergeSort(int* tab, int l, int r) {
	if (r &gt; l) {
		int m = (l + r) / 2;
		mergeSort(tab, l, m);
		mergeSort(tab, m + 1, r);
		merge(tab, l, m, r);
	}
}


int main()
{
	int n;

	cout &lt;&lt; "Wprowadz liczbe elementow tablicy: ";
	cin &gt;&gt; n;

	//Dynamiczne tworzenie tablicy
	int* tab = new int&#91;n];

	cout &lt;&lt; "\nWprowadz " &lt;&lt; n &lt;&lt; " liczb do posortowania" &lt;&lt; endl;
	cout &lt;&lt; "Zatwierdz kazda z nich klawiszem Enter:" &lt;&lt; endl;

	for (int x = 0; x &lt; n; x++) {
		cin &gt;&gt; tab&#91;x];
	}

	cout &lt;&lt; endl &lt;&lt; "Tablica przed posortowaniem:" &lt;&lt; endl;
	printTab(tab, n);

	cout &lt;&lt; endl &lt;&lt; "Rozpoczecie sortowania" &lt;&lt; endl;
	mergeSort(tab, 0, n-1);

	cout &lt;&lt; endl &lt;&lt; "Oto tablica po sortowaniu:" &lt;&lt; endl;

	printTab(tab, n);

	delete&#91;] tab;
	system("pause");
	return 0;

}

void printTab(int* tab, int n) {
	cout &lt;&lt; endl;
	for (int x = 0; x &lt; n; x++) {
		cout &lt;&lt; tab&#91;x] &lt;&lt; " | ";
	}
	cout &lt;&lt; endl;
}

100

101

102

//program do sortowania n-elementowej tablicy

//przy pomocy algorytmu sortowania przez scalanie

//Jan Żwirek

#include <iostream>

using namespace std;

void printTab(int* tab, int n);

void merge(int* tab, int l, int m, int r)

{

int lSize = m - l + 1;

int rSize = r - m;

//Tablice pomocnicze

int* tabL = new int[lSize];

int* tabR = new int[rSize];

// Kopiowanie danych do tablic pomocniczych

for (int x = 0; x < lSize; x++)

tabL[x] = tab[l + x];

for (int y = 0; y < rSize; y++)

tabR[y] = tab[m + 1 + y];

int indexL = 0;

int indexR = 0;

int currIndex;

//Łączenie tablic R i L

for (currIndex = l; indexL < lSize && indexR < rSize; currIndex++)

{

if (tabL[indexL] <= tabR[indexR])

tab[currIndex] = tabL[indexL++];

else

tab[currIndex] = tabR[indexR++];

}

//Jeśli w tablicy tabL pozostały jeszcze jakieś elementy

//kopiujemy je

while (indexL < lSize)

tab[currIndex++] = tabL[indexL++];

//Jeśli w tablicy tabR pozostały jeszcze jakieś elementy

//kopiujemy je

while (indexR < rSize)

tab[currIndex++] = tabR[indexR++];

delete[] tabL;

delete[] tabR;

}

void mergeSort(int* tab, int l, int r) {

if (r > l) {

int m = (l + r) / 2;

mergeSort(tab, l, m);

mergeSort(tab, m + 1, r);

merge(tab, l, m, r);

}

int main()

{

int n;

cout << "Wprowadz liczbe elementow tablicy: ";

cin >> n;

//Dynamiczne tworzenie tablicy

int* tab = new int[n];

cout << "\nWprowadz " << n << " liczb do posortowania" << endl;

cout << "Zatwierdz kazda z nich klawiszem Enter:" << endl;

for (int x = 0; x < n; x++) {

cin >> tab[x];

}

cout << endl << "Tablica przed posortowaniem:" << endl;

printTab(tab, n);

cout << endl << "Rozpoczecie sortowania" << endl;

mergeSort(tab, 0, n-1);

cout << endl << "Oto tablica po sortowaniu:" << endl;

printTab(tab, n);

delete[] tab;

system("pause");

return 0;

}

void printTab(int* tab, int n) {

cout << endl;

for (int x = 0; x < n; x++) {

cout << tab[x] << " | ";

}

cout << endl;

}

Java

package matura;

import java.util.Scanner;

public class Main {
	
	
	private static void printArray(int&#91;] tab) {
		System.out.print("| ");
		for(int i = 0; i &lt; tab.length; i++)
		{
			System.out.print(tab&#91;i] + " | ");
		}
		System.out.println();
		System.out.println();
	}
	private static void merge(int&#91;] tab, int l, int m, int r)
	{
		int lSize = m - l + 1;
		int rSize = r - m;
	 
		//Tablice pomocnicze
		int&#91;] tabL = new int&#91;lSize];
		int&#91;] tabR = new int&#91;rSize];
	 
		// Kopiowanie danych do tablic pomocniczych
		for (int x = 0; x &lt; lSize; x++)
			tabL&#91;x] = tab&#91;l + x];
		for (int y = 0; y &lt; rSize; y++)
			tabR&#91;y] = tab&#91;m + 1 + y];
	 
		int indexL = 0;
		int indexR = 0;
		int currIndex;
	 
		//Łączenie tablic R i L
		for (currIndex = l; indexL &lt; lSize &amp;&amp; indexR &lt; rSize; currIndex++)
		{
			if (tabL&#91;indexL] &lt;= tabR&#91;indexR])
				tab&#91;currIndex] = tabL&#91;indexL++];
			else
				tab&#91;currIndex] = tabR&#91;indexR++];
		}
	 
		//Jeśli w tablicy tabL pozostały jeszcze jakieś elementy
		//kopiujemy je
		while (indexL &lt; lSize)
			tab&#91;currIndex++] = tabL&#91;indexL++];
	 
		//Jeśli w tablicy tabR pozostały jeszcze jakieś elementy
		//kopiujemy je
		while (indexR &lt; rSize)
			tab&#91;currIndex++] = tabR&#91;indexR++];
	 
		
	}
	 
	 
	private static void mergeSort(int&#91;] tab, int l, int r) {
		if (r &gt; l) {
			int m = (l + r) / 2;
			mergeSort(tab, l, m);
			mergeSort(tab, m + 1, r);
			merge(tab, l, m, r);
		}
	}
	public static void main(String&#91;] args){ 
		Scanner sc = new Scanner(System.in); //inicjalizujemy Scanner - obiekt pozwalajacy na wczytywanie zmiennych od uzytkownika
		System.out.println("Wprowadz liczbe elementow tablicy: ");
		int n = sc.nextInt();
		int&#91;] arr = new int&#91;n];
		for(int i = 0; i &lt; n; i++) {
			System.out.println("Podaj element nr." + i + ": ");
			arr&#91;i]= sc.nextInt(); //wczytujemy kolejne elementy tablicy
		}
		System.out.println("Oto wprowadzona tablica:");
		printArray(arr);
		System.out.println();
		mergeSort(arr, 0, n-1);
		System.out.println();
		System.out.println("Oto wprowadzona tablica po przesortowaniu:");
		printArray(arr);
		sc.close(); //zwalniamy zasoby
	}
	
}

package matura;

import java.util.Scanner;

public class Main {

private static void printArray(int[] tab) {

System.out.print("| ");

for(int i = 0; i < tab.length; i++)

{

System.out.print(tab[i] + " | ");

}

System.out.println();

}

private static void merge(int[] tab, int l, int m, int r)

{

int lSize = m - l + 1;

int rSize = r - m;

//Tablice pomocnicze

int[] tabL = new int[lSize];

int[] tabR = new int[rSize];

// Kopiowanie danych do tablic pomocniczych

for (int x = 0; x < lSize; x++)

tabL[x] = tab[l + x];

for (int y = 0; y < rSize; y++)

tabR[y] = tab[m + 1 + y];

int indexL = 0;

int indexR = 0;

int currIndex;

//Łączenie tablic R i L

for (currIndex = l; indexL < lSize && indexR < rSize; currIndex++)

{

if (tabL[indexL] <= tabR[indexR])

tab[currIndex] = tabL[indexL++];

else

tab[currIndex] = tabR[indexR++];

}

//Jeśli w tablicy tabL pozostały jeszcze jakieś elementy

//kopiujemy je

while (indexL < lSize)

tab[currIndex++] = tabL[indexL++];

//Jeśli w tablicy tabR pozostały jeszcze jakieś elementy

//kopiujemy je

while (indexR < rSize)

tab[currIndex++] = tabR[indexR++];

}

private static void mergeSort(int[] tab, int l, int r) {

if (r > l) {

int m = (l + r) / 2;

mergeSort(tab, l, m);

mergeSort(tab, m + 1, r);

merge(tab, l, m, r);

}

public static void main(String[] args){

Scanner sc = new Scanner(System.in); //inicjalizujemy Scanner - obiekt pozwalajacy na wczytywanie zmiennych od uzytkownika

System.out.println("Wprowadz liczbe elementow tablicy: ");

int n = sc.nextInt();

int[] arr = new int[n];

for(int i = 0; i < n; i++) {

System.out.println("Podaj element nr." + i + ": ");

arr[i]= sc.nextInt(); //wczytujemy kolejne elementy tablicy

}

System.out.println("Oto wprowadzona tablica:");

printArray(arr);

System.out.println();

mergeSort(arr, 0, n-1);

System.out.println();

System.out.println("Oto wprowadzona tablica po przesortowaniu:");

printArray(arr);

sc.close(); //zwalniamy zasoby

}

Python

def wypisz(tab):  # tworzymy metode do wypiswania zawartosci naszej tablicy
    for el in tab:
        print(el, end=" | ")


def scal(tab, n, m, r): #tworzymy funkcje scalajaca zbiory
    lsize = m - n + 1 #obliczamy wielkosci zbiorow
    rsize = r - m

    left = &#91;0] * lsize  #i tworzymy tablice pomocnicze
    right = &#91;0] * rsize

    for x in range(lsize): #kopiujemy dane do tablic pomocniczych
        left&#91;x] = tab&#91;n + x]
    for y in range(rsize):
        right&#91;y] = tab&#91;m + y + 1]

    leftIndex = 0 #tworzymy pomocnicze zmienne przechowujace indexy
    rightIndex = 0
    currIndex = n
    while leftIndex &lt; lsize and rightIndex &lt; rsize: #a nastepnie z ich pomoca laczymy prawa i lewa tablice
        if left&#91;leftIndex] &lt;= right&#91;rightIndex]:
            tab&#91;currIndex] = left&#91;leftIndex]
            leftIndex += 1
        else:
            tab&#91;currIndex] = right&#91;rightIndex]
            rightIndex += 1
        currIndex += 1

    while leftIndex &lt; lsize: #jezeli w lewej tablicy zostaly jeszcze jakies elementy
        tab&#91;currIndex] = left&#91;leftIndex] #kopiujemy je do wyjsciowej
        currIndex += 1
        leftIndex += 1
    while rightIndex &lt; rsize: #jezeli w prawej tablicy zostaly jeszcze jakies elementy
        tab&#91;currIndex] = right&#91;rightIndex] #kopiujemy je do wyjsciowej
        currIndex += 1
        rightIndex += 1


def sortujScalanie(tab, l, r):
    if r &gt; l:
        m = int((l + r) / 2)
        sortujScalanie(tab, l, m)
        sortujScalanie(tab, m + 1, r)
        scal(tab, l, m, r)


print("Podaj ilosc elementow tablicy:")
a = int(input())
tablica = &#91;]
for i in range(a):
    print("Podaj element nr. ", (i + 1))
    tablica.append(int(input()))
print("Oto twoja tablica:")
wypisz(tablica)
sortujScalanie(tablica, 0, a - 1)
print("Oto twoja tablica po sortowaniu:")
wypisz(tablica)

def wypisz(tab): # tworzymy metode do wypiswania zawartosci naszej tablicy

for el in tab:

print(el, end=" | ")

def scal(tab, n, m, r): #tworzymy funkcje scalajaca zbiory

lsize = m - n + 1 #obliczamy wielkosci zbiorow

rsize = r - m

left = [0] * lsize #i tworzymy tablice pomocnicze

right = [0] * rsize

for x in range(lsize): #kopiujemy dane do tablic pomocniczych

left[x] = tab[n + x]

for y in range(rsize):

right[y] = tab[m + y + 1]

leftIndex = 0 #tworzymy pomocnicze zmienne przechowujace indexy

rightIndex = 0

currIndex = n

while leftIndex < lsize and rightIndex < rsize: #a nastepnie z ich pomoca laczymy prawa i lewa tablice

if left[leftIndex] <= right[rightIndex]:

tab[currIndex] = left[leftIndex]

leftIndex += 1

else:

tab[currIndex] = right[rightIndex]

rightIndex += 1

currIndex += 1

while leftIndex < lsize: #jezeli w lewej tablicy zostaly jeszcze jakies elementy

tab[currIndex] = left[leftIndex] #kopiujemy je do wyjsciowej

currIndex += 1

leftIndex += 1

while rightIndex < rsize: #jezeli w prawej tablicy zostaly jeszcze jakies elementy

tab[currIndex] = right[rightIndex] #kopiujemy je do wyjsciowej

currIndex += 1

rightIndex += 1

def sortujScalanie(tab, l, r):

if r > l:

m = int((l + r) / 2)

sortujScalanie(tab, l, m)

sortujScalanie(tab, m + 1, r)

scal(tab, l, m, r)

print("Podaj ilosc elementow tablicy:")

a = int(input())

tablica = []

for i in range(a):

print("Podaj element nr. ", (i + 1))

tablica.append(int(input()))

print("Oto twoja tablica:")

wypisz(tablica)

sortujScalanie(tablica, 0, a - 1)

print("Oto twoja tablica po sortowaniu:")

wypisz(tablica)

Nieco teorii

Algorytm sortowania, został odkryty przez legendarnego matematyka i informatyka Johna von Neumanna. Jego złożoność czasowa ma wartość O(nlog(n)), co jest bardzo dobrym wynikiem. Jest on bardzo popularny w przypadku sortowania wszelkiego rodzaju list. Możliwe, że wiele z was wykorzystywało go, bez świadomości o jego istnieniu. Jest wykorzystywany m.in. w funkcji Collections.sort() w jęzuku Java.

Podsumowanie

Właśnie wspólnie poznaliśmy zasadę działania sortowania przez scalanie. Znajomość tego popularnego algorytmu, z pewnością przyda Wam się w zrozumieniu wielu funkcji sortowania.

Ku mojej wielkiej przykrości, muszę ogłosić koniec serii „Piątku z sortowaniem”. Nie oznacza to jednak końca pojawiania się materiałów na binarnie.pl! Szykujemy dla Was wiele ciekawych wpisów, które już niedługo ujrzą światło dzienne. Trzymajcie się i do zobaczenia już niedługo!

Binarnie.pl

Sortowanie przez scalanie – algorytm i implementacje