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 wstawianie z wykorzystaniem listy jednokierunkowej

SPIS TREŚCI
Tematy pomocnicze

Problem

Dane wejściowe należy posortować rosnąco, wykorzystując listę jednokierunkową. Do sortowania należy wykorzystać algorytm sortujący przez wstawianie.

Rozwiązanie

Sortowanie przez wstawianie ( ang. insertion sort ) jest algorytmem klasy O ( n 2 ). Zasada działania jest następująca:

Tworzymy pustą listę, która będzie przechowywała sortowane elementy.

Na liście umieszczamy dwóch strażników – pierwszy dowolny, drugi o wartości największej.

Odczytujemy z wejścia kolejne elementy. Na liście szukamy elementu, którego wartość jest większa lub równa wartości elementu odczytanego. Odczytany element wstawiamy przed element znaleziony.

Kontynuujemy odczyt elementów aż do wyczerpania danych.

Z listy wyprowadzamy na wyjście kolejno wszystkie elementy z pominięciem strażników.

Listę usuwamy z pamięci.

Algorytm sortowania przez wstawianie z wykorzystaniem listy jednokierunkowej

Wejście:

ciąg elementów do posortowania

Wyjście:

ciąg posortowanych rosnąco elementów

Zmienne pomocnicze:

L  –  wskaźnik pierwszego elementu listy jednokierunkowej
e, p  – wskaźniki elementów listy
v  – odczytana dana

Lista kroków:

K01: Twórz pustą listę L  
K02: Dodaj do L  dwóch strażników  
K03: Dopóki na wejściu są dane,
wykonuj kroki K04...K10
 
K04:     Czytaj v odczytujemy element z wejścia
K05:     p  ← L w p pierwszy strażnik
K06:     Dopóki v  > ( pnextdata  ),
    wykonuj p  ← ( pnext  )
szukamy na liście pierwszego elementu, który nie jest mniejszy od v
K07:     Twórz nowy element o adresie e v wstawiamy przed znaleziony element
K08: ( edata  ) ← v  
K09: ( enext  ) ← ( pnext  )  
K10: ( pnext  ) ← e  
K11: p  ← ( Lnext  ) wyprowadzamy zawartość listy pomijając strażników
K12 Dopóki ( pnext  ) ≠ nil,
wykonuj kroki K13...K14
 
K13:     Pisz ( pdata  )  
K14:     p  ← ( pnext  )  
K15: Usuń listę L  
K16: Zakończ  

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.

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
Pascal
// Sortowanie przez wstawianie z listą jednokierunkową
// Data: 21.08.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------------------

program listinsort;

type                           // typ elementu listy jednokierunkowej
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    data  : integer;
  end;

var
  L    : PslistEl;             // wskaźnik początku listy
  e, p : PslistEl;             // wskaźniki elementów listy
  n    : integer;              // liczba elementów do posortowania
  v    : integer;              // wartość elementu
  i    : integer;              // licznik elementów

begin
  new ( L );                   // tworzymy pierwszego strażnika
  new ( L^.next );             // tworzymy drugiego strażnika
  L^.next^.next := nil;        // drugi strażnik jest ostatni na liście
  L^.next^.data := MAXINT;     // wartość drugiego strażnika

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

  for i := 1 to n do
  begin

    read ( v );                // czytamy element

    p := L;                    // p ustawiamy na pierwszego strażnika

    while v > p^.next^.data do // szukamy miejsca wstawienia
      p := p^.next;

    new ( e );                 // tworzymy nowy element

    e^.data := v;              // inicjujemy element
    e^.next := p^.next;

    p^.next := e;              // element wstawiamy do listy L

  end;

  p := L^.next;                // listę przesyłamy na wyjście

  while p^.next <> nil do
  begin
    write ( p^.data, ' ' );
    p := p^.next;
  end;

  writeln;

  while L <> nil do            // usuwamy listę z pamięci
  begin
    e := L;
    L := L^.next;
    dispose ( e );
  end;
end.
C++
// Sortowanie przez wstawianie z listą jednokierunkową
// Data: 21.08.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------------------

#include <iostream>

using namespace std;

struct slistEl                // typ elementu listy jednokierunkowej
{
  slistEl * next;
  int data;
};

int main( )
{
  slistEl * L;                // wskaźnik początku listy
  slistEl * e, * p;           // wskaźniki elementów listy
  int n;                      // liczba elementów do posortowania
  int v;                      // wartość elementu

  L = new slistEl;            // tworzymy pierwszego strażnika
  L->next = new slistEl;      // tworzymy drugiego strażnika
  L->next->next = NULL;       // drugi strażnik jest ostatni na liście
  L->next->data = 2147483647; // wartość drugiego strażnika

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

  for( int i = 0; i < n; i++ )
  {
    cin >> v;                 // czytamy element
                              // szukamy miejsca wstawienia
    for( p = L; v > p->next->data; p = p->next ) ;

    e = new slistEl;          // tworzymy nowy element

    e->data = v;              // inicjujemy element
    e->next = p->next;

    p->next = e;              // element wstawiamy do listy L

  }
                              // listę przesyłamy na wyjście
  for( p = L->next; p->next; p = p->next ) cout << p->data << " ";

  cout << endl;

  while( L )                  // usuwamy listę z pamięci
  {
    e = L;
    L = L->next;
    delete e;
  }

  return 0;
}
Basic
' Sortowanie przez wstawianie z listą jednokierunkową
' Data: 21.08.2012
' (C)2020 mgr Jerzy Wałaszek
'---------------------------------------------

Type slistEl               ' typ elementu listy jednokierunkowej
  next As slistEl Ptr
  data As Integer
End Type

Dim L As slistEl Ptr       ' wskaźnik początku listy
Dim As slistEl Ptr e, p    ' wskaźniki elementów listy
Dim n As Integer           ' liczba elementów do posortowania
Dim v As Integer           ' wartość elementu
Dim i As Integer           ' licznik elementów

Open Cons For Input As #1

L = new slistEl            ' tworzymy pierwszego strażnika
L->next = new slistEl      ' tworzymy drugiego strażnika
L->next->next = 0          ' drugi strażnik jest ostatni na liście
L->next->data = 2147483647 ' wartość drugiego strażnika

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

for i = 1 To n

  Input #1, v              ' czytamy element

  p = L                    ' szukamy miejsca wstawienia
  
  While v > p->next->Data: p = p->Next: Wend 

  e = new slistEl          ' tworzymy nowy element

  e->data = v              ' inicjujemy element
  e->next = p->Next

  p->next = e              ' element wstawiamy do listy L

Next

Close #1

p = L->Next                ' listę przesyłamy na wyjście

While p->Next
  Print Using "& ";p->Data;
  p = p->Next
Wend

Print

While L                    ' usuwamy listę z pamięci
  e = L
  L = L->Next
  Delete e
Wend

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 

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.