Data Structure and Functions For this project you are given the following print_array, and print_list functions: #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.c and print_list.c (containing the print_array and print_list functions) will be compiled with your functions during the correction. Please declare the prototype of the functions print_array and print_list in your sort.h header file Please use the following data structure for doubly linked list: /**

• struct listint_s - Doubly linked list node

• @n: Integer stored in the node

• @prev: Pointer to the previous element of the list

• @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; Please, note this format is used for Quiz and Task questions.

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) … Please use the “short” notation (don’t use constants). Example: O(nk) or O(wn) should be written O(n). If an answer is required within a file, all your answers files must have a newline at the end.

Tests Here is a quick tip to help you test your sorting algorithms with big sets of random integers: Random.org

Quiz questions Great! You've completed the quiz successfully! Keep going! (Show quiz) Tasks 0. Bubble sort mandatory

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

Prototype: void bubble_sort(int *array, size_t size); You’re expected to print the array after each time you swap two elements (See example below) Write in the file 0-O, the big O notations of the time complexity of the Bubble sort algorithm, with 1 notation per line:

in the best case in the average case in the worst case alex@/tmp/sort$ cat 0-main.c #include <stdio.h> #include <stdlib.h> #include "sort.h"

/**

• main - Entry point

• Return: Always 0 */ int main(void) { int array[] = {19, 48, 99, 71, 13, 52, 96, 73, 86, 7}; size_t n = sizeof(array) / sizeof(array[0]);

  print_array(array, n); printf("\n"); bubble_sort(array, n); printf("\n"); print_array(array, n); return (0); } alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic -std=gnu89 0-bubble_sort.c 0-main.c print_array.c -o bubble alex@/tmp/sort$ ./bubble 19, 48, 99, 71, 13, 52, 96, 73, 86, 7

19, 48, 71, 99, 13, 52, 96, 73, 86, 7 19, 48, 71, 13, 99, 52, 96, 73, 86, 7 19, 48, 71, 13, 52, 99, 96, 73, 86, 7 19, 48, 71, 13, 52, 96, 99, 73, 86, 7 19, 48, 71, 13, 52, 96, 73, 99, 86, 7 19, 48, 71, 13, 52, 96, 73, 86, 99, 7 19, 48, 71, 13, 52, 96, 73, 86, 7, 99 19, 48, 13, 71, 52, 96, 73, 86, 7, 99 19, 48, 13, 52, 71, 96, 73, 86, 7, 99 19, 48, 13, 52, 71, 73, 96, 86, 7, 99 19, 48, 13, 52, 71, 73, 86, 96, 7, 99 19, 48, 13, 52, 71, 73, 86, 7, 96, 99 19, 13, 48, 52, 71, 73, 86, 7, 96, 99 19, 13, 48, 52, 71, 73, 7, 86, 96, 99 13, 19, 48, 52, 71, 73, 7, 86, 96, 99 13, 19, 48, 52, 71, 7, 73, 86, 96, 99 13, 19, 48, 52, 7, 71, 73, 86, 96, 99 13, 19, 48, 7, 52, 71, 73, 86, 96, 99 13, 19, 7, 48, 52, 71, 73, 86, 96, 99 13, 7, 19, 48, 52, 71, 73, 86, 96, 99 7, 13, 19, 48, 52, 71, 73, 86, 96, 99

7, 13, 19, 48, 52, 71, 73, 86, 96, 99 alex@/tmp/sort$ Repo:

GitHub repository: sorting_algorithms File: 0-bubble_sort.c, 0-O

1. Insertion sort mandatory

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

Prototype: void insertion_sort_list(listint_t **list); You are not allowed to modify the integer n of a node. You have to swap the nodes themselves. You’re expected to print the list after each time you swap two elements (See example below) Write in the file 1-O, the big O notations of the time complexity of the Insertion sort algorithm, with 1 notation per line:

in the best case in the average case in the worst case alex@/tmp/sort$ cat 1-main.c #include <stdio.h> #include <stdlib.h> #include "sort.h"

/**

• create_listint - Creates a doubly linked list from an array of integers

• @array: Array to convert to a doubly linked list

• @size: Size of the array

• Return: Pointer to the first element of the created list. NULL on failure */ listint_t *create_listint(const int *array, size_t size) { listint_t *list; listint_t *node; int *tmp;

  list = NULL; while (size--) { node = malloc(sizeof(*node)); if (!node) return (NULL); tmp = (int *)&node->n; *tmp = array[size]; node->next = list; node->prev = NULL; list = node; if (list->next) list->next->prev = list; } return (list); }

/**

• main - Entry point

• Return: Always 0 */ int main(void) { listint_t *list; int array[] = {19, 48, 99, 71, 13, 52, 96, 73, 86, 7}; size_t n = sizeof(array) / sizeof(array[0]);

  list = create_listint(array, n); if (!list) return (1); print_list(list); printf("\n"); insertion_sort_list(&list); printf("\n"); print_list(list); return (0); } alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic -std=gnu89 1-main.c 1-insertion_sort_list.c print_list.c -o insertion alex@/tmp/sort$ ./insertion 19, 48, 99, 71, 13, 52, 96, 73, 86, 7

