Algorytmy i Struktury Danych - Sortowanie przez wstawianie z listą

Sortowanie przez wstawianie (ang. insertion sort) jest algorytmem klasy O (n²). 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 > (p→next→data), wykonuj p ← (p→next)	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:	(e→data) ← v
K09:	(e→next) ← (p→next)
K10:	(p→next) ← e
K11:	p ← (L→next)	wyprowadzamy zawartość listy pomijając strażników
K12	Dopóki (p→next) ≠ nil, wykonuj kroki K13…K14
K13:	Pisz (p→data)
K14:	p ← ( p→next)
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

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.

Sortowanie przez wstawianie z wykorzystaniem listy jednokierunkowej