Algorithms

---

• Algorithms implemented in different languages

Search

---

Binary search

• Complexity:
  • Time: O(log(n)), θ(log(n)), Ω(1)
  • Space: O(n)
• Impl:
  • C++: binary_search.cpp
  • Golang: binarysearch.go
  • Python3: binary_search.py
  • Rust: binary_search.rs
  • Typescript: binarySearch.ts

Linear search

• Complexity:
  • Time: O(n), θ(n), Ω(1)
  • Space: O(n)
• Impl:
  • C++: linear_search.cpp
  • Golang: linearsearch.go
  • Python3: linear_search.py
  • Rust: linear_search.rs
  • Typescript: linearSearch.ts

Sort

---

Bubble sort

• Complexity:
  • Time: O(n²), θ(n²), Ω(n)
  • Space: O(1)
• Impl:
  • C++: bubble_sort.cpp
  • Golang: bubblesort.go
  • Python3: bubble_sort.py
  • Rust: bubble_sort.rs
  • Typescript: bubbleSort.ts

Counting sort

• Complexity:
  • Time: O(n+k), θ(n+k), Ω(n+k)
  • Space: O(n+k)
• Impl:
  • C++: counting_sort.cpp
  • Golang: countingsort.go
  • Python3: counting_sort.py
  • Rust: counting_sort.rs
  • Typescript: countingSort.ts

Heap sort

• Complexity:
  • Time: O(n log(n)), θ(n log(n)), Ω(n log(n))
  • Space: O(n)
• Impl:
  • C++: heap_sort.cpp
  • Golang: heapsort.go
  • Python3: heap_sort.py
  • Rust: heap_sort.rs
  • Typescript: heapSort.ts

Insertion sort

• Complexity:
  • Time: O(n²), θ(n²), Ω(n)
  • Space: O(1)
• Impl:
  • C++: insertion_sort.cpp
  • Golang: insertionsort.go
  • Python3: insertion_sort.py
  • Rust: insertion_sort.rs
  • Typescript: insertionSort.ts

Merge sort

• Complexity:
  • Time: O(n log(n)), θ(n log(n)), Ω(n log(n))
  • Space: O(n)
• Impl:
  • C++: merge_sort.cpp
  • Golang: mergesort.go
  • Python3: merge_sort.py
  • Rust: merge_sort.rs
  • Typescript: mergeSort.ts

Quick sort

• Complexity:
  • Time: O(n²), θ(n log n), Ω(n log n)
  • Space: O(n)
• Impl:
  • C++: quick_sort.cpp
  • Golang: quicksort.go
  • Python3: quick_sort.py
  • Rust: quick_sort.rs
  • Typescript: quickSort.ts

Selection sort

• Complexity:
  • Time: O(n²), Θ(n²), θ(n log(n)), Ω(n²)
  • Space: O(n)
• Impl:
  • C++: selection_sort.cpp
  • Golang: selectionsort.go
  • Python3: selection_sort.py
  • Rust: selection_sort.rs
  • Typescript: selectionSort.ts

Shell sort

• Complexity:
  • Time: O(n(log(n))²), O(n²), Θ(n(log(n))²), Θ(n²), Ω(n log(n))
  • Space: O(1)
• Impl:
  • C++: shell_sort.cpp
  • Golang: shellsort.go
  • Python3: shell_sort.py
  • Rust: shell_sort.rs
  • Typescript: shellSort.ts