StefiIOE

[ADS]Bubble sort on a linked list

Dec 2nd, 2020 (edited)
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.48 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. class DLLNode<E> {
  6.     protected E element;
  7.     protected DLLNode<E> pred, succ;
  8.  
  9.     public DLLNode(E elem, DLLNode<E> pred, DLLNode<E> succ) {
  10.         this.element = elem;
  11.         this.pred = pred;
  12.         this.succ = succ;
  13.     }
  14.  
  15.     @Override
  16.     public String toString() {
  17.         return element.toString();
  18.     }
  19. }
  20.  
  21. class DLL<E> {
  22.     private DLLNode<E> first, last;
  23.  
  24.     public DLL() {
  25.         // Construct an empty SLL
  26.         this.first = null;
  27.         this.last = null;
  28.     }
  29.  
  30.     public void deleteList() {
  31.         first = null;
  32.         last = null;
  33.     }
  34.  
  35.     public int length() {
  36.         int ret;
  37.         if (first != null) {
  38.             DLLNode<E> tmp = first;
  39.             ret = 1;
  40.             while (tmp.succ != null) {
  41.                 tmp = tmp.succ;
  42.                 ret++;
  43.             }
  44.             return ret;
  45.         } else
  46.             return 0;
  47.  
  48.     }
  49.  
  50.     public void insertFirst(E o) {
  51.         DLLNode<E> ins = new DLLNode<E>(o, null, first);
  52.         if (first == null)
  53.             last = ins;
  54.         else
  55.             first.pred = ins;
  56.         first = ins;
  57.     }
  58.  
  59.     public void insertLast(E o) {
  60.         if (first == null)
  61.             insertFirst(o);
  62.         else {
  63.             DLLNode<E> ins = new DLLNode<E>(o, last, null);
  64.             last.succ = ins;
  65.             last = ins;
  66.         }
  67.     }
  68.  
  69.     public void insertAfter(E o, DLLNode<E> after) {
  70.         if (after == last) {
  71.             insertLast(o);
  72.             return;
  73.         }
  74.         DLLNode<E> ins = new DLLNode<E>(o, after, after.succ);
  75.         after.succ.pred = ins;
  76.         after.succ = ins;
  77.     }
  78.  
  79.     public void insertBefore(E o, DLLNode<E> before) {
  80.         if (before == first) {
  81.             insertFirst(o);
  82.             return;
  83.         }
  84.         DLLNode<E> ins = new DLLNode<E>(o, before.pred, before);
  85.         before.pred.succ = ins;
  86.         before.pred = ins;
  87.     }
  88.  
  89.     public E deleteFirst() {
  90.         if (first != null) {
  91.             DLLNode<E> tmp = first;
  92.             first = first.succ;
  93.             first.pred = null;
  94.             if (first == null)
  95.                 last = null;
  96.             return tmp.element;
  97.         } else
  98.             return null;
  99.     }
  100.  
  101.     public E deleteLast() {
  102.         if (first != null) {
  103.             if (first.succ == null)
  104.                 return deleteFirst();
  105.             else {
  106.                 DLLNode<E> tmp = last;
  107.                 last = last.pred;
  108.                 last.succ = null;
  109.                 return tmp.element;
  110.             }
  111.         }
  112.         // else throw Exception
  113.         return null;
  114.     }
  115.  
  116.     @Override
  117.     public String toString() {
  118.         String ret = new String();
  119.         if (first != null) {
  120.             DLLNode<E> tmp = first;
  121.             ret += tmp + "<->";
  122.             while (tmp.succ != null) {
  123.                 tmp = tmp.succ;
  124.                 ret += tmp + "<->";
  125.             }
  126.         } else
  127.             ret = "Prazna lista!!!";
  128.         return ret;
  129.     }
  130.  
  131.     public DLLNode<E> getFirst() {
  132.         return first;
  133.     }
  134.  
  135.     public DLLNode<E> getLast() {
  136.  
  137.         return last;
  138.     }
  139.  
  140. }
  141.  
  142. public class BubbleSortDLL {
  143.  
  144.     public static void bubbleSort(DLL<Integer> lista) {
  145.  
  146.         DLLNode<Integer> prv = lista.getFirst();
  147.  
  148.         while (prv != null) {
  149.  
  150.             DLLNode<Integer> vtor = prv.succ;
  151.  
  152.             while (vtor != null) {
  153.  
  154.                 if (prv.element > vtor.element) {
  155.  
  156.                     int tmp = prv.element;
  157.                     prv.element = vtor.element;
  158.                     vtor.element = tmp;
  159.                 }
  160.                 vtor = vtor.succ;
  161.             }
  162.             prv = prv.succ;
  163.         }
  164.  
  165.         DLLNode<Integer> tmp = lista.getFirst();
  166.         while (tmp != null) {
  167.             System.out.print(tmp.element);
  168.             if (tmp.succ != null)
  169.                 System.out.print(" ");
  170.             tmp = tmp.succ;
  171.         }
  172.     }
  173.  
  174.     public static void main(String[] args) throws IOException {
  175.         DLL<Integer> lista = new DLL<Integer>();
  176.         BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
  177.         String s = stdin.readLine();
  178.         int N = Integer.parseInt(s);
  179.         s = stdin.readLine();
  180.         String[] pomniza = s.split(" ");
  181.         for (int i = 0; i < N; i++) {
  182.             lista.insertLast(Integer.parseInt(pomniza[i]));
  183.         }
  184.  
  185.         bubbleSort(lista);
  186.  
  187.     }
  188.  
  189. }
Add Comment
Please, Sign In to add comment