19, 48, 71, 99, 13, 52, 96, 73, 86, 7 19, 48, 71, 13, 99, 52, 96, 73, 86, 7 19, 48, 13, 71, 99, 52, 96, 73, 86, 7 19, 13, 48, 71, 99, 52, 96, 73, 86, 7 13, 19, 48, 71, 99, 52, 96, 73, 86, 7 13, 19, 48, 71, 52, 99, 96, 73, 86, 7 13, 19, 48, 52, 71, 99, 96, 73, 86, 7 13, 19, 48, 52, 71, 96, 99, 73, 86, 7 13, 19, 48, 52, 71, 96, 73, 99, 86, 7 13, 19, 48, 52, 71, 73, 96, 99, 86, 7 13, 19, 48, 52, 71, 73, 96, 86, 99, 7 13, 19, 48, 52, 71, 73, 86, 96, 99, 7 13, 19, 48, 52, 71, 73, 86, 96, 7, 99 13, 19, 48, 52, 71, 73, 86, 7, 96, 99 13, 19, 48, 52, 71, 73, 7, 86, 96, 99 13, 19, 48, 52, 71, 7, 73, 86, 96, 99 13, 19, 48, 52, 7, 71, 73, 86, 96, 99 13, 19, 48, 7, 52, 71, 73, 86, 96, 99 13, 19, 7, 48, 52, 71, 73, 86, 96, 99 13, 7, 19, 48, 52, 71, 73, 86, 96, 99 7, 13, 19, 48, 52, 71, 73, 86, 96, 99

7, 13, 19, 48, 52, 71, 73, 86, 96, 99 alex@/tmp/sort$ Repo:

GitHub repository: sorting_algorithms File: 1-insertion_sort_list.c, 1-O

2. Selection sort mandatory

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

Prototype: void selection_sort(int *array, size_t size); You’re expected to print the array after each time you swap two elements (See example below) Write in the file 2-O, the big O notations of the time complexity of the Selection sort algorithm, with 1 notation per line:

in the best case in the average case in the worst case alex@/tmp/sort$ cat 2-main.c #include <stdio.h> #include <stdlib.h> #include "sort.h"

/**

• main - Entry point

• Return: Always 0 */ int main(void) { int array[] = {19, 48, 99, 71, 13, 52, 96, 73, 86, 7}; size_t n = sizeof(array) / sizeof(array[0]);

  print_array(array, n); printf("\n"); selection_sort(array, n); printf("\n"); print_array(array, n); return (0); } alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic -std=gnu89 2-main.c 2-selection_sort.c print_array.c -o select alex@/tmp/sort$ ./select 19, 48, 99, 71, 13, 52, 96, 73, 86, 7

7, 48, 99, 71, 13, 52, 96, 73, 86, 19 7, 13, 99, 71, 48, 52, 96, 73, 86, 19 7, 13, 19, 71, 48, 52, 96, 73, 86, 99 7, 13, 19, 48, 71, 52, 96, 73, 86, 99 7, 13, 19, 48, 52, 71, 96, 73, 86, 99 7, 13, 19, 48, 52, 71, 73, 96, 86, 99 7, 13, 19, 48, 52, 71, 73, 86, 96, 99

7, 13, 19, 48, 52, 71, 73, 86, 96, 99 alex@/tmp/sort$ Repo:

GitHub repository: sorting_algorithms File: 2-selection_sort.c, 2-O

3. Quick sort mandatory

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

Prototype: void quick_sort(int *array, size_t size); You must implement the Lomuto partition scheme. The pivot should always be the last element of the partition being sorted. You’re expected to print the array after each time you swap two elements (See example below) Write in the file 3-O, the big O notations of the time complexity of the Quick sort algorithm, with 1 notation per line:

in the best case in the average case in the worst case alex@/tmp/sort$ cat 3-main.c #include <stdio.h> #include <stdlib.h> #include "sort.h"

/**

• main - Entry point

• Return: Always 0 */ int main(void) { int array[] = {19, 48, 99, 71, 13, 52, 96, 73, 86, 7}; size_t n = sizeof(array) / sizeof(array[0]);

  print_array(array, n); printf("\n"); quick_sort(array, n); printf("\n"); print_array(array, n); return (0); } alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic -std=gnu89 3-main.c 3-quick_sort.c print_array.c -o quick alex@/tmp/sort$ ./quick 19, 48, 99, 71, 13, 52, 96, 73, 86, 7

7, 48, 99, 71, 13, 52, 96, 73, 86, 19 7, 13, 99, 71, 48, 52, 96, 73, 86, 19 7, 13, 19, 71, 48, 52, 96, 73, 86, 99 7, 13, 19, 71, 48, 52, 73, 96, 86, 99 7, 13, 19, 71, 48, 52, 73, 86, 96, 99 7, 13, 19, 48, 71, 52, 73, 86, 96, 99 7, 13, 19, 48, 52, 71, 73, 86, 96, 99

7, 13, 19, 48, 52, 71, 73, 86, 96, 99 alex@/tmp/sort$ Repo:

GitHub repository: sorting_algorithms File: 3-quick_sort.c, 3-O