1. FreeCodeCamp - Algorithms and Data Structures
Algorithm: a set of instructions to finish a task
Types of searches:
Simple/Sequential/Linear [ O (n) ]
- searching through one record at a time in order, in a linear fashion.
- searching first to last
Code:
package main
import "fmt"
// linear search searches a list for the target and returns the index in the list if found
func linear_search(list []int, target int) (int, bool) {
for i := 0; i < len(list); i++ {
if list[i] == target {
return i, true
}
}
return 0, false
}
func main() {
list := []int{1, 412, 41, 561, 612, 513, 51, 421, 1, 31, 31, 51, 51, 351, 51, 51, 2421, 41, 4124}
x, found := linear_search(list, 22)
if found {
fmt.Println("INDEX:", x)
} else {
fmt.Println("NO VALUES FOUND.")
}
}
Binary Search [ O (log n) ]
Data List (Input) -> Index Position of Target (Output) or Does not Exist Return (Output)
- Requires sorted data.
- Searches through data by eliminating half of results by comparing high and lows from target.
Code:
package main
import (
"fmt"
"math"
"sort"
)
// binarySearch returns the index and true or false whether the target is found in the list.
func binarySearch(list []int, target int) (int, bool) {
first := 0
last := len(list) - 1
for first <= last {
midpoint := math.Floor(float64(first+last) / 2)
if list[int(midpoint)] == target {
return int(midpoint), true
} else if list[int(midpoint)] < target {
first = int(midpoint) + 1
} else {
last = int(midpoint) - 1
}
}
return 0, false
}
// recursiveBinarySearch returns true or false whether target is found in the list using recursive.
func recursiveBinarySearch(list []int, target int) bool {
if len(list) == 0 {
return false
} else {
midpoint := math.Floor(float64(len(list)) / 2)
if list[int(midpoint)] == target {
return true
} else if list[int(midpoint)] < target {
return recursiveBinarySearch(list[int(midpoint)+1:], target)
} else {
return recursiveBinarySearch(list[:int(midpoint)], target)
}
}
}
func main() {
list := []int{1, 7, 2, 4, 3, 8, 6, 5}
// Sorted: 1,2,3,4,5,6,7,8
sort.Ints(list)
/*x, found := binarySearch(list, 10)
if found {
fmt.Println("INDEX:", x)
} else {
fmt.Println("NO VALUES FOUND.")
}*/
y := recursiveBinarySearch(list, 11)
fmt.Println("Target Found:", y)
}
Correctness and Efficiency:
Efficiency measured by Time Complexity (how fast algorithm completes) and Space Complexity measured by amount of memory taken to run the algorithm (until it finishes). Needs a good balance of low time and low space.
Use worst case scenario as the benchmark for efficiency. EX: Using the largest problem.
Big O:
Theoretical definition of the complexity of an algorithm as a function of the size. Basically, a notation to describe complexity.
Measures complexity as the input size grows.
Variable= O(n)
// O is measure of order of magnitude of complexity.
// n is the number of inputs. Function of the size.
O(1) // constant time, time complexity is constant no matter how big the input grows.
O(n) //
O(log n) // Logarithmic Runtime
O(n^2) // Quadratic Runtime
O(n^3) // Cubic Runtime
O( n log n) // Quasilinear Runtime
O(x^n) // Exponential Runtime
O(n!) // Factorial Runtime
Data Structures:
Linked Lists: A list that contains a head and tail node and each node contains reference to next node like a chain.
Types:
- Doubly Linked List, each node contains reference to node forward and backwards of itself.
- Single , each node contains reference to the node in front of it going towards the tail.
Node Struct:
- data
- next node pointer
Linked List Struct:
- head node
- length (optional)
Prepend , add node to the head
Append , add node to the tail
Insert, add node at any point in the list
Sorting Algorithms:
Merge Sort, a sort that keeps splitting an unsorted array into halves until single item arrays exist in pairs for left and right sides. Then perform merge function to sort the pairs back up to the top of the tree using recursive.
Merge Code: merging two sorted lists
package main
import "fmt"
func merge(left, right []int) []int {
leftCount := 0
rightCount := 0
answer := []int{}
for leftCount < len(left) && rightCount < len(right) {
if left[leftCount] < right[rightCount] {
answer = append(answer, left[leftCount])
leftCount++
} else {
answer = append(answer, right[rightCount])
rightCount++
}
}
for ; leftCount < len(left); leftCount++ {
answer = append(answer, left[leftCount])
}
for ; rightCount < len(right); rightCount++ {
answer = append(answer, right[rightCount])
}
return answer
}
func main() {
x := []int{1, 2, 3}
y := []int{5, 6, 8}
merged := merge(x, y)
fmt.Println(merged)
}
MergeSort Code O(nlogn): Splitting lists into halves and calling mergeSort and merge recursively
package main
import (
"fmt"
)
func mergeSort(list []int) []int {
// If list only have 1 number or none, return it.
if len(list) < 2 {
return list
}
// Split recursion
left := mergeSort(list[:len(list)/2])
right := mergeSort(list[len(list)/2:])
return merge(left, right)
}
func merge(left, right []int) []int {
answer := []int{}
leftCount := 0
rightCount := 0
for leftCount < len(left) && rightCount < len(right) {
if left[leftCount] < right[rightCount] {
answer = append(answer, left[leftCount])
leftCount++
} else {
answer = append(answer, right[rightCount])
rightCount++
}
}
for ; leftCount < len(left); leftCount++ {
answer = append(answer, left[leftCount])
}
for ; rightCount < len(right); rightCount++ {
answer = append(answer, right[rightCount])
}
return answer
}
func main() {
unsortedArray := []int{8, 2, 5, 3, 4, 7, 6, 1}
sortedArray := mergeSort(unsortedArray)
fmt.Println(sortedArray)
}
BogoSort: shuffling an array and checking whether its sorted.
package main
import (
"fmt"
"math/rand"
"time"
)
// isSorted checks whether a list is sorted by comparing first and next value.
func isSorted(list []int) bool {
for i, _ := range list {
if i != (len(list) - 1) {
if list[i] > list[i+1] {
return false
}
}
}
return true
}
// bogoSort shuffles a list.
func bogoSort(list *[]int) {
rand.Shuffle(len(*list), func(i, j int) {
(*list)[i], (*list)[j] = (*list)[j], (*list)[i]
})
}
func main() {
rand.Seed(time.Now().UnixNano())
x := []int{4, 1, 7, 5, 8}
tries := 0
for {
tries++
fmt.Println(tries)
bogoSort(&x)
fmt.Println(x)
if isSorted(x) {
break
}
}
fmt.Println(x)
}
SelectionSort O(n^2): selecting the min element and appending to a new array and shrinking unsorted array and repeating the process until all unsorted elements are used to created a sorted array.
package main
func selectionSort(list *[]int) {
sorted := make([]int, 0, len(*list))
unSorted := *list
for i := 0; i < len(*list); i++ {
min := unSorted[0]
index := 0
for i, e := range unSorted {
if e <= min {
min = e
index = i
}
}
sorted = append(sorted, (unSorted)[index])
if index == 0 {
unSorted = unSorted[1:]
} else if index == (len(*list) - 1) {
unSorted = unSorted[:index]
} else {
unSorted = append(unSorted[0:index], unSorted[index+1:]...)
}
}
*list = sorted
}
/*func main() {
x := []int{4, 6, 3, 2, 9, 7, 3, 5}
fmt.Println(x)
selectionSort(&x)
fmt.Println(x)
}*/
QuickSort O(nlogn) or O(n^2): using a pivot and creating left and right array which holds elements less or greater than pivot and merging them in the end to create a sorted array. The left and right are run through quicksort recursively.
package main
//import "fmt"
func quickSort(list []int) []int {
if len(list) <= 1 {
return list
}
pivot := make([]int, 1)
pivot[0] = list[0]
leftList := []int{}
rightList := []int{}
for i := 1; i < len(list); i++ {
if list[i] > pivot[0] {
rightList = append(rightList, list[i])
} else {
leftList = append(leftList, list[i])
}
}
leftSublist := quickSort(leftList)
rightSublist := quickSort(rightList)
answer := []int{}
answer = append(leftSublist, pivot...)
answer = append(answer, rightSublist...)
return answer
}
/*func main() {
x := []int{4, 6, 3, 2, 9, 7, 3, 5}
fmt.Println(quickSort(x))
}*/
Comments
Post a Comment