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

©2019 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 K04...K10  
K04:     Czytaj v odczytujemy element z wejścia
K05:     pL 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 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)2019 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)2019 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)2019 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
©2019 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.