/sorting_algorithms

Alx project covers Sorting algorithms and Big O notation.

Primary LanguageC

0x1B. C - Sorting algorithms & Big O

Resources

Read or watch:

Learning Objectives

General

  • 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

Tasks

0. Bubble sort

Requirements:

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)

Mode: mandatory

File: 0-bubble_sort.c, 0-O

1. Insertion sort

Requirements:

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)

Mode: mandatory

File: 1-insertion_sort_list.c, 1-O

2. Selection sort

Requirements:

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)

Mode: mandatory

File: 2-selection_sort.c, 2-O

3. Quick sort

Requirements:

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)

Mode: mandatory

File: 3-quick_sort.c, 3-O

4. Shell sort - Knuth Sequence

  • Write a function that sorts an array of integers in ascending order using the Shell sort algorithm, using the Knuth sequence

Requirements:

Prototype: void shell_sort(int *array, size_t size); You must use the following sequence of intervals (a.k.a the Knuth sequence):

n+1 = n * 3 + 1 1, 4, 13, 40, 121, ...

n+1 = n * 3 + 1 1, 4, 13, 40, 121, ... You’re expected to print the array each time you decrease the interval (See example below).

Mode: #advanced

File: 100-shell_sort.c

5. Cocktail shaker sort

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

Requirements:

Prototype: void cocktail_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)

Mode: #advanced

File: 101-cocktail_sort_list.c, 101-O

6. Counting sort

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

Requirements:

Prototype: void counting_sort(int *array, size_t size); You can assume that array will contain only numbers >= 0 You are allowed to use malloc and free for this task You’re expected to print your counting array once it is set up (See example below)

This array is of size k + 1 where k is the largest number in array

This array is of size k + 1 where k is the largest number in array

Mode: #advanced

File: 102-counting_sort.c, 102-O

7. Merge sort

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

Requirements:

Prototype: void merge_sort(int *array, size_t size); You must implement the top-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 the left array before the right array

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 the left array before the right array You are allowed to use printf You are allowed to use malloc and free only once (only one call) Output: see example

Mode: #advanced

File: 103-merge_sort.c, 103-O

8. Heap sort

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

Requirements:

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

Mode: #advanced

File: 104-heap_sort.c, 104-O

9. Radix sort

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

Requirements:

Prototype: void radix_sort(int *array, size_t size); You must implement the LSD radix sort algorithm You can assume that array will contain only numbers >= 0 You are allowed to use malloc and free for this task You’re expected to print the array each time you increase your significant digit (See example below)

Mode: #advanced

File: 105-radix_sort.c

10. Bitonic sort

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

Requirements:

Prototype: void bitonic_sort(int *array, size_t size); You can assume that size will be equal to 2^k, where k >= 0 (when array is not NULL …) You are allowed to use printf You’re expected to print the array each time you swap two elements (See example below) Output: see example

Mode: #advanced

File: 106-bitonic_sort.c, 106-O

11. Quick Sort - Hoare Partition scheme

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

Requirements:

Prototype: void quick_sort_hoare(int *array, size_t size); You must implement the Hoare 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)

Mode: #advanced

File: 107-quick_sort_hoare.c, 107-O

12. Dealer

Requirements:

Prototype: void sort_deck(deck_node_t **deck); You are allowed to use the C standard library function qsort Please use the following data structures:

Mode: #advanced

File: 1000-sort_deck.c, deck.h