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 tak, aby otrzymać listę posortowaną.

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. Każdą z podlist znów dzielimy na podlisty.

[9 5 2 2] [3 3 0 6] [8 8 1 5] [7 9 3 9]

Kontynuujemy podziały…

[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ą zawsze 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

Elementy pomocnicze:

h₁, h₂ : wskaźniki elementów list pomocniczych.
l_split(L, L₁, L₂) : dzieli listę L na dwie podlisty L₁ i L₂.
l_merge(L₁, L₂, L) : scala dwie listy posortowane L₁ i L₂ w jedną listę posortowaną L.
l_merge_sort(L) : poniższy algorytm sortowania listy L.

Lista kroków:

K01: Jeśli h = nil  h→next = nil, ; lista jest pusta lub jednoelementowa
     to zakończ ; 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₁) ; obie podlisty sortujemy rekurencyjnie
K06: l_merge_sort(h₂) ; tym samym algorytmem
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 liniowej klasy O(n) zużycia 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 : PSLel);
var
  h1, h2 : PSLel;
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(SLel * & h)
{
  SLel * 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 SLel Ptr)
  Dim As SLel 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

Python (dodatek)

# klasa elementu listy
#---------------------
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy jednokierunkowej
#-----------------------------
class SLvar:


    # Konstruktor
    def __init__(self):
        self.head = None


    # Dodaje nowy element na początek
    def l_push_front(self, v):
        p = SLel(v)
        p.next = self.head
        self.head = p


    # Usuwa element z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            p = None


    # Usuwa element z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            p = None


    # Rozdziela na dwie listy
    def l_split(self, h1, h2):
        s = False
        h1.l_push_front(0)
        h2.l_push_front(0)
        p1 = h1.head
        p2 = h2.head
        while self.head:
            if s:
                p2.next = self.head
                p2 = p2.next
            else:
                p1.next = self.head
                p1 = p1.next
            self.head = self.head.next
            s = not s
        p1.next = None
        p2.next = None
        h1.l_pop_front()
        h2.l_pop_front()


    # łączy listy posortowane
    def l_merge(self, h1, h2):
        self.l_push_front(0)
        p = self.head
        while h1.head and h2.head:
            if h1.head.data > h2.head.data:
                p.next = h2.head
                h2.head = h2.head.next
            else:
                p.next = h1.head
                h1.head = h1.head.next
            p = p.next
        if h1.head:
            p.next = h1.head
            h1.head = None
        if h2.head:
            p.next = h2.head
            h2.head = None
        self.l_pop_front()


    # sortuje przez scalanie
    def l_merge_sort(self):
        if self.head and self.head.next:
            h1 = SLvar()
            h2 = SLvar()
            self.l_split(h1, h2)
            h1.l_merge_sort()
            h2.l_merge_sort()
            self.l_merge(h1, h2)

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
  PSLel = ^SLel;

  SLel =  record
    next  : PSLel;
    data  : integer;
  end;

// Definicja typu obiektowego SLvar
//------------------------------------

  SLvar = object
    public
      head : PSLel; // początek listy

      constructor init;
      destructor  destroy;
      procedure   l_print;
      procedure   l_push_front(v : integer);
      procedure   l_pop_front;
      procedure   l_split(var h1, h2 : SLvar);
      procedure   l_merge(var h1, h2 : SLvar);
      procedure   l_merge_sort();
  end;

//------------------------
// Metody obiektu SLvar
//------------------------

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

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

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure SLvar.l_print;
var
  p : PSLel;
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 SLvar.l_push_front(v : integer);
var
  p : PSLel;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

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

// Dokonuje podziału listy
//------------------------
procedure SLvar.l_split(var h1, h2 : SLvar);
var
  p1, p2 : PSLel;
  s : boolean;
begin
  s := false;
  h1.l_push_front(0);
  h2.l_push_front(0);
  p1 := h1.head;
  p2 := h2.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;
  h1.l_pop_front();
  h2.l_pop_front();
end;

// Scala dwie obce listy
//----------------------
procedure SLvar.l_merge(var h1, h2 : SLvar);
var
  p : PSLel;
begin
  l_push_front(0);
  p := head;
  while(h1.head <> nil) and (h2.head <> nil) do
  begin
    if h1.head^.data > h2.head^.data then
    begin
      p^.next := h2.head;
      h2.head := h2.head^.next;
    end
    else
    begin
      p^.next := h1.head;
      h1.head := h1.head^.next;
    end;
    p := p^.next;
  end;
  if h1.head <> nil then
  begin
    p^.next := h1.head;
    h1.head := nil;
  end;
  if h2.head <> nil then
  begin
    p^.next := h2.head;
    h2.head := nil;
  end;
  l_pop_front();
end;

// Sortuje listę przez scalanie
//-----------------------------
procedure SLvar.l_merge_sort();
var
  h1, h2 : SLvar;
begin
  if(head <> nil) and (head^.next <> nil) then
  begin
    h1.init;
    h2.init;
    l_split(h1, h2);
    h1.l_merge_sort;
    h2.l_merge_sort;
    l_merge(h1, h2);
  end;
