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 wstawianie 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(n2). Złożoność pamięciowa ma klasę O(n). 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:

Przykład:

 
Dane
Operacja
 dane:
   SL:
   SP:
 9  5  2  1  9  6  3
 0
10
Tworzymy stosy i inicjujemy je.
W SL umieszczamy najmniejszą liczbę.
W SP umieszczamy największą liczbę.
 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 
1 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 bez
pierwszego i ostatniego elementu.

Zbiór jest posortowany.

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.
xMAX : największa wartość liczbowa
xMIN : najmniejsza wartość liczbowa

Lista kroków:

K01: Utwórz puste stosy SL i SP
K02: SL.push(xMIN) ; strażnik początkowy
K03: SP.push(xMAX) ; strażnik końcowy
K04: Dopóki są dane wejściowe,
     wykonuj kroki K05…K12
K05:   Czytaj v ; odczytujemy daną z wejścia
K06:   Dopóki SL.top() > v,
       wykonuj kroki K07..K08
K07:     SP.push(SL.top()) ; przesyłamy dane ze stosu SL
K08:     SL.pop() ; na stos SP
K09:   Dopóki SL.top() < v,
       wykonuj kroki K10…K11
K10:     SL.push(SP.top()) ; przesyłamy dane ze stosu SP
K11:     SP.pop() ; na stos SL
K12:   SL.push(v) ; odczytane dane umieszczamy na stosie SL
K13: Dopóki SL.empty() = false, ; przesyłamy stos SL do SP
     wykonuj kroki K14…K15
K14:   SP.push(SL.top())
K15:   SL.pop()
K16: SP.pop() ; pozbywamy się strażnika początkowego
K17:   vSP.top() ; pobieramy dane do przesłania na wyjście
       SP.pop()
K18:   Jeśli SP.empty() = true, ; pobrane dane
       to zakończ ; to strażnik końcowy
K19:   Pisz v ; przesyłamy dane na wyjście
K20:   Idź do kroku 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

  readln(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
      Inc(SPp); // wszystkie elementy większe od v
    end;

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

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

  readln;

  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ść
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
Python (dodatek)
# Sortowanie przez wstawianie ze stosami
# Data: 17.06.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------------------

SLp = 1 # indeksy szczytów stosów
SPp = 1 

n = int(input()) # odczytujemy liczbę elementów

SL = [0] * (n+2) # tworzymy stosy
SP = [0] * (n+2)

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

arr = input().split()

for i in range(n):  # przetwarzamy dane wejściowe
    v = int(arr[i]) # 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

    while SP[SPp-1] < v:
        SPp -= 1
        SL[SLp] = SP[SPp] # przenosimy z SP do SL wszystkie
        SLp += 1 # elementy mniejsze od v

    SL[SLp] = v # v umieszczamy w SL
    SLp += 1

while SLp > 0:
    SLp -= 1
    SP[SPp] = SL[SLp] # przenosimy stos SL do SP
    SPp += 1

SPp -= 1 # usuwamy strażnika
while True: # przesyłamy SP na wyjście
    SPp -= 1
    v = SP[SPp]
    if SPp:
        print(v,end=" ")
    if not SPp: break

print()

del SL # usuwamy stosy
del SP
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.