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

SPIS TREŚCI W KONSERWACJI
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 (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 S L 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 S P 
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

Zmienne 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 kroki K05…K12		  
K05: Czytaj v odczytujemy daną z wejścia
K06: Dopóki S L.top() > v,
wykonuj kroki K07..K08		  
K07: SP.push (SL.top()) przesyłamy dane ze stosu SL na stos SP
K08: SL.pop()  
K09: Dopóki S L.top() < v,
wykonuj kroki 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 kroki 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: v ← SP.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 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 SL i SP.
  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
©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.