Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Group Project On Sorting Algorithms & Big O Notation In Programming

NotificationsYou must be signed in to change notification settings

samuelselasi/sorting_algorithms

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

90 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CAlgorithmData structure

willy-wonka

Resources

Read or watch:

Requirements

General

  • Allowed editors:vi,vim,emacs
  • All your files will be compiled on Ubuntu 20.04 LTS usinggcc, using the options-Wall -Werror -Wextra -pedantic -std=gnu89
  • All your files should end with a new line
  • AREADME.md file, at the root of the folder of the project, is mandatory
  • Your code should use theBetty style. It will be checked usingbetty-style.pl andbetty-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 likeprintf,puts, … is totally forbidden.
  • In the following examples, themain.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 ownmain.c files at compilation. Ourmain.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 calledsort.h
  • Don’t forget to push your header file
  • All your header files should be include guarded
  • Alist/array does not need to be sorted if its size is less than2.

More Info

Data Structure and Functions

For this project you are given the followingprint_array, andprint_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 filesprint_array.c andprint_list.c (containing theprint_array andprint_list functions) will be compiled with your functions during the correction.
  • Please declare the prototype of the functionsprint_array andprint_list in yoursort.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) orO(wn) should be writtenO(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

Tasks

0. Bubble sort

Write a function that sorts an array of integers in ascending order using theBubble 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 file0-O, the big O notations of the time complexity of theBubble sort algorithm, with1 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 bubblealex@/tmp/sort$ ./bubble19, 48, 99, 71, 13, 52, 96, 73, 86, 719, 48, 71, 99, 13, 52, 96, 73, 86, 719, 48, 71, 13, 99, 52, 96, 73, 86, 719, 48, 71, 13, 52, 99, 96, 73, 86, 719, 48, 71, 13, 52, 96, 99, 73, 86, 719, 48, 71, 13, 52, 96, 73, 99, 86, 719, 48, 71, 13, 52, 96, 73, 86, 99, 719, 48, 71, 13, 52, 96, 73, 86, 7, 9919, 48, 13, 71, 52, 96, 73, 86, 7, 9919, 48, 13, 52, 71, 96, 73, 86, 7, 9919, 48, 13, 52, 71, 73, 96, 86, 7, 9919, 48, 13, 52, 71, 73, 86, 96, 7, 9919, 48, 13, 52, 71, 73, 86, 7, 96, 9919, 13, 48, 52, 71, 73, 86, 7, 96, 9919, 13, 48, 52, 71, 73, 7, 86, 96, 9913, 19, 48, 52, 71, 73, 7, 86, 96, 9913, 19, 48, 52, 71, 7, 73, 86, 96, 9913, 19, 48, 52, 7, 71, 73, 86, 96, 9913, 19, 48, 7, 52, 71, 73, 86, 96, 9913, 19, 7, 48, 52, 71, 73, 86, 96, 9913, 7, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

1. Insertion sort

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

  • Prototype:void insertion_sort_list(listint_t **list);
  • You are not allowed to modify the integern of a node. You have to swap the nodes themselves.
  • You’re expected to print thelist after each time you swap two elements (See example below)

Write in the file1-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 insertionalex@/tmp/sort$ ./insertion19, 48, 99, 71, 13, 52, 96, 73, 86, 719, 48, 71, 99, 13, 52, 96, 73, 86, 719, 48, 71, 13, 99, 52, 96, 73, 86, 719, 48, 13, 71, 99, 52, 96, 73, 86, 719, 13, 48, 71, 99, 52, 96, 73, 86, 713, 19, 48, 71, 99, 52, 96, 73, 86, 713, 19, 48, 71, 52, 99, 96, 73, 86, 713, 19, 48, 52, 71, 99, 96, 73, 86, 713, 19, 48, 52, 71, 96, 99, 73, 86, 713, 19, 48, 52, 71, 96, 73, 99, 86, 713, 19, 48, 52, 71, 73, 96, 99, 86, 713, 19, 48, 52, 71, 73, 96, 86, 99, 713, 19, 48, 52, 71, 73, 86, 96, 99, 713, 19, 48, 52, 71, 73, 86, 96, 7, 9913, 19, 48, 52, 71, 73, 86, 7, 96, 9913, 19, 48, 52, 71, 73, 7, 86, 96, 9913, 19, 48, 52, 71, 7, 73, 86, 96, 9913, 19, 48, 52, 7, 71, 73, 86, 96, 9913, 19, 48, 7, 52, 71, 73, 86, 96, 9913, 19, 7, 48, 52, 71, 73, 86, 96, 9913, 7, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

2. Selection sort

Write a function that sorts an array of integers in ascending order using theSelection 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 file2-O, the big O notations of the time complexity of the Selection sort algorithm, with1 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 selectalex@/tmp/sort$ ./select19, 48, 99, 71, 13, 52, 96, 73, 86, 77, 48, 99, 71, 13, 52, 96, 73, 86, 197, 13, 99, 71, 48, 52, 96, 73, 86, 197, 13, 19, 71, 48, 52, 96, 73, 86, 997, 13, 19, 48, 71, 52, 96, 73, 86, 997, 13, 19, 48, 52, 71, 96, 73, 86, 997, 13, 19, 48, 52, 71, 73, 96, 86, 997, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

3. Quick sort

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

  • Prototype:void quick_sort(int *array, size_t size);
  • You must implement theLomuto partition scheme.
  • The pivot should always be the last element of the partition being sorted.
  • You’re expected to print thearray after each time you swap two elements (See example below)

Write in the file3-O, the big O notations of the time complexity of theQuick sort algorithm, with1 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 quickalex@/tmp/sort$ ./quick19, 48, 99, 71, 13, 52, 96, 73, 86, 77, 48, 99, 71, 13, 52, 96, 73, 86, 197, 13, 99, 71, 48, 52, 96, 73, 86, 197, 13, 19, 71, 48, 52, 96, 73, 86, 997, 13, 19, 71, 48, 52, 73, 96, 86, 997, 13, 19, 71, 48, 52, 73, 86, 96, 997, 13, 19, 48, 71, 52, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

4. Shell sort - Knuth Sequence

Write a function that sorts an array of integers in ascending order using theShell sort algorithm, using theKnuth sequence

  • Prototype:void shell_sort(int *array, size_t size);
  • You must use the following sequence of intervals (a.k.a theKnuth sequence):
    • n+1 = n * 3 + 1
    • 1, 4, 13, 40, 121, ...
  • You’re expected to print thearray each time you decrease the interval (See example below).

No big O notations of the time complexity of the Shell sort (Knuth sequence) algorithm needed - as the complexity is dependent on the size of array and gap

alex@/tmp/sort$ cat 100-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");    shell_sort(array, n);    printf("\n");    print_array(array, n);    return (0);}alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic  -std=gnu89 100-main.c 100-shell_sort.c print_array.c -o shellalex@/tmp/sort$ ./shell19, 48, 99, 71, 13, 52, 96, 73, 86, 713, 7, 96, 71, 19, 48, 99, 73, 86, 527, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

5. Cocktail shaker sort

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

  • Prototype:void cocktail_sort_list(listint_t **list);
  • You are not allowed to modify the integern of a node. You have to swap the nodes themselves.
  • You’re expected to print thelist after each time you swap two elements (See example below)

Write in the file101-O, the big O notations of the time complexity of theCocktail shaker sort algorithm, with1 notation per line:

  • in the best case
  • in the average case
  • in the worst case
alex@/tmp/sort$ cat 101-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");    cocktail_sort_list(&list);    printf("\n");    print_list(list);    return (0);}alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic  -std=gnu89 101-main.c 101-cocktail_sort_list.c print_list.c -o cocktailalex@/tmp/sort$ ./cocktail19, 48, 99, 71, 13, 52, 96, 73, 86, 719, 48, 71, 99, 13, 52, 96, 73, 86, 719, 48, 71, 13, 99, 52, 96, 73, 86, 719, 48, 71, 13, 52, 99, 96, 73, 86, 719, 48, 71, 13, 52, 96, 99, 73, 86, 719, 48, 71, 13, 52, 96, 73, 99, 86, 719, 48, 71, 13, 52, 96, 73, 86, 99, 719, 48, 71, 13, 52, 96, 73, 86, 7, 9919, 48, 71, 13, 52, 96, 73, 7, 86, 9919, 48, 71, 13, 52, 96, 7, 73, 86, 9919, 48, 71, 13, 52, 7, 96, 73, 86, 9919, 48, 71, 13, 7, 52, 96, 73, 86, 9919, 48, 71, 7, 13, 52, 96, 73, 86, 9919, 48, 7, 71, 13, 52, 96, 73, 86, 9919, 7, 48, 71, 13, 52, 96, 73, 86, 997, 19, 48, 71, 13, 52, 96, 73, 86, 997, 19, 48, 13, 71, 52, 96, 73, 86, 997, 19, 48, 13, 52, 71, 96, 73, 86, 997, 19, 48, 13, 52, 71, 73, 96, 86, 997, 19, 48, 13, 52, 71, 73, 86, 96, 997, 19, 13, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$* in the best case* in the average case* in the worst case

6. Counting sort

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

  • Prototype:void counting_sort(int *array, size_t size);
  • You can assume that array will contain only numbers>= 0
  • You are allowed to usemalloc andfree for this task
  • You’re expected to print your counting array once it is set up (See example below)
    • This array is of sizek + 1 wherek is the largest number in array

Write in the file102-O, the big O notations of the time complexity of theCounting sort algorithm, with1 notation per line:

  • in the best case
  • in the average case
  • in the worst case
alex@/tmp/sort$ cat 102-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");    counting_sort(array, n);    printf("\n");    print_array(array, n);    return (0);}alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic  -std=gnu89 102-main.c 102-counting_sort.c print_array.c -o countingalex@/tmp/sort$ ./counting19, 48, 99, 71, 13, 52, 96, 73, 86, 70, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 107, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

7. Merge sort

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

  • Prototype:void merge_sort(int *array, size_t size);
  • You must implement thetop-down merge sort algorithm
    • When you divide an array into two sub-arrays, the size of the left array should always be <= the size of the right array. i.e.{1, 2, 3, 4, 5} -> {1, 2}, {3, 4, 5}
    • Sort theleft array before theright array
  • You are allowed to useprintf
  • You are allowed to usemalloc andfree only once (only one call)
  • Output: see example

Write in the file103-O, the big O notations of the time complexity of theMerge sort algorithm, with1 notation per line:

  • in the best case
  • in the average case
  • in the worst case
alex@/tmp/sort$ cat 103-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");    merge_sort(array, n);    printf("\n");    print_array(array, n);    return (0);}alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic  -std=gnu89 103-main.c 103-merge_sort.c print_array.c -o mergealex@/tmp/sort$ ./merge19, 48, 99, 71, 13, 52, 96, 73, 86, 7Merging...[left]: 19[right]: 48[Done]: 19, 48Merging...[left]: 71[right]: 13[Done]: 13, 71Merging...[left]: 99[right]: 13, 71[Done]: 13, 71, 99Merging...[left]: 19, 48[right]: 13, 71, 99[Done]: 13, 19, 48, 71, 99Merging...[left]: 52[right]: 96[Done]: 52, 96Merging...[left]: 86[right]: 7[Done]: 7, 86Merging...[left]: 73[right]: 7, 86[Done]: 7, 73, 86Merging...[left]: 52, 96[right]: 7, 73, 86[Done]: 7, 52, 73, 86, 96Merging...[left]: 13, 19, 48, 71, 99[right]: 7, 52, 73, 86, 96[Done]: 7, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

8. Heap sort

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

  • Prototype:void heap_sort(int *array, size_t size);
  • You must implement thesift-down heap sort algorithm
  • You’re expected to print the array after each time you swap two elements (See example below)

Write in the file104-O, the big O notations of the time complexity of theHeap sort algorithm, with1 notation per line:

  • in the best case
  • in the average case
  • in the worst case
alex@/tmp/sort$ cat 104-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");    heap_sort(array, n);    printf("\n");    print_array(array, n);    return (0);}alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic  -std=gnu89 104-main.c 104-heap_sort.c print_array.c -o heapalex@/tmp/sort$ ./heap19, 48, 99, 71, 13, 52, 96, 73, 86, 719, 48, 99, 86, 13, 52, 96, 73, 71, 719, 86, 99, 48, 13, 52, 96, 73, 71, 719, 86, 99, 73, 13, 52, 96, 48, 71, 799, 86, 19, 73, 13, 52, 96, 48, 71, 799, 86, 96, 73, 13, 52, 19, 48, 71, 77, 86, 96, 73, 13, 52, 19, 48, 71, 9996, 86, 7, 73, 13, 52, 19, 48, 71, 9996, 86, 52, 73, 13, 7, 19, 48, 71, 9971, 86, 52, 73, 13, 7, 19, 48, 96, 9986, 71, 52, 73, 13, 7, 19, 48, 96, 9986, 73, 52, 71, 13, 7, 19, 48, 96, 9948, 73, 52, 71, 13, 7, 19, 86, 96, 9973, 48, 52, 71, 13, 7, 19, 86, 96, 9973, 71, 52, 48, 13, 7, 19, 86, 96, 9919, 71, 52, 48, 13, 7, 73, 86, 96, 9971, 19, 52, 48, 13, 7, 73, 86, 96, 9971, 48, 52, 19, 13, 7, 73, 86, 96, 997, 48, 52, 19, 13, 71, 73, 86, 96, 9952, 48, 7, 19, 13, 71, 73, 86, 96, 9913, 48, 7, 19, 52, 71, 73, 86, 96, 9948, 13, 7, 19, 52, 71, 73, 86, 96, 9948, 19, 7, 13, 52, 71, 73, 86, 96, 9913, 19, 7, 48, 52, 71, 73, 86, 96, 9919, 13, 7, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 9913, 7, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

9. Radix sort

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

  • Prototype:void radix_sort(int *array, size_t size);
  • You must implement theLSD radix sort algorithm
  • You can assume thatarray will contain only numbers>= 0
  • You are allowed to usemalloc andfree for this task
  • You’re expected to print thearray each time you increase yoursignificant digit (See example below)
alex@/tmp/sort$ cat 105-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");    radix_sort(array, n);    printf("\n");    print_array(array, n);    return (0);}alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic  -std=gnu89 105-main.c 105-radix_sort.c print_array.c -o radixalex@/tmp/sort$ ./radix19, 48, 99, 71, 13, 52, 96, 73, 86, 771, 52, 13, 73, 96, 86, 7, 48, 19, 997, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

10. Bitonic sort

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

  • Prototype:void bitonic_sort(int *array, size_t size);
  • You can assume that size will be equal to2^k, wherek >= 0 (whenarray is notNULL …)
  • You are allowed to useprintf
  • You’re expected to print thearray each time you swap two elements (See example below)
  • Output: see example

Write in the file106-O, the big O notations of the time complexity of theBitonic sort algorithm, with1 notation per line:

  • in the best case
  • in the average case
  • in the worst case
alex@/tmp/sort$ cat 106-main.c#include <stdio.h>#include <stdlib.h>#include "sort.h"/** * main - Entry point * * Return: Always 0 */int main(void){    int array[] = {100, 93, 40, 57, 14, 58, 85, 54, 31, 56, 46, 39, 15, 26, 78, 13};    size_t n = sizeof(array) / sizeof(array[0]);    print_array(array, n);    printf("\n");    bitonic_sort(array, n);    printf("\n");    print_array(array, n);    return (0);}alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic  -std=gnu89 106-main.c 106-bitonic_sort.c print_array.c -o bitonicalex@/tmp/sort$ ./bitonic100, 93, 40, 57, 14, 58, 85, 54, 31, 56, 46, 39, 15, 26, 78, 13Merging [16/16] (UP):100, 93, 40, 57, 14, 58, 85, 54, 31, 56, 46, 39, 15, 26, 78, 13Merging [8/16] (UP):100, 93, 40, 57, 14, 58, 85, 54Merging [4/16] (UP):100, 93, 40, 57Merging [2/16] (UP):100, 93Result [2/16] (UP):93, 100Merging [2/16] (DOWN):40, 57Result [2/16] (DOWN):57, 40Result [4/16] (UP):40, 57, 93, 100Merging [4/16] (DOWN):14, 58, 85, 54Merging [2/16] (UP):14, 58Result [2/16] (UP):14, 58Merging [2/16] (DOWN):85, 54Result [2/16] (DOWN):85, 54Result [4/16] (DOWN):85, 58, 54, 14Result [8/16] (UP):14, 40, 54, 57, 58, 85, 93, 100Merging [8/16] (DOWN):31, 56, 46, 39, 15, 26, 78, 13Merging [4/16] (UP):31, 56, 46, 39Merging [2/16] (UP):31, 56Result [2/16] (UP):31, 56Merging [2/16] (DOWN):46, 39Result [2/16] (DOWN):46, 39Result [4/16] (UP):31, 39, 46, 56Merging [4/16] (DOWN):15, 26, 78, 13Merging [2/16] (UP):15, 26Result [2/16] (UP):15, 26Merging [2/16] (DOWN):78, 13Result [2/16] (DOWN):78, 13Result [4/16] (DOWN):78, 26, 15, 13Result [8/16] (DOWN):78, 56, 46, 39, 31, 26, 15, 13Result [16/16] (UP):13, 14, 15, 26, 31, 39, 40, 46, 54, 56, 57, 58, 78, 85, 93, 10013, 14, 15, 26, 31, 39, 40, 46, 54, 56, 57, 58, 78, 85, 93, 100alex@/tmp/sort$

11. Quick Sort - Hoare Partition scheme

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

  • Prototype:void quick_sort_hoare(int *array, size_t size);
  • You must implement theHoare partition scheme.
  • The pivot should always be the last element of the partition being sorted.
  • You’re expected to print thearray after each time you swap two elements (See example below)

Write in the file107-O, the big O notations of the time complexity of theQuick sort algorithm, with1 notation per line:

  • in the best case
  • in the average case
  • in the worst case
alex@/tmp/sort$ cat 107-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_hoare(array, n);    printf("\n");    print_array(array, n);    return (0);}alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic  -std=gnu89 107-main.c 107-quick_sort_hoare.c print_array.c -o quickalex@/tmp/sort$ ./quick19, 48, 99, 71, 13, 52, 96, 73, 86, 77, 48, 99, 71, 13, 52, 96, 73, 86, 197, 19, 99, 71, 13, 52, 96, 73, 86, 487, 19, 13, 71, 99, 52, 96, 73, 86, 487, 13, 19, 71, 99, 52, 96, 73, 86, 487, 13, 19, 48, 99, 52, 96, 73, 86, 717, 13, 19, 48, 71, 52, 96, 73, 86, 997, 13, 19, 48, 52, 71, 96, 73, 86, 997, 13, 19, 48, 52, 71, 86, 73, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 997, 13, 19, 48, 52, 71, 73, 86, 96, 99alex@/tmp/sort$

