Workshop 3 - Iterative Flashcards
Binary Search
Must be sorted.
Check the middle element of array.
If not found determine, which other half of list where it can be located. (EXCLUDE HALF SPACE).
Binary Search - BigO
Best Case:
O(1) - searched value is middle element in list/array
Worst Case:
O(log2n) - when searched value is not in list/array.
Average case:
If data is distributed randomly - each elements has equal chance
Sorted Vs Unsorted
Sorted is better as its in order, and automatically know that its increasing.
Sequential/ Linear Search
Use a while loop to find object in a list, if not found in index one check the next index.
Sequential/Linear Search - BigO
Best Case: O(1)
Worst Case: O(n)
Average Case: N/2
Linear Time Complexity: O(n)
Binary Search
List/array must be sorted.
Check the middle element of the list.
If not found determine which half of list/array item can be located.
– Exclude half elements
Repeat by searching half list array which may contain the element by examining the middle element. Half again.
Repeat till found.
Binary Search - BigO
Best Case: O(1) when searched value is the middle element.
Worst Case: O(log2n) when searched value is not in array.
Needs 1+log2n comparisons
Average Case: If data is distributed randomly
Needs 1+log2n comparisons
COMPLEXITY : O(log2n)
Selection Sort
Works searching one item at a time.
Sorted part left - initially empty.
Unsorted on right part - initially completed list.
Selection Sort will find the largest or smallest elements in the array.
1st Comparisons
2nd Swap
Process is iterated till found.
Selection Sort - BigO
Best Case: O(n2)
Worst Case: O(n2)
Algorithm unsuitable for large data sets.
Bubble Sort
Repeatedly passing through list - swapping adjacent items if in wrong order.
If sorting on the top ascending/descending order the largest/smallest item will bubble to the top.
Process iterated on the whole list until all items considered - list then sorted.
Bubble Sort - BigO
Best Case: O(n2)
If efficiency improved for best case using flag variable = O(n)
Worst Case: O(n2)
Algorithm slow for large data sets.
Insertion Sort
Works by sorting the list item one at a time.
List is split into a sorted and a non-sorted part.
Through each iteration, element is waiting to be sorted and is inserted in its correct location within the sorted list.
Process iterated again and again.
Insertion Sort
Best Case: O(n) data is already sorted.
Worst Case: O(n2)