end;

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

var
  L : SLvar; // lista jednokierunkowa
  i : integer;

begin
  Randomize;

  L.init;

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

  writeln;

  L.l_merge_sort;
  L.l_print;

  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 SLel
{
  SLel * next;
  int data;
};

// Definicja typu obiektowego SLvar
//------------------------------------

class SLvar
{
  public:
    SLel * head;

    SLvar();  // konstruktor
    ~SLvar(); // destruktor
    void l_print();
    void l_push_front(char v);
    void l_pop_front();
    void l_split(SLvar & h1, SLvar & h2);
    void l_merge(SLvar & h1, SLvar & h2);
    void l_merge_sort();
};

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

// Destruktor listy
//-----------------
SLvar::~SLvar()
{
  while(head) l_pop_front();
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void SLvar::l_print()
{
  SLel * p;

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

// Procedura dołączania na początek listy
//---------------------------------------
void SLvar::l_push_front(char v)
{
  SLel * p;

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

// Procedura usuwa pierwszy element
//---------------------------------
void SLvar::l_pop_front()
{
  SLel * p = head;

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

// Dokonuje podziału listy
//------------------------
void SLvar::l_split(SLvar & h1, 
                       SLvar & h2)
{
  SLel * p1, * p2;
  bool s = false;
  h1.l_push_front(0);
  h2.l_push_front(0);
  p1 = h1.head;
  p2 = h2.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;
  h1.l_pop_front();
  h2.l_pop_front();
}

// Scala dwie obce listy
//----------------------
void SLvar::l_merge(SLvar & h1, 
                       SLvar & h2)
{
  SLel * p;
  l_push_front(0);
  p = head;
  while(h1.head && h2.head)
  {
    if(h1.head->data > h2.head->data)
    {
      p->next = h2.head;
      h2.head = h2.head->next;
    }
    else
    {
      p->next = h1.head;
      h1.head = h1.head->next;
    }
    p = p->next;
  }
  if(h1.head)
  {
    p->next = h1.head;
    h1.head = NULL;
  }
  if(h2.head)
  {
    p->next = h2.head;
    h2.head = NULL;
  }
  l_pop_front();
}

// Sortuje listę przez scalanie
//-----------------------------
void SLvar::l_merge_sort()
{
  SLvar h1, h2;
  if(head && head->next)
  {
    l_split(h1, h2);
    h1.l_merge_sort();
    h2.l_merge_sort();
    l_merge(h1, h2);
  }
}

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

int main()
{
  SLvar L; // lista jednokierunkowa
  int i;

  srand(time(NULL));

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

  cout << endl;

  L.l_merge_sort();
  L.l_print();

  return 0;
}

Basic

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

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

' Typ obiektowy slist
'------------------------------
Type SLvar
  head As SLel Ptr
 
  Declare Constructor()
  Declare Destructor()
  Declare Sub l_print()
  Declare Sub l_push_front(v As Integer)
  Declare Sub l_pop_front()
  Declare Sub l_split(ByRef h1 As SLvar, _
                      ByRef h2 As SLvar)
  Declare Sub l_merge(ByRef h1 As SLvar, _
                      ByRef h2 As SLvar)
  Declare Sub l_merge_sort()
End Type

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

Dim L As SLvar ' lista jednokierunkowa
Dim i As Integer

Randomize

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

Print

L.l_merge_sort()
L.l_print()

End

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

' Destruktor listy
'-----------------
Destructor SLvar()
  While head
    l_pop_front()
  Wend
End Destructor

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

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

  Dim p As SLel Ptr

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

' Procedura usuwa pierwszy element
'---------------------------------
Sub SLvar.l_pop_front()

  Dim p As SLel 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 SLvar.l_split(ByRef h1 As SLvar, _
                     ByRef h2 As SLvar)
  Dim As SLel Ptr p1, p2
  Dim As Integer s = 0
  h1.l_push_front(0)
  h2.l_push_front(0)
  p1 = h1.head
  p2 = h2.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
  h1.l_pop_front()
  h2.l_pop_front()
End Sub

' Scala dwie obce listy
'----------------------
Sub SLvar.l_merge(ByRef h1 As SLvar, _
                     ByRef h2 As SLvar)
  Dim p As SLel Ptr
  l_push_front(0)
  p = head
  while(h1.head <> 0) AndAlso (h2.head <> 0)
    If h1.head->data > h2.head->data Then
      p->next = h2.head
      h2.head = h2.head->next
    Else
      p->next = h1.head
      h1.head = h1.head->next
    End If
    p = p->next
  Wend
  If h1.head then
    p->next = h1.head
    h1.head = 0
  End If
  If h2.head then
    p->next = h2.head
    h2.head = 0
  End If
  l_pop_front()
End Sub

' Sortuje listę przez scalanie
'-----------------------------
Sub SLvar.l_merge_sort()
  Dim As SLvar h1, h2
  if(head <> 0) AndAlso (head->next <> 0) Then
    l_split(h1, h2)
    h1.l_merge_sort()
    h2.l_merge_sort()
    l_merge(h1, h2)
  End If
End Sub

Python (dodatek)

# Sortowanie listy jednokierunkowej
# przez scalanie
# Data: 28.05.2024
# (C)2024 mgr Jerzy Wałaszek
# ----------------------------------

import random


# klasa elementu listy
# ---------------------
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy jednokierunkowej
# -----------------------------
class SLvar:


    # Konstruktor
    def __init__(self):
        self.head = None


    # Dodaje nowy element na początek
    def l_push_front(self, v):
        p = SLel(v)
        p.next = self.head
        self.head = p


    # Usuwa element z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            p = None


    # Usuwa element z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            p = None


    # wyświetla listę
    def l_print(self):
        p = self.head
        while p:
            print("%4d" % p.data, end="")
            p = p.next
        print()


    # Rozdziela na dwie listy
    def l_split(self, h1, h2):
        s = False
        h1.l_push_front(0)
        h2.l_push_front(0)
        p1 = h1.head
        p2 = h2.head
        while self.head:
            if s:
                p2.next = self.head
                p2 = p2.next
            else:
                p1.next = self.head
                p1 = p1.next
            self.head = self.head.next
            s = not s
        p1.next = None
        p2.next = None
        h1.l_pop_front()
        h2.l_pop_front()


    # łączy listy posortowane
    def l_merge(self, h1, h2):
        self.l_push_front(0)
        p = self.head
        while h1.head and h2.head:
            if h1.head.data > h2.head.data:
                p.next = h2.head
                h2.head = h2.head.next
            else:
                p.next = h1.head
                h1.head = h1.head.next
            p = p.next
        if h1.head:
            p.next = h1.head
            h1.head = None
        if h2.head:
            p.next = h2.head
            h2.head = None
        self.l_pop_front()


    # sortuje przez scalanie
    def l_merge_sort(self):
        if self.head and self.head.next:
            h1 = SLvar()
            h2 = SLvar()
            self.l_split(h1, h2)
            h1.l_merge_sort()
            h2.l_merge_sort()
            self.l_merge(h1, h2)


# ---------------
# Program główny
# ---------------

sl = SLvar()  # lista jednokierunkowa
for i in range(200):
    sl.l_push_front(random.randrange(-99, 100))
sl.l_print()
print()
sl.l_merge_sort()
sl.l_print()

Wynik:

 -16 -37  45  81   1  76 -45 -63  14 -17  42   8  75  64  90 -98  62  87 -27 -17
 -79  79  74  17  86 -31  28  13   8  33  -9 -23   2 -26 -27  70 -20  13 -58  16
  79  -9  60  30 -55  53 -31   1  -3 -71 -14  42 -64  67 -57 -31 -46  29  34 -52
  31   8 -12 -48 -81 -50  15 -27  40  -4   7 -45  85  81  51  94  88   4  71 -27
  17  93  46  71 -54 -28   0 -76 -81  58  42  35  80  97  74  35 -92  57 -82 -45
 -26   2  12 -33 -55  15  84  92  59  24 -10 -69 -25 -53  81  35  33  31  30 -71
  39 -86 -74  48  76 -53  36 -24  -9  85  25  27  73 -92 -81 -89 -64  43 -56  18
  88  94  66  -8 -24  39  89 -85  41  -6  82  32 -21  11  86 -55 -33  49 -87  90
 -86 -46  17  22  53 -78 -20  55 -22  32  22  98 -55 -97 -91  58  28  27  26  42
  56 -42  42 -54 -58 -82 -25  11  38 -86 -80 -81 -64 -90  93  -7  77   7 -66  82

 -98 -97 -92 -92 -91 -90 -89 -87 -86 -86 -86 -85 -82 -82 -81 -81 -81 -81 -80 -79
 -78 -76 -74 -71 -71 -69 -66 -64 -64 -64 -63 -58 -58 -57 -56 -55 -55 -55 -55 -54
 -54 -53 -53 -52 -50 -48 -46 -46 -45 -45 -45 -42 -37 -33 -33 -31 -31 -31 -28 -27
 -27 -27 -27 -26 -26 -25 -25 -24 -24 -23 -22 -21 -20 -20 -17 -17 -16 -14 -12 -10
  -9  -9  -9  -8  -7  -6  -4  -3   0   1   1   2   2   4   7   7   8   8   8  11
  11  12  13  13  14  15  15  16  17  17  17  18  22  22  24  25  26  27  27  28
  28  29  30  30  31  31  32  32  33  33  34  35  35  35  36  38  39  39  40  41
  42  42  42  42  42  43  45  46  48  49  51  53  53  55  56  57  58  58  59  60
  62  64  66  67  70  71  71  73  74  74  75  76  76  77  79  79  80  81  81  81
  82  82  84  85  85  86  86  87  88  88  89  90  90  92  93  93  94  94  97  98

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

Problem

Rozwiązanie

Algorytm sortowania listy jednokierunkowej przez scalanie

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy