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 przez scalanie za pomocą stosów

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Należy posortować rosnąco ciąg danych wejściowych za pomocą stosowego algorytmu sortowania przez wstawianie.

Rozwiązanie

Sortowanie przez wstawianie ( ang. insertion sort ) jest algorytmem sortującym o czasowej złożoności obliczeniowej O ( n 2 ). 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 S L  – stos lewy i S P  – stos prawy.

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

Na stosie S P  umieszczamy wartość największą z możliwych. Na stosie S P  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 S L  dotąd pobieramy i przesyłamy elementy na stos S P, aż szczyt S L  nie będzie większy od pobranego elementu.

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

Pobrany element umieszczamy na stosie S L.

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

Przykład:

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

 
 
 1  2  3  5  6  9  9 
Odczytujemy z S P  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

Zmienne pomocnicze:

S L, S P  – stosy do przechowywania elementów
v  –  przechowuje element

Lista kroków:

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

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 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.
Dane przykładowe ( przekopiuj do schowka i wklej do okna konsoli ):

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
Pascal
// Sortowanie przez wstawianie ze stosami
// Data: 21.08.2012
// (C)2020 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.
C++
// Sortowanie przez wstawianie ze stosami
// Data: 21.08.2012
// (C)2020 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;
}
Basic
' Sortowanie przez wstawianie ze stosami
' Data: 21.08.2012
' (C)2020 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
Na początek:  podrozdziału   strony 

Zadania

  1. Napisz program sortujący, który będzie wykorzystywał listy jednokierunkowe na stosy S L  i S P.
  2. Zastanów się, czy powyższy algorytm da się zrealizować w jednej tablicy.
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.