C - Sorting algorithms & Big O

This project was on Sorting algorithms & Big O in C.

Summary

I learnt about 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 and also what a stable sorting algorithm is.

Requirements

• Language: C
• Standard libraries are not allowed, except specified. i.e.printf, puts, etc. are not allowed.
• OS: Ubuntu 20.04 LTS
• Compiler: gcc 4.8.4
• Compiler options: -Wall -Werror -Wextra -pedantic -std=gnu89
• Style guidelines: Betty style

Files

Each file contains the solution to a task in the project.

Each of the *-O files contains the big O notations of the time complexity of the different sorting algorithm, with 1 notation per line:

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

• 0-bubble_sort.c: A function that sorts an array of integers in ascending order using the Bubble sort algorithm.
  • 0-O: The time complexity of the Bubble sort algorithm.
• 1-insertion_sort_list.c: A function that sorts a doubly linked list of integers in ascending order using the Insertion sort algorithm.
  • 1-O: The time complexity of the Insertion sort algorithm.
• 2-selection_sort.c: A function that sorts an array of integers in ascending order using the Selection sort algorithm.
  • 2-O: The time complexity of the Selection sort algorithm.
• 3-quick_sort.c: A function that sorts an array of integers in ascending order using the Quick sort algorithm.
  • 3-O: The time complexity of the Quick sort algorithm.
• 100-shell_sort.c: A function that sorts an array of integers in ascending order using the Shell sort algorithm, using the Knuth sequence.
• 101-cocktail_sort_list.c: A function that sorts a doubly linked list of integers in ascending order using the Cocktail shaker sort algorithm.
  • 101-O: The time complexity of the Cocktail shaker sort algorithm.
• 102-counting_sort.c: A function that sorts an array of integers in ascending order using the Counting sort algorithm.
  • 102-O: The time complexity of the Counting sort algorithm.
• 103-merge_sort.c: A function that sorts an array of integers in ascending order using the Merge sort algorithm.
  • 103-O: The time complexity of the Merge sort algorithm.
• 104-heap_sort.c: A function that sorts an array of integers in ascending order using the Heap sort algorithm
  • 104-O: The time complexity of the Heap sort algorithm.
• 105-radix_sort.c: A function that sorts an array of integers in ascending order using the Radix sort algorithm.
• 106-bitonic_sort.c: A function that sorts an array of integers in ascending order using the Bitonic sort algorithm.
  • 106-O: The time complexity of the Bitonic sort algorithm.
• 107-quick_sort_hoare.c: A function that sorts an array of integers in ascending order using the Quick sort algorithm, implemented with the Hoare partition scheme.
  • 107-O: The time complexity of the Quick sort algorithm.
• 1000-sort_deck.c: A function that sorts a deck of cards.
  • deck.h: A header file that contains the used data structures definition for this task.

• sort.h: A Header file containing prototypes for all functions written in the project.
• print_array.c: A function that prints an array of integers. Provided by Alx.
• print_list.c: A function that prints a list of integers. Provided by Alx.
• main_files: A folder of test files. Provided by Alx.

Credits

Work is owned and maintained by Michael C. Iyke and Ebube Ochemba.

Acknowledgement

All work contained in this project was completed as part of the curriculum for Alx. ALX is a leading technology training provider, built to accelerate the careers of young Africans through the technology and professional skills that enable them to thrive in the digital economy. The program prepares students for careers in the tech industry using project-based peer learning. For more information, visit.