diff options
| -rw-r--r-- | src/03/04/README.md | 52 | ||||
| -rw-r--r-- | src/03/sort.c | 8 |
2 files changed, 58 insertions, 2 deletions
diff --git a/src/03/04/README.md b/src/03/04/README.md index 0a95052..fb94660 100644 --- a/src/03/04/README.md +++ b/src/03/04/README.md @@ -3,6 +3,54 @@ following algorithms, and illustrate the details of the execution of the algorithms: a. merge-sort algorithm. + +```plaintext +[3,1,4,1,5,9,2,6,5,3,5,] +[3,1,4,1,5,9,] +[3,1,4,] +[3,1,] +[3,] +[3,1,] +[1,3,4,] +[1,3,4,1,5,9,] +[1,3,4,1,5,] +[1,3,4,1,] +[1,3,4,1,5,] +[1,3,4,1,5,9,] +[1,1,3,4,5,9,2,6,5,3,5,] +[1,1,3,4,5,9,2,6,5,] +[1,1,3,4,5,9,2,6,] +[1,1,3,4,5,9,2,] +[1,1,3,4,5,9,2,6,] +[1,1,3,4,5,9,2,6,5,] +[1,1,3,4,5,9,2,5,6,3,5,] +[1,1,3,4,5,9,2,5,6,3,] +[1,1,3,4,5,9,2,5,6,3,5,] +``` + b. quick-sort algorithm. - * Choose a partitioning strategy you like to pick a pivot element from the sequence. - * Analyze how different portioning strategies may impact on the performance of the sorting algorithm. +* Choose a partitioning strategy you like to pick a pivot element from the sequence. +* Analyze how different portioning strategies may impact on the performance of the sorting algorithm. + +For choosing a pivot I chose to use the value in the last element of the sequence. +Alternative, strategies include choosing a random pivot in each sub-sequence. + +Using the last item in the sub-sequence as the pivot: + +```plaintext +[3,1,4,1,5,9,2,6,5,3,] +[3,1,4,1,2,] +[1,1,] +[1,] +[] +[1,] +[1,1,] +[1,1,2,3,4,] +[1,1,2,] +[1,1,2,3,3,] +[1,1,2,3,3,4,5,6,5,9,] +[1,1,2,3,3,4,] +[1,1,2,3,3,4,5,5,5,9,] +[1,1,2,3,3,4,5,5,] +[1,1,2,3,3,4,5,5,5,6,] +``` diff --git a/src/03/sort.c b/src/03/sort.c index d67bfff..d46a8d6 100644 --- a/src/03/sort.c +++ b/src/03/sort.c @@ -1,6 +1,14 @@ #include <stdio.h> #include <stdlib.h> +static void dump(int *items, int n) +{ + printf("["); + for (int i = 0; i < n; ++i) + printf("%d,", items[i]); + printf("]\n"); +} + static void _merge(int *items, int min, int mid, int max) { int length = (max-min) + 1; int tmp[length]; |
