import java.util.*;
class node{
int data;
node next,prev;
public node(int n){
data = n;
next = prev = null;
}
}
class list{
node head,tail;
public list(){
head = tail = null;
}
void addLast(int n){
node input = new node(n);
if(head==null){
head = tail = input;
}
else{
tail.next = input;
input.prev = tail;
tail = input;
}
}
public void insertion()
{
node flag=head;
node pencari;
int temp;
do
{
if (flag.next.data<flag.data)
{
pencari=flag;
while (flag.next.data>pencari.data)
{
pencari=pencari.prev;
}
temp=pencari.data;
pencari.data=flag.next.data;
flag.next.data=temp;
}
flag=flag.next;
} while (flag.next!=null);
}
void cetak (){
node temp = head;
while(temp!=null){
System.out.print(temp.data+” “);
temp = temp.next;
}
}
}
public class InsertionSort{
public static void main (String[] args){
Scanner input = new Scanner (System.in);
System.out.print(“Jumlah bilangan : “);
int n = input.nextInt();
list angka = new list();
System.out.println(“Masukkan bilangan :”);
for(int i=0;i<n;i++) {
System.out.print(“=> “);
int a = input.nextInt();
angka.addLast(a);
}
System.out.println(“Urutan bilangan dari kecil ke besar :”);
for(int i=0;i<n-1;i++){
angka.insertion();
}
angka.cetak();
System.out.println();
}
}
