Transcript PowerPoint

Sorting and Searching
Searching
• List of numbers
(5, 9, 2, 6, 3, 4, 8)
• Find 3 and tell me where it was
Linear Search
• Start at the beginning and search until you
find the item
• What is the algorithm?
Linear Search
•
•
Start at the beginning and search until
you find the item
What is the algorithm?
1.
2.
3.
4.
5.
Set current element to first element
Compare target and current element
if found – success!
else – set current element to be next element
go back to step 2
Linear Search
• In the worst case, how many comparisons
will you perform?
Linear Search
• In the worst case, how many comparisons
will you perform?
– N where N is the number of items in the list
Binary Search
• If the list is sorted, can we find a better
algorithm?
(5, 9, 2, 6, 3, 4, 8)
(2, 3, 4, 5, 6, 8, 9)
• What is the algorithm?
Binary Search
(2, 3, 4, 5, 6, 8, 9)
1. compare item to middle element
2. if no match, divide list in half
3. if item is less than middle
1. search first half of list
4. else
1. search second half of list
5. go back to 1
Binary Search
• In the worst case, how many comparisons
will you perform?
– log N where N is the number of items in the
list
• Which is better, linear or binary search?
• Why?
Sorting
• How would you sort a list of numbers?
(5, 9, 1, 6, 3, 4, 8)
Sorting
• How would you sort a list of numbers?
(5, 9, 1, 6, 3, 4, 8)
• cur_index = 0
• for each element in list
– linear search for smallest element in list starting at
cur_index
– if smallest element found is less than element at
cur_index – swap
– increment cur_index
Sorting
(5, 9, 1, 6, 3, 4, 8)
cur_index = 0
min_index = 2 (element 1)
swap 0th element and 2nd element
(1, 9, 5, 6, 3, 4, 8)
cur_index = 1
Sorting
(1, 9, 5, 6, 3, 4, 8) cur_index = 1 swap 1st and 4th
(1, 3, 5, 6, 9, 4, 8) cur_index = 2 swap 2nd and 5th
(1, 3, 4, 6, 9, 5, 8) cur_index = 3 swap 3rd and 5th
(1, 3, 4, 5, 9, 6, 8) cur_index = 4 swap 4th and 5th
(1, 3, 4, 5, 6, 9, 8) cur_index = 5 swap 5th and 6th
(1, 3, 4, 5, 6, 8, 9) cur_index = 6
Complexity of Selection Sort
• How many comparisons were necessary
for selection sort?