0x1B. C - Sorting algorithms & Big O
Author - Junior Mwadime Muema
Resources Read or watch:
Sorting algorithm Big O notation Sorting algorithms animations 15 sorting algorithms in 6 minutes (WARNING: The following video can trigger seizure/epilepsy. It is not required for the project, as it is only a funny visualization of different sorting algorithms) CS50 Algorithms explanation in detail by David Malan All about sorting algorithms
More Info 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
Copyright (c) 2023 JUNIOR MWADIME MUEMA
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.