Lecture 30

Sorting an array of strings

for strings you can't use < , >
there exists a method called compareTo() which returns an integer

String x;
String y;
x.compareTo(y);

returns a negative number if x < y
returns zero if x == y
returns a positive number if x > y

String implements the comparable interface

public interface Comparable
{
public int compareTo(Object in);
}

Any class that implements comparable is strongly suggested to do it as follows

1. Total Ordering

- if a.compareTo(b) == 0;
then b.compareTo(a) == 0; (reflexive)

- if a.compareTo(b) <= 0;
then b.compareTo(a) >= 0; (antisymmetric)

- if a.compareTo(b) <= 0 and b.compareTo(c) <= 0
then a.compareTo(c) <= 0 (transitive)

a.compareTo(b) is defined for all a,b (Total)


2. If you implement equals() then if a.compareTo(b) == 0;
then a.equals(b) == true
and vice versa


Searching a sorted list

Sorted list searching can be done recursively with the divide and conquer strategy

Strategy
- split the list in half
- Let s represent the list item at the split point

if list has size > 1

if s = i, return index of s
if s > i, search the list segment with smaller values
if s < i, search the list segment with larger values

if list has size 1

if s = i, return index of s
otherwise i is not in the list
eg/ return -1

Lecture 29

QuickSort

• somewhat trickier than MergeSort
• join is trivial
• all the action happens in split
• in QuickSort , split sorts the elements into bins
• all the list elements less than the given number is the 'pivot'
• all the list elements Greater than a given number
• all list elements equal to the pivot
• choose the pivot arbitrarily from one of the list elements

eg

493872

choose 4 as pivot

low - 3,2
high - 9,8,7
pivot - 4

concatenate the list in order

sort(low)
sort(pivot + high)

• pivot list is guaranteed to have at least one element(the pivot)
• i want both split lists to be smaller than the initial list

1. low list is non empty
1. split between low and pivot
2. if low is empty but high is not
1. split between pivot and high
3. if both low and high are empty then split somewhere in middle of pivot

Lecture 28

Sorting

• A fundamental task of computer science
• given an array , put the array in order

int a[]= {3,9,0,2,6}
sort(a);
a=0,2,3,6,9

Sorting Strategies

1. Bubble Sort
• take the unsorted array and start at the top
• traverse the list until you find an element out of order
• using pairwise exchanges move the out of order element toward the top of the list until it is in order
• continue until the end of the list
• once an out of order element is found we float it to the correct position

Example

1. 39026
2. 30926
3. 03926
4. 03296
5. 02396
6. 02369

Divide and Conquer Sorting

• nobody uses bubblesort for anything serious
• better methods:
  
• mergesort
• quicksort
• if the list is of size > 1 then
1. divide the list into two sublists
2. sort each sublist
3. join the two sublists
• else
1. do nothing
• these are recursive sorting algorithms
• all the actio nhappens in the splitting and joining

public static void Sort(int[]a, int begin, int end)
//sorts the subvector of 'a' from beginning to end inclusive
{
if (end - begin > 0)
{
int S = split(a,beginning,end)
sort(a,begin,S);
sort(a,S+1,end;
join(a,begin,S,end)
}

• MergeSort
• split is simple
• join is complicated
• QuickSort
• split is complicated
• join is simple

MergeSort

• Split
• splits the list down the middle
• returns (begin + end )/ 2
• Join
• two sorted Lists
• merge them in order

Example

038249
038 249
0<2
2<3
3<4
4<8
8<9
023489


42091

420:91

• 42:0
• 4:2
• 4 //done
• 2 //done
• join(2,4)
• 24
• join(24,0)
• 024
• 9:1
• 9 //done
  
• 1 //done
• join(9,1)
• 19
• join(024,91)
• 01249
  

Lecture 27

Stacks and queues

• best implemented with linked lists
• trying to implement with arrays or arraylists is not feasible

Doubly Linked Lists

• in a double linked list keep track of
• head
• next pointer in each node
• tail
  
• previous pointer of each node

public class DoubleLinkedList
{
public class ListNode
{
private myObject item;
private ListNode next;
private ListNode prev;
public ListNode {...}
}
public void addNode(MyObject, int)
public void delNode(int)
public myObject getData(int)

public void addNodeToHead(MyObject a)
public void addNodeToTail(MyObject b)
public void delNodeFromHead()
public void delNodeFromTail()
public MyObject getDataFromHead()
public MyObject getDataFromTail()



Adding a Node to A Position

//ListNode c = a.next;
b.next = a.next;
b.prev = a;
(a.next).prev = b;
a.next = b
//c.prev = b;
if (a==tail)
{tail=b;}


More Formally

//Check whether a exists

if (a != null)
{
b.next = a.next;
b.prev = a;
a.next = b;
if (a==tail){tail = b;}
else{
(b.next).prev = b
}

Deleting a Node From a Given Position

if(a.next)!= null
{
if (a.next = tail)
{a.next = null;
tail = a}
else{
a.next = (a.next).next
(a.next).prev = a;
}
}

Doubly linked list with stacks and queues

• Stack
• add
• addNodeToHead(MyObject)
• delete
• getDataFromHead()
• delNodeFromHead()
• Queue
• add a
• addNodeToHead(MyObject)
• delete / leave
• getDataFromTail
• delNodeFromTail()
  

Lecture 26

Linked Lists Continued

Node Inner Classes

• ListNode has no use or meaning apart from the linked list
• our existing definition opens the list to privacy leaks
• a careless application programmer could get a reference and change it
• make ListNode an inner class within the 'linked list' class
• advantages
  
• eliminates privacy leaks
• simplifies LinkedList
• disadvantages
• reduces flexibility

Example

public class LinkedList inner
{
private class ListNode // inner class
{
private myObject item;
private ListNode next;
public ListNode(MyObject item, ListNode next) { ... }
}
private listNode head; ...}

• using myObject as a generic
• linked lists with generics

public class LinkedList inner //good

{
private class ListNode /** this is good, but this alone does not suffice */
{
private T item;
private ListNode next; // bad
private ListNode next; //good

• use the generic type parameter firstly with the outer class as well as the inner class
• use the generic type parameter with every declaration of the generic object.
  

Lecture 25

Recursion

• Stack
• space for parameters / local values/ return values
• indirect recursion
• a method which calls iteself with different parameters
• recursion
• a method which calls itself within itself
• if this is done wrong you get a stack overflow error

int fact(int n)
{
//base case

if (n == 1) { return n}
return n * fact(n-1);
}

• famous recursive methods
• binary search
• mergesort
• quick sort
• towers of hanoi

int bSearch(int[]A, int key, int l, int r)

{
// base case

if (l>r) return -(l + 1)
int m = (l + r) / 2;
if (A[m] == key ) return m;
if (A[m] < face="courier new">return bSearch( A, key, m+1, r)
return bSearch(A, key, L, m-1);

}


these were the notes i got when turnpin was in class, he doesn't write on the board too often so i hope this helps.