Algorytmy i Struktury Danych - Sortowanie listy przez scalanie

Zasada sortowania przez scalanie (ang. merge sort) jest bardzo prosta. Jeśli dana lista posiada więcej niż jeden element, to dzielimy ją na dwie podlisty, po czym sortujemy rekurencyjnie każdą z tych podlist i na końcu scalamy je.

Dlaczego to działa? Otóż kolejne podziały dadzą nam w końcu listy jednoelementowe, które są zawsze uporządkowane. Teraz idąc w górę scalamy te listy i otrzymujemy na końcu listę posortowaną. Oto prosty przykład:

[9 8 3 7 5 8 3 9 2 1 0 3 2 5 6 9]	Oto lista wejściowa.
[9 3 5 3 2 0 2 6] [8 7 8 9 1 3 5 9]	Listę dzielimy na dwie podlisty.
[9 5 2 2] [3 3 0 6] [8 8 1 5] [7 9 3 9]	Każdą z podlist znów dzielimy na podlisty.
[9 2] [5 2] [3 0] [3 6] [8 1] [8 5] [7 3] [9 9]	Kontynuujemy podziały…
[9] [2] [5] [2] [3] [0] [3] [6] [8] [1] [8] [5] [7] [3] [9] [9]	Otrzymujemy w końcu listy jednoelementowe, które są automatycznie posortowane.
[9] + [2] [5] + [2] [3] + [0] [3] + [6] [8] + [1] [8] + [5] [7] + [3] [9] + [9]	Teraz przystępujemy do scalania par list. Ponieważ są one posortowane, to po scaleniu również otrzymamy listy posortowane.
[2 9] + [2 5] [0 3] + [3 6] [1 8] + [5 8] [3 7] + [9 9]	Kontynuujemy scalanie…
[2 2 5 9] + [0 3 3 6] [1 5 8 8] + [3 7 9 9]	Kontynuujemy scalanie…
[0 2 2 3 3 5 6 9] + [1 3 5 7 8 8 9 9]	Kontynuujemy scalanie…
[0 1 2 2 3 3 3 5 5 6 7 8 8 9 9 9]	I na koniec otrzymujemy listę posortowaną.

Algorytm sortowania listy jednokierunkowej przez scalanie

Wejście:

adres początku listy do posortowania

Wyjście:

lista wskazywana przez h posortowana rosnąco względem zawartości pól danych elementów

Zmienne pomocnicze:

h₁, h₂

wskaźniki elementów list pomocniczych

Lista kroków:

K01:	Jeśli (h = nil) (h→next = nil), to zakończ	lista jest pusta lub jednoelementowa – kończymy
K02:	h₁ ← nil	przygotowujemy wskaźniki dla podlist
K03:	h₂ ← nil
K04:	l_split (h, h₁, h₂)	dokonujemy podziału listy na dwie podlisty
K05:	l_merge_sort (h₁)	pierwszą podlistę sortujemy rekurencyjnie tym samym algorytmem
K06:	l_merge_sort (h₂)	to samo z drugą podlistą
K07:	l_merge (h₁, h₂, h)	scalamy obie podlisty, lista h jest posortowana
K08:	Zakończ

Algorytm sortowania przez scalanie posiada logarytmiczno liniową klasę złożoności obliczeniowej O (n·logn), jednakże z powodu rekurencyjnego charakteru wymaga on O (n) pamięci na adresy list pośrednich – same elementy nie są dublowane. Nie nadaje się zatem do sortowania bardzo długich list.

Pascal

procedure l_merge_sort (var h : PslistEl);
var
  h1, h2 : PslistEl;
begin
  if(h <> nil) and (h^.next <> nil) then
  begin
    h1 := nil;
    h2 := nil;
    l_split (h, h1, h2);
    l_merge_sort (h1);
    l_merge_sort (h2);
    l_merge (h1, h2, h);
  end;
end;

C++

void l_merge_sort (slistEl * & h)
{
  slistEl * h1, h2;
  if(h && h->next)
  {
    h1 = h2 = NULL;
    l_split (h, h1, h2);
    l_merge_sort (h1);
    l_merge_sort (h2);
    l_merge (h1, h2, h);
  }
}

Basic