Another example of output:

alex@/tmp/sort$ ./quick_287, 65, 28, 63, 93, 52, 39, 59, 27, 30, 24, 83, 69, 62, 13, 6, 88, 58, 92, 26, 42, 11, 16, 21, 75, 36, 71, 8, 45, 3838, 65, 28, 63, 93, 52, 39, 59, 27, 30, 24, 83, 69, 62, 13, 6, 88, 58, 92, 26, 42, 11, 16, 21, 75, 36, 71, 8, 45, 8738, 8, 28, 63, 93, 52, 39, 59, 27, 30, 24, 83, 69, 62, 13, 6, 88, 58, 92, 26, 42, 11, 16, 21, 75, 36, 71, 65, 45, 8738, 8, 28, 36, 93, 52, 39, 59, 27, 30, 24, 83, 69, 62, 13, 6, 88, 58, 92, 26, 42, 11, 16, 21, 75, 63, 71, 65, 45, 8738, 8, 28, 36, 21, 52, 39, 59, 27, 30, 24, 83, 69, 62, 13, 6, 88, 58, 92, 26, 42, 11, 16, 93, 75, 63, 71, 65, 45, 8738, 8, 28, 36, 21, 16, 39, 59, 27, 30, 24, 83, 69, 62, 13, 6, 88, 58, 92, 26, 42, 11, 52, 93, 75, 63, 71, 65, 45, 8738, 8, 28, 36, 21, 16, 11, 59, 27, 30, 24, 83, 69, 62, 13, 6, 88, 58, 92, 26, 42, 39, 52, 93, 75, 63, 71, 65, 45, 8738, 8, 28, 36, 21, 16, 11, 26, 27, 30, 24, 83, 69, 62, 13, 6, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 8738, 8, 28, 36, 21, 16, 11, 26, 27, 30, 24, 6, 69, 62, 13, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 8738, 8, 28, 36, 21, 16, 11, 26, 27, 30, 24, 6, 13, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 8713, 8, 28, 36, 21, 16, 11, 26, 27, 30, 24, 6, 38, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 8713, 8, 6, 36, 21, 16, 11, 26, 27, 30, 24, 28, 38, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 8713, 8, 6, 11, 21, 16, 36, 26, 27, 30, 24, 28, 38, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 8711, 8, 6, 13, 21, 16, 36, 26, 27, 30, 24, 28, 38, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 876, 8, 11, 13, 21, 16, 36, 26, 27, 30, 24, 28, 38, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 876, 8, 11, 13, 21, 16, 28, 26, 27, 30, 24, 36, 38, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 876, 8, 11, 13, 21, 16, 28, 26, 27, 24, 30, 36, 38, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 876, 8, 11, 13, 21, 16, 24, 26, 27, 28, 30, 36, 38, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 876, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 62, 69, 83, 88, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 876, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 62, 69, 83, 87, 58, 92, 59, 42, 39, 52, 93, 75, 63, 71, 65, 45, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 62, 69, 83, 87, 58, 45, 59, 42, 39, 52, 93, 75, 63, 71, 65, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 62, 69, 83, 87, 58, 45, 59, 42, 39, 52, 65, 75, 63, 71, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 62, 69, 71, 87, 58, 45, 59, 42, 39, 52, 65, 75, 63, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 62, 69, 71, 63, 58, 45, 59, 42, 39, 52, 65, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 62, 65, 71, 63, 58, 45, 59, 42, 39, 52, 69, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 62, 65, 52, 63, 58, 45, 59, 42, 39, 71, 69, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 65, 52, 63, 58, 45, 59, 42, 62, 71, 69, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 62, 52, 63, 58, 45, 59, 42, 65, 71, 69, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 62, 52, 42, 58, 45, 59, 63, 65, 71, 69, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 59, 52, 42, 58, 45, 62, 63, 65, 71, 69, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 45, 52, 42, 58, 59, 62, 63, 65, 71, 69, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 45, 42, 52, 58, 59, 62, 63, 65, 71, 69, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 42, 45, 52, 58, 59, 62, 63, 65, 71, 69, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 42, 45, 52, 58, 59, 62, 63, 65, 69, 71, 75, 87, 83, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 42, 45, 52, 58, 59, 62, 63, 65, 69, 71, 75, 83, 87, 93, 92, 886, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 42, 45, 52, 58, 59, 62, 63, 65, 69, 71, 75, 83, 87, 88, 92, 936, 8, 11, 13, 16, 21, 24, 26, 27, 28, 30, 36, 38, 39, 42, 45, 52, 58, 59, 62, 63, 65, 69, 71, 75, 83, 87, 88, 92, 93alex@/tmp/sort$

