Searching ans Sorting Flashcards

Search algorithms Bisection Search Bogo Sort Bubble Sort Merge Sort

1
Q

Search Algorithms

A
  • method for finding an item or group of items
  • Collections could be implicit
  • Collections could be explicit
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Linear Search

A
  • brute force search
  • list does not have to be sorted
  • O(n) - where n is len(L)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Bisection/binary search

divide and conquer

A
  • list MUST be sorted to give correct answer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Linear search

on a SORTED list

A
  • must only look until reach a number greater than e

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Bisection search

A
  • break into smaller version of problems

- answer to smaller version is answer to original problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Searching a sorted list

n is len(L)

A
  • linear search => O(n)
  • binary search => O(log n)
    (assumes the list is sorted!)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

When to sort first then search?

A
  • sort + O(log n) < O(n) ->
    sort < O(n) - O(log n)
  • when sorting is less than O(n) -> never true!
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Amortized cost

n is len(L)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Monkey Sort

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Monkey Sort - complexity

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Bubble Sort

A
  • Compare consecutive pairs of elements
  • Swap elements such that smaller is first
  • Start over when reach end of list
  • No more swaps = stop
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Bubble Sort - complexity

A
  • inner for loop is doing comparisons
  • out while loop is doing multiple passes until no more swaps
    O(n2) where n is len(L)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Selection Sort

1. First step

A
  • extract min. element

- swap it with element at index 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Selection Sort

2. Subsequent step

A
  • in remaining sub-list extract min. element

- swap it with the element at index 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Selection Sort

3. Keep the left portion of the list sorted

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

- all other elements are bigger than first i elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Selection Sort - complexity

A

O(n2) where n is len(L)

17
Q

Merge Sort

A

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

Merge Sort - complexity

overview

A
  • 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
19
Q

Merge Sort - recursevely

A
  • divide list successively into halves

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

20
Q

Merge Sort - complexity

1. at first recursion level

A
  • n/2 elements in each list

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

21
Q

Merge Sort - complexity

2. at second recursion level

A
  • 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)
22
Q

Merge Sort - complexity

3. dividing list in half

A

with each recursive call:

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

23
Q

Merge Sort - complexity

A

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

24
Q

Sorting Summary

n is len(L)

A
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
25
Algorithms Summary
``` Selection Sort Bubble Sort Insertion Sort Merge Sort --------------------------- Linear Search Binary Search ```
26
Selection Sort
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)
27
Bubble Sort
2. swap adjacent pairs of elements if they are out of order 2. "bubbling" larger elements to the right and smaller one to the left Big Oh: Best => O(n) Worst => O(n^2)
28
Insertion Sort
1. proceed once through the array from left to right | 2. shifting elements as necessary to insert each element into its correct place.
29
Merge Sort
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)
30
Linear Search
1. Iterate across the array from left to right 2. trying to find the target element Big Oh: Best => O(1) Worst => O(n)
31
Binary Search
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)
32
Binary Search | Sudocode
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