LAB 10
First we need a class node
15 min
Class Node{ int value; Node next; Node (int val){ value = val node = NULL } Node (int val, Node next){ value = val this.next = next } }
30 mins
- How we know what is the last element of a list
Class List{ Node head; boolean isEmpty(){ return Head == null } int length(){ int len = 0; Node node = head; while( node.next != NULL ) len++ return len; } // creates a new node with the integer and adds it to the end of the list; void addAsTail(int i){ Node node = new Node (i, null); Node current = head while current.next != null current = current.next current.next = node } // creates a new node with the integer and adds it behind all nodes with a val less or equal the val of the node, possibly at the end of the list; void addSorted(int i){ Node node = new Node (i, null); // first check if the list is empty if this.empty() head = node; // the list is not empty then iterate to find the right place Node current = head while current.next != null && current.value <= i current = current.next if current.next == null current.next = node else // show picture Node tmp = current.next current.next = node node.next = tmp } // reverses the list; void reverse() { // Node node = head; List list = new List() while node.next != null newnode = new Node(node) // deep copy list.addFirst(node) node = node.next } int popHead(){ if head==null return "error" else int value = head.value head = head.next return value } void removeFirst (int i){ Node current = head while current.next != null && current.value != i current = current.next if current.next == null return else // bridge } }
Head Tail list
Class HTList{ Node head; Node tail; ... How some method change... lets try }
Do you want that we implement any specific method
15 mins
// void insertionSort() public void insertSorted(Node node) { if (head == null) { head = node; node.next = null; } else if (node.val < head.val) { node.next = head; head = node; } else { Node p = head; int v = node.val; while (p.next != null && p.next.val <= v) { p = p.next; } // insert new node after p node.next = p.next; p.next = node; } }
15 min
void public static quickSort (HTList list) // base case // partition HTList llist = new HTList(); HTList rlist = new HTList(); HTNode pivot = list.pop HTNode current = list.head while current.next != null HTNode newcurrent = HTNode( current ) if newcurrent.value<pivot.value llist.add(newcurrent) else rlist.add(newcurrent) rlist.add(pivot) quickSort(llist) quickSort(rlist) list = llist.append(rlist) return list
3. Quick sort
public void quickSort() { if (this.length() <= 1) { return this; } else { HTList Ls = new HTList(null); HTList Bs = new HTList(null); Node pivot = this.popHead(); int pivotVal = pivot.val; Node p = this.head; Node pNext = null; while (p != null) { pNext = p.next; if (p.val < pivotVal) { Ls.insertHead(p); } else { Bs.insertHead(p); } p = pNext; } Ls.quickSort(); Bs.quickSort(); Bs.insertHead(pivot); Ls.append(Bs); this.head = Ls.head; this.tail = Ls.tail; } }