12. Dealerdeck.h

Write a function that sorts a deck of cards.

  • Prototype:void sort_deck(deck_node_t **deck);
  • You are allowed to use the C standard library functionqsort
  • Please use the following data structures:
typedef enum kind_e{    SPADE = 0,    HEART,    CLUB,    DIAMOND} kind_t;/** * struct card_s - Playing card * * @value: Value of the card * From "Ace" to "King" * @kind: Kind of the card */typedef struct card_s{    const char *value;    const kind_t kind;} card_t;/** * struct deck_node_s - Deck of card * * @card: Pointer to the card of the node * @prev: Pointer to the previous node of the list * @next: Pointer to the next node of the list */typedef struct deck_node_s{    const card_t *card;    struct deck_node_s *prev;    struct deck_node_s *next;} deck_node_t;
  • You have to push youdeck.h header file, containing the previous data structures definition
  • Each node of the doubly linked list contains a card that you cannot modify. You have to swap the nodes.
  • You can assume there is exactly52 elements in the doubly linked list.
  • You are free to use the sorting algorithm of your choice
  • The deck must be ordered:
    • FromAce toKing
    • FromSpades toDiamonds
    • See example below
alex@/tmp/sort$ cat 1000-main.c#include <stdlib.h>#include <stdio.h>#include "deck.h"void print_deck(const deck_node_t *deck){    size_t i;    char kinds[4] = {'S', 'H', 'C', 'D'};    i = 0;    while (deck)    {        if (i)            printf(", ");        printf("{%s, %c}", deck->card->value, kinds[deck->card->kind]);        if (i == 12)            printf("\n");        i = (i + 1) % 13;        deck = deck->next;    }}deck_node_t *init_deck(const card_t cards[52]){    deck_node_t *deck;    deck_node_t *node;    size_t i;    i = 52;    deck = NULL;    while (i--)    {        node = malloc(sizeof(*node));        if (!node)            return (NULL);        node->card = &cards[i];        node->next = deck;        node->prev = NULL;        if (deck)            deck->prev = node;        deck = node;    }    return (deck);}int main(void){    card_t cards[52] = {        {"Jack", CLUB}, {"4", HEART}, {"3", HEART}, {"3", DIAMOND}, {"Queen", HEART}, {"5", HEART}, {"5", SPADE}, {"10", HEART}, {"6", HEART}, {"5", DIAMOND}, {"6", SPADE}, {"9", HEART}, {"7", DIAMOND}, {"Jack", SPADE}, {"Ace", DIAMOND}, {"9", CLUB}, {"Jack", DIAMOND}, {"7", SPADE}, {"King", DIAMOND}, {"10", CLUB}, {"King", SPADE}, {"8", CLUB}, {"9", SPADE}, {"6", CLUB}, {"Ace", CLUB}, {"3", SPADE}, {"8", SPADE}, {"9", DIAMOND}, {"2", HEART}, {"4", DIAMOND}, {"6", DIAMOND}, {"3", CLUB}, {"Queen", CLUB}, {"10", SPADE}, {"8", DIAMOND}, {"8", HEART}, {"Ace", SPADE}, {"Jack", HEART}, {"2", CLUB}, {"4", SPADE}, {"2", SPADE}, {"2", DIAMOND}, {"King", CLUB}, {"Queen", SPADE}, {"Queen", DIAMOND}, {"7", CLUB}, {"7", HEART}, {"5", CLUB}, {"10", DIAMOND}, {"4", CLUB}, {"King", HEART}, {"Ace", HEART},    };    deck_node_t *deck;    deck = init_deck(cards);    print_deck(deck);    printf("\n");    sort_deck(&deck);    printf("\n");    print_deck(deck);    return (0);}alex@/tmp/sort$ gcc -Wall -Wextra -Werror -pedantic  -std=gnu89 1000-main.c 1000-sort_deck.c -o deckalex@/tmp/sort$ ./deck{Jack, C}, {4, H}, {3, H}, {3, D}, {Queen, H}, {5, H}, {5, S}, {10, H}, {6, H}, {5, D}, {6, S}, {9, H}, {7, D}{Jack, S}, {Ace, D}, {9, C}, {Jack, D}, {7, S}, {King, D}, {10, C}, {King, S}, {8, C}, {9, S}, {6, C}, {Ace, C}, {3, S}{8, S}, {9, D}, {2, H}, {4, D}, {6, D}, {3, C}, {Queen, C}, {10, S}, {8, D}, {8, H}, {Ace, S}, {Jack, H}, {2, C}{4, S}, {2, S}, {2, D}, {King, C}, {Queen, S}, {Queen, D}, {7, C}, {7, H}, {5, C}, {10, D}, {4, C}, {King, H}, {Ace, H}{Ace, S}, {2, S}, {3, S}, {4, S}, {5, S}, {6, S}, {7, S}, {8, S}, {9, S}, {10, S}, {Jack, S}, {Queen, S}, {King, S}{Ace, H}, {2, H}, {3, H}, {4, H}, {5, H}, {6, H}, {7, H}, {8, H}, {9, H}, {10, H}, {Jack, H}, {Queen, H}, {King, H}{Ace, C}, {2, C}, {3, C}, {4, C}, {5, C}, {6, C}, {7, C}, {8, C}, {9, C}, {10, C}, {Jack, C}, {Queen, C}, {King, C}{Ace, D}, {2, D}, {3, D}, {4, D}, {5, D}, {6, D}, {7, D}, {8, D}, {9, D}, {10, D}, {Jack, D}, {Queen, D}, {King, D}alex@/tmp/sort$
[8]ページ先頭
©2009-2025 Movatter.jp