Sub l_merge_sort (ByRef h As slistEl Ptr)
  Dim As slistEl Ptr h1, h2
  if(h <> 0) AndAlso (h->next <> 0) Then
    h1 = 0
    h2 = 0
    l_split (h, h1, h2);
    l_merge_sort (h1);
    l_merge_sort (h2);
    l_merge (h1, h2, h);
  End If
End Sub

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program tworzy listę 200 pseudolosowych liczb całkowitych, po czym sortuje ją przez scalanie. Program wykorzystuje obiekt listy jednokierunkowej. Typ danych elementów listy został zmieniony ze znakowego na całkowity.

Pascal

// Sortowanie listy jednokierunkowej przez scalanie
// Data: 25.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------------

program slist_merge_sort;

// Typ elementów listy
//--------------------
type
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : integer;
  end;

// Definicja typu obiektowego slist
//---------------------------------

  slist = object
    public
      head : PslistEl; // początek listy

      constructor init;
      destructor  destroy;
      procedure   printl;
      procedure   push_front (v : integer);
      procedure   pop_front;
      procedure   split (var l1, l2 : slist);
      procedure   merge (var l1, l2 : slist);
      procedure   merge_sort();
  end;

//---------------------
// Metody obiektu slist
//---------------------

// Konstruktor - inicjuje pole head
//---------------------------------
constructor slist.init;
begin
  head := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor slist.destroy;
begin
  while head <> nil do pop_front;
end;


// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure slist.printl;
var
  p : PslistEl;
begin
  p := head;
  while p <> nil do
  begin
    write (p^.data:4);
    p := p^.next;
  end;
  writeln;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure slist.push_front (v : integer);
var
  p : PslistEl;
