Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Sortowanie listy jednokierunkowej przez scalanie

SPIS TREŚCI
Tematy pomocnicze

Problem

Daną listę jednokierunkową należy posortować rosnąco względem zawartości pól danych jej elementów.

Rozwiązanie

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:

h  –  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 1, h 2  – wskaźniki elementów list pomocniczych

Lista kroków:

K01: Jeśli ( h  = nil ) obrazek ( hnext  = nil ),
to zakończ
lista jest pusta lub jednoelementowa – kończymy
K02: h 1 ← nil przygotowujemy wskaźniki dla podlist
K03: h 2 ← nil  
K04: l_split ( h, h 1, h 2 ) dokonujemy podziału listy na dwie podlisty
K05: l_merge_sort ( h 1 ) pierwszą podlistę sortujemy rekurencyjnie tym samym algorytmem
K06: l_merge_sort ( h 2 ) to samo z drugą podlistą
K07: l_merge ( h 1, h 2, 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 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 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: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.