Sorting an array of strings

for strings you can't use < , >

there exists a method called compareTo() which returns an integer

there exists a method called compareTo() which returns an integer

String x;

String y;

x.compareTo(y);

String y;

x.compareTo(y);

returns a negative number if x < y

returns zero if x == y

returns a positive 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);

}

{

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

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 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

otherwise i is not in the list

eg/ return -1