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

©2024 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 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:

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

Lista kroków:

K01: Jeśli (h = nil)obrazek(h→next = nil), ; lista jest pusta lub jednoelementowa
     to zakończ                      ; kończymy
K02: h1 ← nil ; przygotowujemy wskaźniki dla podlist
K03: h2 ← nil
K04: l_split(h,h1,h2) ; dokonujemy podziału listy na dwie podlisty
K05: l_merge_sort(h1) ; obie podlisty sortujemy rekurencyjnie
K06: l_merge_sort(h2) ; tym samym algorytmem
K07: l_merge(h1,h2,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 : 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
Python (dodatek)
# klasa elementu listy
#---------------------
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
#-----------------------------
class slistVar:

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

    # Dodaje nowy element na początek
    def l_push_front(self,v):
        p = slistEl(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
            del p
    # Usuwa element z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            del p

    # 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 = slistVar()
            h2 = slistVar()
            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
  PslistEl = ^slistEl;

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

// Definicja typu obiektowego slistVar
//------------------------------------

  slistVar = object
    public
      head : PslistEl; // 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 : slistVar);
      procedure   l_merge(var h1,h2 : slistVar);
      procedure   l_merge_sort();
  end;

//------------------------
// Metody obiektu slistVar
//------------------------

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

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

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

// Procedura usuwa pierwszy element
//---------------------------------
procedure slistVar.l_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 slistVar.l_split(var h1,h2 : slistVar);
var
  p1, p2 : PslistEl;
  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 slistVar.l_merge(var h1,h2 : slistVar);
var
  p : PslistEl;
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 slistVar.l_merge_sort();
var
  h1,h2 : slistVar;
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 : slistVar; // 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 slistEl
{
  slistEl * next;
  int data;
};

// Definicja typu obiektowego slistVar
//------------------------------------

class slistVar
{
  public:
    slistEl * head;

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

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

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

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

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

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

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

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

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

// Dokonuje podziału listy
//------------------------
void slistVar::l_split(slistVar & h1,
                       slistVar & h2)
{
  slistEl * 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 slistVar::l_merge(slistVar & h1,
                       slistVar & h2)
{
  slistEl * 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 slistVar::l_merge_sort()
{
  slistVar 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()
{
  slistVar 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 slistEl
  next As slistEl Ptr
  data As Integer
End Type

' Typ obiektowy slist
'------------------------------
Type slistVar
  head As slistEl 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 slistVar,_
                      ByRef h2 As slistVar)
  Declare Sub l_merge(ByRef h1 As slistVar,_
                      ByRef h2 As slistVar)
  Declare Sub l_merge_sort()
End Type

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

Dim L As slistVar ' 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 slistVar()
  head = 0
End Constructor

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

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub slistVar.l_print()
 
  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 slistVar.l_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 slistVar.l_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 slistVar.l_split(ByRef h1 As slistVar,_
                     ByRef h2 As slistVar)
  Dim As slistEl 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 slistVar.l_merge(ByRef h1 As slistVar,_
                     ByRef h2 As slistVar)
  Dim p As slistEl 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 slistVar.l_merge_sort()
  Dim As slistVar 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 slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
#-----------------------------
class slistVar:

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

    # Dodaje nowy element na początek
    def l_push_front(self,v):
        p = slistEl(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
            del p
    # Usuwa element z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            del p

    # 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 = slistVar()
            h2 = slistVar()
            self.l_split(h1,h2)
            h1.l_merge_sort()
            h2.l_merge_sort()
            self.l_merge(h1,h2)
    
#---------------
# Program główny
#---------------

L = slistVar() # lista jednokierunkowa

for i in range(200):
    L.l_push_front(random.randrange(-99,100)) 

L.l_print()
print()

L.l_merge_sort()

L.l_print()

del L
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 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 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.