/* compile with `clang -std=c99 -Wall -o sort sort.c` *//* compile with `clang -std=c99 -Wall -o sort sort.c` */Include C-libraries for input/output, allocation of memory, and string manipulation.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>Implement a sorting algorithm of your liking (do not use some already implemented sorting algorithm from some library) to sort words alphabetically (case-insensitive), then print all words sorted alphabetically.
Read an arbitrary number of words (use scanf). Each word will consist of at
most 63 characters and consists of upper-case and lower-case letters (A-Z and
a-z, no other special characters). The list of words is always terminated by
a “.” (which is not a valid word and thus should not be stored).
After “.” was entered, print all words that were entered in alphabetical order. For this, it should not matter whether the word starts with an upper case or lower case letter.
The word must be printed in the same way it was entered. In particular it is not allowed to convert upper-case letters to lower case letters. If the same word was entered twice, it should also be printed twice.
You can use bubble sort to sort the elements or you can read up on other sorting algorithms for practice. In particular, selection sort is easy to implement. Quicksort is more complex but it is one of the fastest sorting algorithms.
Make sure that you use a stable sorting algorithm (which means that elements that are equal do not change the position relative to each other. Selection Sort and Bubble Sort are stable).
We first declare functions for splitting up the problem into smaller parts.
/* */Compare two strings, not regarding upper- or lower-case characters.
int stricmp(const char *a, const char *b);Read all words into a table of strings. table is an out-parameter, which
means the function will change it: it is the address of the variable
which contains the table of words.
int read_words(char ***table);Free the dynamic memory of the table of words.
void free_words(char ***table, int words);Bubble sort the table.
void bubble_sort(char **table, int words);Stable version of quicksort.
void quicksort_stable(char **table, int words);In-place version of quicksort.
void quicksort_inplace(char **table, int from, int to);int main(int argc, char **argv) {Initialize the table of strings and read all the words into it.
char **table;
int words = read_words(&table);Switch the sort algorithm with a command-line argument. This is completely unnecessary for this homework exercise.
sort -b will use bubble sort,sort -i will use the in-place quicksort, if (argc > 1 && strcmp(argv[1], "-b") == 0) {
bubble_sort(table, words);
} else if (argc > 1 && strcmp(argv[1], "-i") == 0) {
quicksort_inplace(table, 0, words - 1);
} else {
quicksort_stable(table, words);
}Print out the sorted table of words.
for (int i = 0; i < words; i++) {
printf("%s\n", table[i]);
}Free the dynamic memory.
free_words(&table, words);
return 0;
}Swap two entries in the word list.
void swap(char **table, int a, int b) {
char *tmp = table[a];
table[a] = table[b];
table[b] = tmp;
}Bubble goes from left to right and compares each entry with the one following it, then swaps them if they are in the wrong order. This way, the elements “bubble up” to their correct position.
void bubble_sort(char **table, int words) {N - 1 times we need to bubble up, as for N elements, we can do
N - 1 pair-wise comparisons.
for (int i = 0; i < words - 1; i++) {In each iteration, we have i correctly bubbled elements,
so we only have to sort through 0 to index N - i, which again,
means N - i - 1 pair-wise comparisons.
for (int j = 0; j < words - i - 1; j++) {Swap if the next element is larger.
int cmp = stricmp(table[j], table[j + 1]);
if (cmp > 0) {
swap(table, j, j + 1);
}
}
}
}Stable sort a list of words with quicksort. Stable means that two values considered equal end up in the same order as in the original array.
void quicksort_stable(char **table, int words) {This quicksort uses 2N*log(N) extra space, similar to merge sort.
The basic idea is to choose a pivot element, then partition all items into things smaller or larger than this pivot, then recursively sort these shorter lists, and finally stitch together the result with concat [smaller] [pivot] [larger]. This is a classic divide and conquer algorithm.
/* */Nothing to sort if list has less than 2 elements.
if (words < 2) {
return;
}N=2, check if swap is needed.
if (words == 2) {
int cmp = stricmp(table[0], table[1]);
if (cmp > 0) {
swap(table, 0, 1);
}
return;
}To make quicksort stable, sort everything < into before, everything > into after, and == elements into before, if they come before the pivot, after if they come after. Choosing the last element as pivot makes this a bit easier, because there are no elements that come after the pivot then.
char *pivot = table[words - 1];before and after can be maximally words - 1 values.
We know our N is small so we do not mind that these temporary
arrays of strings are allocated on the local stack.
char *before[words - 1];
int beforeWords = 0;
char *after[words - 1];
int afterWords = 0;For each word in the table (before the pivot), compare it to the pivot.
for (int i = 0; i < words - 1; i++) {
int cmp = stricmp(table[i], pivot);If smaller or equal, sort it into the before list.
if (cmp <= 0) {
before[beforeWords] = table[i];
beforeWords += 1;
} else {Else sort it into the after list.
after[afterWords] = table[i];
afterWords += 1;
}
}Sort the sub-lists.
quicksort_stable((char **) &before, beforeWords);
quicksort_stable((char **) &after, afterWords);Now reassign the sorted elements into the original table
for (int i = 0; i < beforeWords; i++) {
table[i] = before[i];
}
table[beforeWords] = pivot;
for (int i = 0; i < afterWords; i++) {
table[beforeWords + 1 + i] = after[i];
}
}Quicksort but without using additional space for partial arrays.
void quicksort_inplace(char **table, int from, int to) {In-place quicksort swaps elements as many times as necessary to
achieve [ <= ] p [ >= ] in the original array.
Unfortunately, in-place quicksort is not stable.
/* */If there are <= 1 elements, no sorting is needed.
if (to - from < 1) {
return;
}Exactly two, then check if swap is needed.
if (to - from == 1) {
int cmp = stricmp(table[from], table[to]);
if (cmp > 0) {
swap(table, from, to);
}
return;
}First we pick a pivot element, choosing the last one.
int pivot = to;Then we partition the array in-place by keeping track of two pointers, left and right, which start out at the ends of the range we want to partition.
int left = from;
int right = pivot - 1;Then we let both pointers move towards each other until they meet and the whole array has been checked.
while (right >= left) {Each iteration we compare the right-most element of the unconsidered range with the pivot, and either swap it with the pivot or to the start of the unconsidered range.
int cmp = stricmp(table[right], table[pivot]);Swap < to the start of the range.
if (cmp < 0) {
if (left != right) {
swap(table, left, right);
}
left += 1;
continue;
}Swap > to the right of the pivot.
if (cmp > 0) {
swap(table, right, pivot);
pivot = right;
right = pivot - 1;
}If equal, only reduce unconsidered range.
if (cmp == 0) {
right -= 1;
}
}In the end we get an array where everything that is < p is left of the pivot, and everything > p is to the right of the pivot. The equal elements will be either left or right from the pivot, depending on the order of swaps. This is unstable sorting.
The stability could be restored here by determining the range of equal elements around pivot, then sorting them by a different criterion, say memory address or some property that relates to the original positions.
quicksort_inplace(table, from, pivot - 1);
quicksort_inplace(table, pivot + 1, to);
}Read in words from stdin until we see a ..
int read_words(char ***table) {
int size = 16;
int words = 0;
char *buffer = calloc(64, sizeof(char));
*table = calloc(size, sizeof(char *));
do {Read in a word
scanf("%s", buffer);End if it is “.”
if (strcmp(".", buffer) == 0) {
break;
}If adding it would overflow, reallocate bigger table.
if (words == size) {
size *= 2;
*table = realloc(*table, size * sizeof(char*));
}
(*table)[words] = strdup(buffer);
words += 1;
} while(1);Free the dynamic buffer.
free(buffer);
return words;
}Free the dynamic memory allocated by read_words.
void free_words(char ***table, int words) {Free all individual words.
for (int i = 0; i < words; i++) {
free((*table)[i]);
(*table)[i] = NULL;
}Free the table itself.
free(*table);
*table = NULL;
}Case-insensitive string compare.
int stricmp(const char *a, const char *b) {
int i = 0;Loop through words until null-termination is reached, so only as long as the shorter string.
while (a[i] != '\0' || b[i] != '\0') {
char A = a[i];lowercase A
if ((A >= 'A' && A <= 'Z')) {
A += 32;
}
char B = b[i];lowercase B
if ((B >= 'A' && B <= 'Z')) {
B += 32;
}
if (A == B) {
i += 1;
continue;
}
if (A < B) {
return -1;
}
return 1;
}
return 0;
}