// Sortowanie przez wstawianie
// z listą jednokierunkową
// Data: 21.08.2012
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program listinsort;

type // typ elementu listy jednokierunkowej
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    Data: integer;
  end;

var
  L   : PSLel; // wskaźnik początku listy
  e, p : PSLel; // 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.

// Sortowanie przez wstawianie
// z listą jednokierunkową
// Data: 21.08.2012
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

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

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

  L = new SLel; // tworzymy pierwszego
                   // strażnika
  L->next = new SLel; // 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 SLel; // 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;
}

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

Type SLel ' typ elementu listy
  next As SLel Ptr
  data As Integer
End Type

Dim L As SLel Ptr ' wskaźnik początku listy
Dim As SLel 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 SLel ' tworzymy pierwszego strażnika
L->next = new SLel ' 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 SLel ' 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