Skip to content

BoykoPetevBoev/SoftUni-Algorithms-Fundamentals-November-2020

Repository files navigation

Sorting Algorithms

Name Best Average Worst Memory Stable Method
Selection Sort n2 n2 n2 1 No Selection
Bubble Sort n n2 n2 1 Yes Exchanging
Insertion Sort n n2 n2 1 Yes Insertion
Merge Sort n*log(n) n*log(n) n*log(n) 1 (or n) Yes Merging
Quick Sort n*log(n) n*log(n) n2 log(n) Depends Partitioning

Selection Sort

Selection Sort

Simple, but inefficient algorithm. Swap the first with the min element on the right, then the second, etc.

  • Memory: O(1)
  • Stable: No
  • Method: Selection

Bubble Sort

Bubble Sort

Simple, but inefficient algorithm. Swaps to neighbor elements when not in order until sorted.

  • Memory: O(1)
  • Stable: Yes
  • Method: Exchanging

Insertion Sort

Insertion Sort

Simple, but inefficient algorithm. Move the first unsorted element left to its place.

  • Memory: O(1)
  • Stable: Yes
  • Method: Insertion

Merge Sort

Merge Sort

Efficient sorting algorithm.

  1. Divide the list into sub-lists (typically 2 sub-lists)
  2. Sort each sub-list (recursively call merge-sort)
  3. Merge the sorted sub-lists into a single list

Best, average and worst case: O(n*log(n))

  • Memory: O(n) / O(1)
  • Stable: Yes
  • Method: Merging

Quick Sort

Quick Sort

Quick Sort

Efficient sorting algorithm.

  1. Choose a pivot
  2. Move smaller elements left & larger right
  3. sort left & right

Best & average case: O(n*log(n)); Worst: O(n2)

  • Memory: O(log(n))
  • Stable: Depends
  • Method: Partitioning

About

RECURSION / SEARCHING / SORTING / GRAPH THEORY

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published