This project introduces concepts of data structures and algorithms in programming. It is meant to be done by groups of two students. Each group of two should pair program for at least the mandatory part.
At the end of this project students 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
- Resources from Holberton
- Read Sorting algorithm, Big O notation.
- Watch 15 sorting algorithms in 6 minutes, Sorting algorithms animations
- Here is a quick tip to help you test your sorting algorithms with big sets of random integers: Random.org
- Other resources independently discovered
- e-lectures from VisuAlgo
- Time Complexity from official Python documentation
- CS 5050 Handout
- Allowed editors:
vi,vim,emacs - All your files will be compiled on Ubuntu 14.04 LTS
- Your programs and functions will be compiled with
gcc 4.8.4(C90) using the flags-Wall -Werror -Wextra and -pedantic
- All your files should end with a new line
- A
README.mdfile, at the root of the folder of the project is mandatory - Your code should use the
Bettystyle. It will be checked usingbetty-style.plandbetty-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.cfiles are showed 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 ownmain.cfiles at compilation. Ourmain.cfiles might be different from the one showed 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.
- For this project you are given the following
print_array, andprint_listfunctions:
#include <stdlib.h>
#include <stdio.h>
/**
* print_array - Prints an array of integers
*
* @array: The array to be printed
* @size: Number of elements in @array
*/
void print_array(const int *array, size_t size)
{
size_t i;
i = 0;
while (array && i < size)
{
if (i > 0)
printf(", ");
printf("%d", array[i]);
++i;
}
printf("\n");
}#include <stdio.h>
#include "sort.h"
/**
* print_list - Prints a list of integers
*
* @list: The list to be printed
*/
void print_list(const listint_t *list)
{
int i;
i = 0;
while (list)
{
if (i > 0)
printf(", ");
printf("%d", list->n);
++i;
list = list->next;
}
printf("\n");
}- Our files
print_array.candprint_list.c(containing theprint_arrayandprint_listfunctions) will be compiled with your functions during the correction. - Please declare the prototype of the functions
print_arrayandprint_listin yoursort.hheader file - Please use the following data structure for doubly linked list:
/**
* struct listint_s - Doubly linked list node
*
* @n: Integer stored in the node
* @next: Pointer to the next element of the list
*/
typedef struct listint_s
{
const int n;
struct listint_s *prev;
struct listint_s *next;
} listint_t;For almost all sorting algorithms you will have to work on, you will be asked to write a file containing the big O notation of the time complexity of the algorithm. Please use this format:
O(1)O(n)O(n!)- n square ->
O(n^2) - log(n) ->
O(log(n)) - n * log(n) ->
O(nlog(n)) - ...
- Please use the "short" notation (don't use constants). Example:
O(nk)orO(wn)should be writtenO(n). All your answers files must have an empty line at the end.
| Task # | Type | File name and link | Short description |
|---|---|---|---|
| 0 | Mandatory | Write a function that sorts an array of integers in ascending order using the Bubble sort algorithm Write a function that sorts an array of integers in ascending order using the Bubble sort algorithm void bubble_sort(int *array, size_t size);array after each time you swap two elements (See example below)Write in the file |
|
| 1 | Mandatory | Write a function that sorts a doubly linked list of integers in ascending order using the Insertion sort algorithmvoid insertion_sort_list(listint_t **list);n of a node. You have to swap the nodes themselves.list after each time you swap two elements (See example below)Write in the file |
|
| 2 | Mandatory | Write a function that sorts an array of integers in ascending order using the Selection sort algorithmvoid selection_sort(int *array, size_t size);array after each time you swap two elements (See example below)Write in the file |
|
| 3 | Mandatory | Write a function that sorts an array of integers in ascending order using the Quick sort algorithmvoid quick_sort(int *array, size_t size);Lomuto partition scheme.array after each time you swap two elements (See example below)Write in the file |
|
| 4 | Mandatory | What is the time complexity of this function / algorithm? |
|
| { |
int i;
for (i = 0; i < n; i++)
{
printf("[%d]\n", i);
}
} | 5 | Mandatory | |What is the time complexity of this function / algorithm? | 6 | Mandatory | |What is the time complexity of this function / algorithm? | 7 | Mandatory | |What is the time complexity of this function / algorithm? | 8 | Mandatory | |What is the time complexity of this function / algorithm? | 9 | Mandatory | |What is the time complexity of this function / algorithm? | 10 | Mandatory | |What is the time complexity of this function / algorithm? | 11 | Mandatory | |What is the time complexity of this function / algorithm? | 12 | Mandatory | |What is the time complexity of this function / algorithm? | 13 | Mandatory | |What is the time complexity of this function / algorithm? | 14 | Mandatory | |What is the time complexity of this function / algorithm? | 15 | Mandatory | |
What are the time complexities of those operations on an unsorted array (one answer per line):
What are the time complexities of those operations on a singly linked list (one answer per line):
What are the time complexities of those operations on a doubly linked list (one answer per line):
What are the time complexities of those operations on an unsorted Python 3 list (one answer per line):
What are the time complexities of those operations on a stack (one answer per line):
What are the time complexities of those operations on a queue (one answer per line):
What are the time complexities of those operations on a hash table (one answer per line) - with the implementation you used during the previous Hash Table C project (chaining):
 |
 |
|---|---|
Carrie Ybay  |
Elaine Yeung |
- Readme template from GitHub https://guides.github.com/features/wikis/