/sorting_algorithms

Primary LanguageC

0x1B. C - Sorting algorithms & Big O

This is a collaborative project on sorting algorithm

Background Context

This project is meant to be done by groups of two students.

Contributors

Bubble sort image

RESOURCES

Learning Objectives

At the end of this project, we are expected to be able to explain to anyone, without the help of google

  • 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

Requirements

General

  • Allowed editors: vi, vim, emacs
  • All your files will be compiled on Ubuntu 20.04 LTS using gcc, using the options -Wall -Werror -Wextra -pedantic -std=gnu89
  • All your files should end with a new line
  • A README.md file, at the root of the folder of the project, is mandatory
  • Your code should use the Betty style. It will be checked using betty-style.pl and betty-doc.pl
  • You are not allowed to use global variables
  • No more than 5 functions per file
  • Unless specified otherwise, you are not allowed to use the standard library. Any use of functions like printf, puts, … is totally forbidden.
  • In the following examples, the main.c files are shown as examples. You can use them to test your functions, but you don’t have to push them to your repo (if you do we won’t take them into account). We will use our own main.c files at compilation. Our main.c files might be different from the one shown in the examples
  • The prototypes of all your functions should be included in your header file called sort.h
  • Don’t forget to push your header file
  • All your header files should be include guarded
  • A list/array does not need to be sorted if its size is less than 2.

Tasks

0 Bubble sort

Write a function that sorts an array of integers in ascending order using the Bubble sort algorithm

1 Insertion sort

Write a function that sorts a doubly linked list of integers in ascending order using the Insertion sort algorithm

2 Selection sort

Write a function that sorts an array of integers in ascending order using the Selection sort algorithm

3 Quick sort

Write a function that sorts an array of integers in ascending order using the Quick sort algorithm Write a function that sorts an array of integers in ascending order using the Quick sort algorithm