/sorting_algorithms

0x1B. C - Sorting algorithms & Big O

Primary LanguageC

0x1B. C - Sorting algorithms & Big O

oooooooooo.  ooooo   .oooooo.         .oooooo.
`888'   `Y8b `888'  d8P'  `Y8b       d8P'  `Y8b
 888     888  888  888              888      888
 888oooo888'  888  888              888      888
 888    `88b  888  888     ooooo    888      888
 888    .88P  888  `88.    .88'     `88b    d88'
o888bood8P'  o888o  `Y8bood8P'       `Y8bood8P'

Learning Objectives

General

  • At least four different sorting algorithms
  • What is the Big O notation, and how to evaluate the time complexity of an algorithm
  • How to select the best sorting algorithm for a given input
  • What is a stable sorting algorithm

Big O Asinthotic notation in time complexity

Format used for O notation

  • O(1)
  • O(n)
  • O(n!)
  • n square -> O(n^2)
  • log(n) -> O(log(n))
  • n * log(n) -> O(nlog(n))
  • n + k -> O(n+k)

The “short” notation (don’t use constants). Example: O(nk) or O(wn) will be written O(n).

About O files

In each line will contain the following big O notation about time complexity

  • in the best case
  • in the average case
  • in the worst case

Environment

C programming language C programming language C programming language

  • Language: C

  • OS: Ubuntu 20.04 LTS

  • Editor: VIM 8.1.2269

  • Compiler: gcc 9.3.0

    • flags: -Wall -Werror -Wextra -pedantic -std=gnu89

  • Style guidelines: Betty style

  • Compilation: to compile all the algorithms use ./compile_all.sh with sudo privileges

Autor

Adebayo Ayowale
Noran S Abdelfatth