Sortowanie przez scalanie za pomocą stosów


Tematy pokrewne   Podrozdziały
Podstawowe operacje na tablicach
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Sortowanie przez wstawianie z wykorzystaniem listy jednokierunkowej
Stosy
Podstawowe pojęcia dotyczące stosów. Realizacja stosu za pomocą tablicy i listy jednokierunkowej
Przeliczanie liczb na zapis w innym systemie pozycyjnym
Odwrotna Notacja Polska
Sortowanie przez wstawianie za pomocą stosów
Sortowanie
  Zadania

Problem

Posortować rosnąco ciąg danych wejściowych za pomocą stosowego algorytmu sortowania przez wstawianie.



Sortowanie przez wstawianie (ang. insertion sort) jest algorytmem sortującym o czasowej złożoności obliczeniowej O(n2). Postać listową opisaliśmy w jednym z poprzednich rozdziałów. Zasada działania sortowania przez wstawianie z wykorzystaniem dwóch stosów jest następująca:

 

Tworzymy dwa stosy, które nazwiemy SL – stos lewy i SP – stos prawy.

Na stosie SL umieszczamy wartość najmniejszą z możliwych. Na stosie SL będziemy umieszczali elementy w porządku rosnącym.

Na stosie SP umieszczamy wartość największą z możliwych. Na stosie SP będziemy umieszczali elementy w porządku malejącym.

Szczyt obu stosów reprezentuje punkt wstawiania elementu.

Z wejścia pobieramy kolejne elementy do posortowania.

Ze stosu SL dotąd pobieramy i przesyłamy elementy na stos SP, aż szczyt SL nie będzie większy od pobranego elementu.

Ze stosu SP dotąd pobieramy i przesyłamy elementy na stos SL, aż szczyt SP nie będzie mniejszy od pobranego elementu.

Pobrany element umieszczamy na stosie SL.

Gdy elementy wejściowe się wyczerpią, całą zawartość stosu SL przenosimy do stosu SP. Odczytując teraz stos SP otrzymamy elementy posortowane rosnąco.

 

Przykład:

 

 
Dane Operacja
dane:
SL:
SP:
 9  5  2  1  9  6  3  
 0
10
Tworzymy stosy i inicjujemy je
dane:
SL:
SP:
 5  2  1  9  6  3
 0  9 
10
9 dodajemy do SL
dane:
SL:
SP:
 5  2  1  9  6  3
 0
10  9 
9 przenosimy z SL do SP, ponieważ jest większe od 5
dane:
SL:
SP:
 2  1  9  6  3
 0  5 
10  9
5 dodajemy do SL
dane:
SL:
SP:
 2  1  9  6  3
 0
10  9  5 
5 przenosimy z SL do SP, ponieważ jest większe od 2
dane:
SL:
SP:
 1  9  6  3
 0  2 
10  9  5
2 dodajemy do SL
dane:
SL:
SP:
 1  9  6  3
 0 
10  9  5  2 
2 przenosimy z SL do SP, ponieważ jest większe od 1
dane:
SL:
SP:
 9  6  3
 0  1 
10  9  5  2 
2 dodajemy do SL
dane:
SL:
SP:
 9  6  3
 0  1  2  5 
10  9 
2 i 5 przenosimy z SP do SL, ponieważ są mniejsze od 9
dane:
SL:
SP:
 6  3
 0  1  2  5  9 
10  9 
9 dodajemy do SL
dane:
SL:
SP:
 6  3
 0  1  2  5 
10  9  9 
9 przenosimy z SL do SP, ponieważ jest większe od 6
dane:
SL:
SP:
 3
 0  1  2  5  6 
10  9  9 
6 dodajemy do SL
dane:
SL:
SP:
 3 
 0  1  2 
10  9  9  6  5 
6 i 5 przenosimy z SL do SP, ponieważ są większe od 3
dane:
SL:
SP:
 0  1  2  3 
10  9  9  6  5 
3 dodajemy do SL – dane wejściowe się kończą
dane:
SL:
SP:
10  9  9  6  5  3  2  1  0 
Przepisujemy SL do SP
dane:
SL:
SP:
wynik:

 1  2  3  5  6  9  9 