begin
  new (p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure slist.pop_front;
var
  p : PslistEl;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    dispose (p);
  end;
end;

// Dokonuje podziału listy
//------------------------
procedure slist.split (var l1, l2 : slist);
var
  p1, p2 : PslistEl;
  s : boolean;
begin
  s := false;
  l1.push_front (0);
  l2.push_front (0);
  p1 := l1.head;
  p2 := l2.head;
  while head <> nil do
  begin
    if s then
    begin
      p2^.next := head;
      p2 := p2^.next;
    end
    else
    begin
      p1^.next := head;
      p1 := p1^.next;
    end;
    head := head^.next;
    s := not s;
  end;
  p1^.next := nil;
  p2^.next := nil;
  l1.pop_front();
  l2.pop_front();
end;

// Scala dwie obce listy
//----------------------
procedure slist.merge (var l1, l2 : slist);
var
  p : PslistEl;
begin
  push_front (0);
  p := head;
  while(l1.head <> nil) and (l2.head <> nil) do
  begin
    if l1.head^.data > l2.head^.data then
    begin
      p^.next := l2.head;
      l2.head := l2.head^.next;
    end
    else
    begin
      p^.next := l1.head;
      l1.head := l1.head^.next;
    end;
    p := p^.next;
  end;
  while l1.head <> nil do
  begin
    p^.next := l1.head;
    l1.head := l1.head^.next;
    p := p^.next;
  end;
  while l2.head <> nil do
  begin
    p^.next := l2.head;
    l2.head := l2.head^.next;
    p := p^.next;
  end;
  pop_front();
end;

// Sortuje listę przez scalanie
//-----------------------------
procedure slist.merge_sort();
var
  h1, h2 : slist;
begin
  if(head <> nil) and (head^.next <> nil) then
  begin
    h1.init;
    h2.init;
    split (h1, h2);
    h1.merge_sort;
    h2.merge_sort;
    merge (h1, h2);
  end;
end;

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

var
  L : slist; // obiekt listy jednokierunkowej
  i : integer;

begin
  Randomize;

  L.init;

  for i := 1 to 200 do L.push_front (random (199) - 99);
  L.printl;

  writeln;

  L.merge_sort;
  L.printl;

  L.destroy;
end.

C++

// Sortowanie listy jednokierunkowej przez scalanie
// Data: 25.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

// Typ elementów listy
//--------------------
struct slistEl
{
  slistEl * next;
  int data;
};

// Definicja typu obiektowego slist
//---------------------------------

class slist
{
  public:
    slistEl * head;

    slist();  // konstruktor
    ~slist(); // destruktor
    void printl();
    void push_front (char v);
    void pop_front();
    void split (slist & l1, slist & l2);
    void merge (slist & l1, slist & l2);
    void merge_sort();
};

// Konstruktor listy
//------------------
slist::slist()
{
  head = NULL;
}

// Destruktor listy
//-----------------
slist::~slist()
{
  while(head) pop_front();
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void slist::printl()
{
  slistEl * p;

  for(p = head; p; p = p->next) cout << setw (4) << p->data;
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void slist::push_front (char v)
{
  slistEl * p;

  p = new slistEl;
  p->next = head;
  p->data = v;
  head = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void slist::pop_front()
{
  slistEl * p = head;

  if(p)
  {
    head = p->next;
    delete p;
  }
}

// Dokonuje podziału listy
//------------------------
void slist::split (slist & l1, slist & l2)
{
  slistEl * p1, * p2;
  bool s = false;
  l1.push_front (0);
  l2.push_front (0);
  p1 = l1.head;
  p2 = l2.head;
  while(head)
  {
    if(s)
    {
      p2->next = head;
      p2 = p2->next;
    }
    else
    {
      p1->next = head;
      p1 = p1->next;
    }
    head = head->next;
    s = !s;
  }
  p1->next = p2->next = NULL;
  l1.pop_front();
  l2.pop_front();
}

// Scala dwie obce listy
//----------------------
void slist::merge (slist & l1, slist & l2)
{
  slistEl * p;
  push_front (0);
  p = head;
  while(l1.head && l2.head)
  {
    if(l1.head->data > l2.head->data)
    {
      p->next = l2.head;
      l2.head = l2.head->next;
    }
    else
    {
      p->next = l1.head;
      l1.head = l1.head->next;
    }
    p = p->next;
  }
  while(l1.head)
  {
    p->next = l1.head;
    l1.head = l1.head->next;
    p  = p->next;
  }
  while(l2.head)
  {
    p->next = l2.head;
    l2.head = l2.head->next;
    p  = p->next;
  }
  pop_front();
}

// Sortuje listę przez scalanie
//-----------------------------
void slist::merge_sort()
{
  slist h1, h2;
  if(head && head->next)
  {
    split (h1, h2);
    h1.merge_sort();
    h2.merge_sort();
    merge (h1, h2);
  }
}

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

int main()
{
  slist L; // obiekt listy jednokierunkowej
  int i;

  srand (time(NULL));

  for(i = 0; i < 200; i++) L.push_front (rand() % 199 - 99);
  L.printl();

  cout << endl;

  L.merge_sort();
  L.printl();

  return 0;
}

Basic

' Sortowanie listy jednokierunkowej przez scalanie
' Data: 25.02.2012
' (C)2020 mgr Jerzy Wałaszek
'-------------------------------------------------

' Typ elementów listy
'--------------------
Type slistEl
  next As slistEl Ptr
  data As Integer
End Type

' Typ obiektowy slist
'------------------------------
Type slist
  head As slistEl Ptr
 
  Declare Constructor()
  Declare Destructor()
  Declare Sub printl()
  Declare Sub push_front (v As Integer)
  Declare Sub pop_front()
  Declare Sub split (ByRef l1 As slist, ByRef l2 As slist)
  Declare Sub merge (ByRef l1 As slist, ByRef l2 As slist)
  Declare Sub merge_sort()
End Type

'---------------
' Program główny
'---------------

Dim L As slist     ' obiekt listy jednokierunkowej
Dim i As Integer

Randomize

For i = 1 To 200
	L.push_front (Int (Rnd() * 199) - 99)
Next
L.printl()

Print

L.merge_sort()
L.printl()

End

' Konstruktor listy
'-------------------
Constructor slist()
  head = 0
End Constructor

' Destruktor listy
'-----------------
Destructor slist()
  While head
    pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub slist.printl()
 
  Dim p As slistEl Ptr = head
 
  While p
    Print Using "####";p->Data;
    p = p->next
  Wend
  Print
End Sub

' Procedura dołączania na początek listy
'---------------------------------------
Sub slist.push_front (v As Integer)

  Dim p As slistEl Ptr

  p = new slistEl
  p->next = head
  p->data = v
  head = p
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub slist.pop_front()

  Dim p As slistEl Ptr

  p = head         ' zapamiętujemy początek
  If p Then
    head = p->next ' nowy początek
    Delete p       ' usuń element z pamięci
  End If
End Sub

' Dokonuje podziału listy
'------------------------
Sub slist.split (ByRef l1 As slist, ByRef l2 As slist)
  Dim As slistEl Ptr p1, p2
  Dim As Integer s = 0
  l1.push_front (0)
  l2.push_front (0)
  p1 = l1.head
  p2 = l2.head
  While head
    If s = 0 Then
      p1->next = head
      p1 = p1->next
    Else
      p2->next = head
      p2 = p2->next
    End If
    head = head->next
    s = s Xor 1
  Wend
  p1->next = 0
  p2->next = 0
  l1.pop_front()
  l2.pop_front()
End Sub

' Scala dwie obce listy
'----------------------
Sub slist.merge (ByRef l1 As slist, ByRef l2 As slist)
  Dim p As slistEl Ptr
  push_front (0)
  p = head
  while(l1.head <> 0) AndAlso (l2.head <> 0)
    If l1.head->data > l2.head->data Then
      p->next = l2.head
      l2.head = l2.head->next
    Else
      p->next = l1.head
      l1.head = l1.head->next
    End If
    p = p->next
  Wend
  While l1.head
    p->next = l1.head
    l1.head = l1.head->next
    p  = p->next
  Wend
  While l2.head
    p->next = l2.head
    l2.head = l2.head->next
    p  = p->next
  Wend
  pop_front()
End Sub

' Sortuje listę przez scalanie
'-----------------------------
Sub slist.merge_sort()
  Dim As slist h1, h2
  if(head <> 0) AndAlso (head->next <> 0) Then
    split (h1, h2)
    h1.merge_sort()
    h2.merge_sort()
    merge (h1, h2)
  End If
End Sub

Wynik:

74 -82 -74 -39 -98 72 -78 -3 90 47 53 84 84 -44 -9 28 53 62 -5 72
-99 -64 69 -43 -59 22 22 -98 38 71 -49 80 -93 -14 72 -92 -19 -25 65 31
0 61 53 36 99 -40 93 -83 26 24 -54 2 -3 -37 -40 45 -73 -26 -78 58
-31 65 62 -14 -37 46 -30 12 -96 -33 -41 -26 -82 -86 98 34 -66 5 54 8
-83 -2 88 87 24 -72 -19 27 68 8 -60 39 7 44 92 -13 33 -38 -51 -25
43 59 -75 80 25 -69 17 -83 50 26 67 60 51 -95 -10 -10 12 69 -60 -53
82 11 77 -12 -87 86 -70 61 6 14 -30 15 76 23 -40 12 -69 3 -82 -17
93 37 -7 13 14 64 -91 51 83 58 -30 -41 -82 13 74 -49 50 94 -95 -39
-62 70 12 -30 -55 -3 49 14 -98 64 50 -69 -86 -32 -86 -20 -40 44 96 -36
13 -29 -39 78 -24 40 7 95 -10 42 46 -5 38 27 -37 81 -26 7 -26 -90

-99 -98 -98 -98 -96 -95 -95 -93 -92 -91 -90 -87 -86 -86 -86 -83 -83 -83 -82 -82
-82 -82 -78 -78 -75 -74 -73 -72 -70 -69 -69 -69 -66 -64 -62 -60 -60 -59 -55 -54
-53 -51 -49 -49 -44 -43 -41 -41 -40 -40 -40 -40 -39 -39 -39 -38 -37 -37 -37 -36
-33 -32 -31 -30 -30 -30 -30 -29 -26 -26 -26 -26 -25 -25 -24 -20 -19 -19 -17 -14
-14 -13 -12 -10 -10 -10 -9 -7 -5 -5 -3 -3 -3 -2 0 2 3 5 6 7
7 7 8 8 11 12 12 12 12 13 13 13 14 14 14 15 17 22 22 23
24 24 25 26 26 27 27 28 31 33 34 36 37 38 38 39 40 42 43 44
44 45 46 46 47 49 50 50 50 51 51 53 53 53 54 58 58 59 60 61
61 62 62 64 64 65 65 67 68 69 69 70 71 72 72 72 74 74 76 77
78 80 80 81 82 83 84 84 86 87 88 90 92 93 93 94 95 96 98 99

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.

Sortowanie listy jednokierunkowej przez scalanie