14-Jul-2021
Linear Search
Finding element from array
from left to right, searching specific elements
Pseudocode:
For i items, from 0 to i-1 times
→search for specific element for each item, then stop
→if no, move to next one
→if yes, return true
Worst case: need to look through everything even target is not inside the array
Best case: could find it immediately and not complex, could find immediately
Binary Search
Comparing with linear search , it is more efficient, but need to fulfill conditions and more complex to code
divide the array in half and look for the half that contains specific elements
→the array must first be sorted
My question: if the amount of data is in odd number, could it run binary?
→ this one is for odd numbered array
→could you write one for even number array?
Pseudocode:
Repeat until the (sub)array is 0
→Calculate the middle point of the current array
→if target is at the middle, stop
→Otherwise, if the target is less than what’s at the middle, repeat, changing the end point to be just to the left of the middle
→Otherwise, if the target is more than what’s at the middle, repeat, changing the end point to be just to the right of the middle
Worst case: even if all halves were run through for (log n times), there are no elements in the array that fit , or in the middle of the last half
Best case: the element I am looking for is right in the middle of the array, so I could find it is the first time
Bubble Sort
Move higher element in the right, and lower to the left
My Pseudocode:
Compare the i and i+1 elements for n-2 times
→if i+1 element larger than i element
→ →swap and compare with i+1 and i+2 elements
→if i element larger than i+1 element
→ → move and compare with i+1 and i+2 elements
Problem: no parameter to tell the program when to stop
Tutor:
Set swap counter(???) to non-zero value (so that is could start, look at below code)
Repeat until the swap counter is 0
→Reset swap counter to 0
→Look at each adjacent pair
→ →if two adjacent elements are not in order, swap them and add one to the swap counter
what is swap counter →like the i in my pseudocode
Worst case: the swap need to repeat n² times to finish as the smallest number is in the leftmost in array/ n elements in array is reversed
Best case: no swap needed in the first time, only run for n-2 times to check everything is sorted already
Selection sort
Find the smallest unsorted and add it to the end of the sorted list
My pseudocode:
repeat below as all numbers are sorted
→search through all elements in array
→find the smallest one among all
→swap it with the one in the beginning
Problem: not all and not beginning, it just won’t end if you write it this way
Tutor pseudocode:
Repeat until no unsorted elements remain:
→Search the unsorted part of the data to find the smallest value
→Swap the smallest found value with the first element of the unsorted part
Worst case: need to sway every time, it would then search for n² times to find and swap the number, as there are n elements to look through and you repeat finding it n times
Best case: everything was sorted, you still need to run ntime, which is n² coz you still need to go through n elements for n times — same with worse
Recursion
Call itself as part of its execution → so short that make it more beautiful, without loops
Factorial function (n!) → fact(n) in computer
fact(1) = 1
fact(2) = 2*1
fact(3) = 3*2*1
fact(4) = 4*3*2*1
fact(5) = 5*4*3*2*1
.
.
.
fact(n) = n*fact(n-1)
recursive definition
recursive function has two cases that could apply, given any input
- base case: triggered will terminate the recursive process(without will make infinite loop)
-recursive case: recursion occur (how to make everything occur →unlike loop)
fact(1) = 1 ←base case
fact(2) = 2*1
fact(3) = 3*2*1
fact(4) = 4*3*2*1
fact(5) = 5*4*3*2*1
.
.
.
fact(n) = n*fact(n-1)
in fact(int n)
{
if( n==1)
{
return 1;
}
else
{
return n*fact(n-1)
}
Generally, recursive functions replace loops in non-recursive functions
Could be more than one base cases and recursive cases
Collatz conjecture — apply to positive integers and it is always possible to get “back to 1” if you follow steps:
- if n == 1, stop
-Otherwise, if n is even, repeat this process on n/2
-Otherwise, if n is odd, repeat this process on 3n + 1
Merge sort
Sort smaller arrays and then merge them together
Require recursion
Pseudocode:
Leave if the no of array is 1
Sort left half of array (if n>1)
Sort right half of array (if n>1)
Merge two halves together
Worst: split n elements up and then combine tgt, doublin gthe sorted subarrays as we build them up (n log n)
Best: already sorted but still do everything once — theta notation (n log n)