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

## 7 comments:

I just wanted to say thank you.

no problem man, this is so nice to have before exams. I'm glad i could be some help, for the next cse courses after 1030 i plan on continuing this, but i would probably want multiple moderators because EVERY lecture was getting really difficult to post in time.

but i appreciate your thanks and good luck on the final

Hi,

Thanks from me too.

Are you taking any cs courses in the summer?

On that note, CSE 2001, 2011, 2021 and 2031 are next year's courses. Thats what the undergrad calendar seems to say. The topics look interesting.

finally more comp classes...and less crap classes

Hey Jake,

Thanks for your putting your notes online. I was in Turpins class, so I really really needed it, like most of us in Turpin's class who struggled to get notes out of his lectures.

So you could say you helped AT LEAST half of the students go some way towards getting through this course.

thanks again, best of luck with the exam.

thanks Jake, your notes were very helpful

Post a Comment