Searching ans Sorting

Question 1

Search Algorithms

Answer 1

• method for finding an item or group of items
• Collections could be implicit
• Collections could be explicit

Question 2

Linear Search

Answer 2

• brute force search
• list does not have to be sorted
• O(n) - where n is len(L)

Question 3

Bisection/binary search

divide and conquer

Answer 3

• list MUST be sorted to give correct answer

Question 4

Linear search

on a SORTED list

Answer 4

• must only look until reach a number greater than e

- O(n) - where n is len(L)

Question 5

Bisection search

Answer 5

• break into smaller version of problems

- answer to smaller version is answer to original problem

Question 6

Searching a sorted list

n is len(L)

Answer 6

• linear search => O(n)
• binary search => O(log n)
  (assumes the list is sorted!)

Question 7

When to sort first then search?

Answer 7

• sort + O(log n) < O(n) ->
  sort < O(n) - O(log n)
• when sorting is less than O(n) -> never true!

Question 8

Amortized cost

n is len(L)

Answer 8

• why bother sorting first
• in some cases, may sort list once -> then many searches
• AMORTIZE cost of the sort over many searches
• SORT + KO(log n) < KO(n) -> for large K, SORT time becomes irrelevant

Question 9

Monkey Sort

aka bogosort - stupid sort - slowsort - permutation sort - shotgun sort

Answer 9

is a random sort, every time through the list get randomly sorted and if lucky it is ordered!

Question 10

Monkey Sort - complexity

Answer 10

Best case:
O(n) where n is len(L)
Worst case:
O(?) is unbound if really unlucky

Question 11

Bubble Sort

Answer 11

• Compare consecutive pairs of elements
• Swap elements such that smaller is first
• Start over when reach end of list
• No more swaps = stop

Question 12

Bubble Sort - complexity

Answer 12

• inner for loop is doing comparisons
• out while loop is doing multiple passes until no more swaps
  O(n2) where n is len(L)

Question 13

Selection Sort

1. First step

Answer 13

• extract min. element

- swap it with element at index 0

Question 14

Selection Sort

2. Subsequent step

Answer 14

• in remaining sub-list extract min. element

- swap it with the element at index 1

Question 15

Selection Sort

3. Keep the left portion of the list sorted

Answer 15

• at ith step, first i element in list are sorted

- all other elements are bigger than first i elements

Question 16

Selection Sort - complexity

Answer 16

O(n2) where n is len(L)

Question 17

Merge Sort

Answer 17

Use a divide-and-conquer approach

1. if list of lenght 0 is 1 - already sorted
2. if list has more than one element, split into two lists and sort each
3. merge sorted sublists
   - look at first element of each, move smaller to wend of result
   - when one list empty, just copy rest of other list

Question 18

Merge Sort - complexity

overview

Answer 18

• go through two lists, only one pass
• compare only smallest elements in each sublist
• O(len(left) + len(right) copied elements
• O(len(longer list)) comparisons
• linear lenght of the lists

Question 19

Merge Sort - recursevely

Answer 19

• divide list successively into halves

- depth-first such that conquer smallest pieces down one branch first before moving to larger pieces

Question 20

Merge Sort - complexity

1. at first recursion level

Answer 20

• n/2 elements in each list

- O(n) + O(n) where n is len(L)

Question 21

Merge Sort - complexity

2. at second recursion level

Answer 21

• n/4 elements in each list
• two merges -> O(n) where n is len(L)
  Each recursion level is O(n) where n is len(L)

Question 22

Merge Sort - complexity

3. dividing list in half

Answer 22

with each recursive call:

O(log(n)) where n is len(L)

Question 23

Merge Sort - complexity

Answer 23

O(n log (n)) where n is len(L)

Question 24

Sorting Summary

n is len(L)

Answer 24

bogo sort
- randomness, unbound O()
bubble sort
- O(n2)
selection sort
- O(n2)
- guaranteed the first i elements were sorted
merge sort
- O(n log(n))
O(n log(n)) is the fastest a sort can be

Question 25

Algorithms Summary

Answer 25

Selection Sort
Bubble Sort
Insertion Sort
Merge Sort
---------------------------
Linear Search
Binary Search

Question 26

Selection Sort

Answer 26

1. fin the smallest unsorted element in an array
2. swap it with the first unsorted element of that array
   Big Oh: Best => O(n^2)
   Worst => O(n^2)

Question 27

Bubble Sort

Answer 27

2. swap adjacent pairs of elements if they are out of order
3. “bubbling” larger elements to the right and smaller one to the left
   Big Oh: Best => O(n)
   Worst => O(n^2)

Question 28

Insertion Sort

Answer 28

1. proceed once through the array from left to right

2. shifting elements as necessary to insert each element into its correct place.

Question 29

Merge Sort

Answer 29

1. split the full array into sub arrays
2. then merge those sub arrays back together in the correct order.
   Big Oh: Best => O(n log n)
   Worst => O(n log n)

Question 30

Linear Search

Answer 30

1. Iterate across the array from left to right
2. trying to find the target element
   Big Oh: Best => O(1)
   Worst => O(n)

Question 31

Binary Search

Answer 31

Given a SORTED array!
1. divide and conquer by systematically eliminating half of the remaining elements in the search for the target elements.
Big Oh: Best => O(1)
Worst => (log n)

Question 32

Binary Search

Sudocode

Answer 32

Repeat until (sub)array is of size 0

• calculate the middle point of the current (sub)array
• if the target is at the middle - stop
• otherwise if the target is less than the middle, repeat, changing the end point to be just to the left of the middle
• otherwise if the target is greater than what’s at the middle, repeat, changing the start point to be just to the right of the middle