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

SPIS TREŚCI

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(n2). Zasada działania jest następująca:

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 kroki K04…K10
K04:   Czytaj v ; odczytujemy element do sortowania
K05:   pL    ; w p pierwszy strażnik
K06:   Dopóki v > (pnextdata), ; szukamy na liście pierwszego elementu,
       wykonuj p ← (pnext)      ; który nie jest mniejszy od v
K07:   Twórz nowy element e ; e 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 do odczytu znajdują się w następnym wierszu. Liczby zostają posortowane rosnąco i wyprowadzone 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
  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
{
  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
  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
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
Python (dodatek)
# Sortowanie przez wstawianie
# z listą jednokierunkową
# Data: 28.05.2024
# (C)2024 mgr Jerzy Wałaszek
#----------------------------

# klasa elementu listy
#---------------------
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# tworzymy pierwszego strażnika
L = slistEl(0)
# tworzymy drugiego strażnika
L.next = slistEl(2147483647)
# odczytujemy liczbę elementów
n = int(input())
# czytamy elementy do tablicy
ev = input().split()
# czytamy elementy i sortujemy
for i in range(n):
    v = int(ev[i])
    # szukamy miejsca wstawienia
    p = L
    while v > p.next.data:
        p = p.next
    e = slistEl(v) # tworzymy nowy element
    e.next = p.next
    p.next = e # element wstawiamy do listy L
    
# listę przesyłamy na wyjście
p = L.next
while p.next:
    print(p.data,end=" ")
    p = p.next
print()
while L: # usuwamy listę z pamięci
    e = L
    L = L.next
    del e
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
©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.