Odczytujemy z SP dane z pominięciem pierwszego i ostatniego elementu.

 

Algorytm sortowania przez wstawianie z wykorzystaniem stosów

Wejście:

Ciąg elementów do posortowania

Wyjście:

Ciąg posortowanych rosnąco elementów

Elementy pomocnicze:
SL,SP  – stosy do przechowywania elementów
v  –  przechowuje element
Lista kroków:
K01: Utwórz puste stosy SL i SP  
K02: SL.push(najmniejszą wartość)  
K03: SP.push(największą wartość)  
K04: Dopóki są dane wejściowe, wykonuj K05...K12  
K05:     Czytaj v ; odczytujemy daną z wejścia
K06:     Dopóki SL.top() > v, wykonuj K07..K08  
K07:         SP.push(SL.top()) ; przesyłamy dane ze stosu SL na stos SP
K08:         SL.pop()  
K09:     Dopóki SL.top() < v, wykonuj K10...K11  
K10:         SL.push(SP.top()) ; przesyłamy dane ze stosu SP na stos SL
K11:         SP.pop()  
K12:     SL.push(v) ; odczytane dane umieszczamy na stosie SL
K13: Dopóki SL.empty() = false, wykonuj K14...K15 ; przesyłamy stos SL do SP
K14:     SP.push(SL.top())  
K15:     SL.pop()  
K16: SP.pop() ; pozbywamy się początkowego strażnika
K17: vSP.top()
SP.pop()
; pobieramy dane do przesłania na wyjście
K18: Jeśli SP.empty() = true, to zakończ ; pobrane dane to strażnik końcowy
K19: Pisz v ; umieszczamy dane na wyjściu
K20: Idź do K17 ; i kontynuujemy

 

Program

Ważne:

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 odczytuje ciąg liczb całkowitych ze standardowego wejścia. Pierwsza liczba określa ilość pozostałych liczb. Liczby są sortowane rosnąco i wyprowadzane na wyjście.

Przykładowe dane wejściowe:

25
-1 2 9 17 -3 15 4 6 -9 16 8 1 10 -2 3 12 20 14 18 -5 11 13 7 19 5

 

Lazarus
// Sortowanie przez wstawianie ze stosami
// Data: 21.08.2012
// (C)2012 mgr Jerzy Wałaszek
//---------------------------------------

program stackinsort;

type                                  // typ elementów dla stosów
  Tinteger = array of integer;

var
  SL,SP   : Tinteger;                 // stosy
  SLp,SPp : integer;                  // indeksy szczytów stosów
  n       : integer;                  // liczba elementów wejściowych
  v       : integer;                  // wartość elementu
  i       : integer;                  // licznik

begin
  read(n);                            // odczytujemy liczbę elementów

  SetLength(SL,n+2);                  // tworzymy stosy
  SetLength(SP,n+2);

  SLp := 1; SPp := 1;                 // inicjujemy stosy

  SL[0] := -MAXINT - 1;               // najmniejsza wartość
  SP[0] := MAXINT;                    // największa wartość

  for i := 1 to n do                  // przetwarzamy dane wejściowe
  begin
    read(v);                          // odczytujemy daną z wejścia

    while SL[SLp-1] > v do
    begin
      Dec(SLp);
      SP[SPp] := SL[SLp];             // przenosimy z SL do SP wszystkie
      Inc(SPp);                       // elementy większe od v
    end;

    while SP[SPp-1] < v do
    begin
      Dec(SPp);
      SL[SLp] := SP[SPp];             // przenosimy z SP do SL wszystkie
      Inc(SLp);                       // elementy mniejsze od v
    end;

    SL[SLp] := v;                     // v umieszczamy w SL
    Inc(SLp);
  end;

  while SLp > 0 do                    // przenosimy stos SL do SP
  begin
    Dec(SLp);
    SP[SPp] := SL[SLp];
    Inc(SPp);
  end;

  dec(SPp);                           // usuwamy strażnika
  repeat
    dec(SPp);                         // przesyłamy SP na wyjście
    v := SP[SPp];
    if SPp > 0 then write(v,' ');
  until SPp = 0;

  writeln;

  SetLength(SL,0);                    // usuwamy stosy z pamięci
  SetLength(SP,0);
end.
Code::Blocks
// Sortowanie przez wstawianie ze stosami
// Data: 21.08.2012
// (C)2012 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>

using namespace std;

int main()
{
  int * SL, * SP;                     // stosy
  int SLp = 0,SPp = 0;                // indeksy szczytów stosów
  int n;                              // liczba elementów wejściowych
  int v;                              // wartość elementu

  cin >> n;                           // odczytujemy liczbę elementów

  SL = new int[n+2];                  // tworzymy stosy
  SP = new int[n+2];

  SLp = SPp = 1;                      // inicjujemy stosy

  SL[0] = -2147483648;                // najmniejsza wartość
  SP[0] =  2147483647;                // największa wartość

  for(int i = 0; i < n; i++)          // przetwarzamy dane wejściowe
  {
    cin >> v;                         // odczytujemy daną z wejścia

    while(SL[SLp-1] > v)
      SP[SPp++] = SL[--SLp];          // przenosimy z SL do SP wszystkie
                                      // elementy większe od v
    while(SP[SPp-1] < v)
      SL[SLp++] = SP[--SPp];          // przenosimy z SP do SL wszystkie
                                      // elementy mniejsze od v
    SL[SLp++] = v;                    // v umieszczamy w SL
  }

  while(SLp) SP[SPp++] = SL[--SLp];   // przenosimy stos SL do SP

  SPp--;                              // usuwamy strażnika

  do                                  // przesyłamy SP na wyjście
  {
    v = SP[--SPp];
    if(SPp) cout << v << " ";
  } while(SPp);

  cout << endl;

  delete [] SL;                       // usuwamy stosy
  delete [] SP;

  return 0;
}
Free Basic
' Sortowanie przez wstawianie ze stosami
' Data: 21.08.2012
' (C)2012 mgr Jerzy Wałaszek
'---------------------------------------

Dim As Integer Ptr SL, SP            ' stosy
Dim As integer SLp = 1,SPp = 1       ' indeksy szczytów stosów
Dim n As Integer                     ' liczba elementów wejściowych
Dim v As Integer                     ' wartość Integer
Dim i As Integer                     ' licznik

Open Cons For Input As #1

Input #1, n                          ' odczytujemy liczbę elementów

SL = New Integer [n+2]               ' tworzymy stosy
SP = New Integer [n+2]

SL[0] = -2147483648                  ' najmniejsza wartość
SP[0] =  2147483647                  ' największa wartość

for i = 1 To n                       ' przetwarzamy dane wejściowe

  Input #1,v                         ' odczytujemy daną z wejścia

  While SL[SLp-1] > v
  	 SLp -= 1
    SP[SPp] = SL[SLp]                ' przenosimy z SL do SP wszystkie
    SPp += 1                         ' elementy większe od v
  Wend
  
  While SP[SPp-1] < v
    SPp -= 1	
    SL[SLp] = SP[SPp]                ' przenosimy z SP do SL wszystkie
    SLp += 1                         ' elementy mniejsze od v
  Wend
  
  SL[SLp] = v                        ' v umieszczamy w SL
  SLp += 1
  
Next

Close #1

While SLp > 0
  SLP -= 1
  SP[SPp] = SL[SLp]                  ' przenosimy stos SL do SP
  SPp += 1
Wend

SPp -= 1                             ' usuwamy strażnika

Do                                   ' przesyłamy SP na wyjście
  SPp -= 1
  v = SP[SPp]
  if SPp > 0 Then Print Using "& ";v;
loop While SPp > 0

Print

Delete [] SL                         ' usuwamy stosy
Delete [] SP

End
Wynik
25
-1 2 9 17 -3 15 4 6 -9 16 8 1 10 -2 3 12 20 14 18 -5 11 13 7 19 5
-9 -5 -3 -2 -1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

 

Zadania

  1. Napisz program sortujący, który będzie wykorzystywał listy jednokierunkowe na stosy SL i SP.
  2. Zastanów się, czy powyższy algorytm da się zrealizować w jednej tablicy.

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe