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