Sortowanie przez wstawianie z wykorzystaniem listy jednokierunkowej


Tematy pokrewne
Listy
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Operacje na listach dwukierunkowych
Operacje na listach cyklicznych jednokierunkowych
Liniowe przeszukiwanie listy
Przeszukiwanie liniowe z wartownikiem listy dwukierunkowej
Wyszukiwanie największego/najmniejszego elementu listy
Zliczanie elementów listy
Usuwanie z listy duplikatów
Odwracanie listy jednokierunkowej
Podział listy jednokierunkowej na dwie listy
Scalanie dwóch list posortowanych
Sortowanie listy jednokierunkowej przez scalanie
Sortowanie przez wstawianie z wykorzystaniem listy jednokierunkowej
Sortowanie szybkie listy dwukierunkowej
Samoorganizujące się listy
Haszowanie z wykorzystaniem list jednokierunkowych
Zbiory rozłączne – implementacja listowa

Problem

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

 

 

Sortowanie przez wstawianie (ang. insertion sort) jest algorytmem klasy O(n2). 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

Elementy 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  

 

Program

Ważne:

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

 

Lazarus
// Sortowanie przez wstawianie z listą jednokierunkową
// Data: 21.08.2012
// (C)2012 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.
Code::Blocks
// Sortowanie przez wstawianie z listą jednokierunkową
// Data: 21.08.2012
// (C)2012 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;
}
Free Basic
' Sortowanie przez wstawianie z listą jednokierunkową
' Data: 21.08.2012
' (C)2012 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
Wyniki
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

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe