A few sorting algorithms implemented in C

Question

I was reading about the elementary sorting algorithms like insertion Sort, selection sort and bubble Sort in Introduction to Algorithms by Cormen and I decided to try and implement it in C.

#include<stdio.h>
#define MAXSIZE 100  //  Maximum number of elements permissible in array

void swap(int*,int*);
void print(int*,int);

int main(void) {
    int arr[MAXSIZE],n,i,j,ch,ord;
    void insertion(int*,int,int),selection(int*,int,int),bubble(int*,int,int);
    printf("\nEnter number of elements for array = ");
    scanf("%d",&n);
    printf("\n\nEnter the array elements one by one : \n\n");
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    printf("\n\nWhat sorting you want to use ?\n\n Insertion (1) , Selection (2) or Bubble (3)\n\nEnter choice = ");
    scanf("%d",&ch);
    printf("\n\nSorting order ? \n\n Ascending (1) or Descending (2)\n\nEnter choice = ");
    scanf("%d",&ord);
    printf("\n\n");
    switch(ch){
        case 1:
            insertion(arr,n,ord);
            break;
        case 2:
            selection(arr,n,ord);
            break;
        case 3:
            bubble(arr,n,ord);
    }
    print(arr,n);
printf("\n\n");
return 0;
}

void swap(int *x,int *y){
    int t=*x;
    *x=*y;
    *y=t;
}

void insertion(int *a,int l,int ord){
    int i,j;
    for(i=1;i<l;i++){
        for(j=i;j>0;j--){
            if((ord==1 && a[j]<a[j-1]) || (ord==2 && a[j]>a[j-1]))
                swap(&a[j],&a[j-1]);
            else
                break;
        }
    }
}

void selection(int *a,int l,int ord){
    int index,i,j;
    for(i=0;i<l;i++){
        index=i;
        for(j=i;j<l;j++){
            if((ord==1 && a[j]<a[index]) || (ord==2 && a[j]>a[index]))
                index=j;
        }
    swap(&a[i],&a[index]);
    }       
}

void bubble(int *a,int l,int ord){
    int i,j;
    for(i=l;i>0;i--){
        for(j=0;j<i-1;j++){
            if((ord==1 && a[j]>a[j+1]) || (ord==2 && a[j]<a[j+1]))
                swap(&a[j],&a[j+1]);
        }
    }
}

void print(int *a,int l){
    int i;
    for(i=0;i<l;i++)
        printf("%d\t",a[i]);
}

I'm looking for feedback / improvements on my code and whether the implementation of the sorting algorithms in the respective function definitions are proper or not.

Answer 1

As an additional note, your insertion function does not actually implement an insertion sort, but a gnome sort: to insert an element in the sorted part, your function repeatedly compares an element to the previous one and swaps them if they are not in the correct order, which means it's a gnome sort. An insertion sort would compare every element to the current element to insert to find the position where is should be inserted, then it would move every element after the point of insertion one step to the right and put the current element in the correct place.

Here is an actual insertion sort; the actual code comes from Rosetta Code:

void insertion_sort(int *a, int n) {
    for(size_t i = 1; i < n; ++i) {
        int tmp = a[i];
        size_t j = i;
        while(j > 0 && tmp < a[j - 1]) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = tmp;
    }
}

Answer 2

This is in addition to the other reviews.

User Provided Functions

If you're looking for the "C Way" to do things, your sorting algorithms should take a function pointer to a comparison function that defines how the user wants the items sorted. This will take a bit of boiler plate code on your part but it makes the implementation of the sorting functions themselves slightly cleaner.

// Define the function pointer to a comparison function
// Needs to include <stdbool.h>
typedef bool (*comparer)(const void *a, const void *b);

// Now define your own function to use as a comparison
// In your case, you're using integers so this would be the definition for ascending sort
bool ascending_int_sort(const void *a, const void *b)
{
     return (*(int *)a) > (*(int *)b);
}

// Descending sort implementation
bool descending_int_sort(const void *a, const void *b)
{
     return (*(int *)a) < (*(int *)b);
}

// ...

// You can then implement your sorts like this:
// Notice the more descriptive variable/function names:)
void bubble_sort(int *arr, int length, comparer comp)
{
    for (int i = 0; i < length; ++i) {
        for (int j = i + 1; j < length - 1; ++j) {
             if (comp(&arr[i], &arr[j])) {
                  swap(&arr[i], &arr[j]);
             }
        }
    }
}

// Then the user can call your function like this for ascending sort
bubble_sort(array, length, ascending_int_sort);

The rest of your functions can follow this pattern.

Answer 3

This is a pretty good straightforward implementation of these algorithms. It's really nice that they're all implemented in-place so no extra memory is needed. It looks pretty good, but I have a few suggestions.

Better Naming

Your function names are pretty good. (I might add "sort" to the various sorting routine names, but it's not a big deal.) However, the variable names are a bit too terse. Normally, I'd object to using arr as the name for an array and name it after what's stored in the array. (Something like grades or names or whatever was being sorted.) In this example case, it's acceptable, but keep that in mind for the future.

It's tradition for i and j to be used for loop control variables, and I don't mind those. But I would change n to numElements. (Or if you have a better name for the array, name it num<whatever's in the array> such as numGrades, numNames, etc.)

The function parameters a and l should be named with more readable names, like arr and length. ord is reasonable, but I'd prefer order.

Use enum when appropriate

ch is presumably supposed to hold a character, which would be a reasonable name, except that it holds an int. Likewise, ord is supposed to hold the order.

Both of those should be an enumerated type. I'd make one for the sort type and one for the sort order. Something like this:

typedef enum {
    SO_Ascending = 1,
    SO_Descending
} SortOrder;

typedef enum {
    ST_Insertion = 1,
    ST_Selection,
    ST_Bubble
} SortType;

You can then create variables of those types and read the values into them.

Error handling

You may have noticed that the user can enter invalid values, too. You should verify that the values they entered are reasonable and prompt them again if not. To do that, it would probably make sense to break out some of the functionality in main() into separate functions. I suggest something like this:

void promptForArray(int arr [ MAXSIZE ], int* numElements)
{
    do {
        printf("\nEnter number of elements for array = ");
        scanf("%d", numElements);
        if ((*numElements <= 0) || (*numElements > MAXSIZE))
        {
            printf("\nYou entered an invalid value for the number of elements. Please choose a value between 1 and %d\n", MAXSIZE);
        }
    } while ((*numElements <= 0) || (*numElements > MAXSIZE));

    printf("\n\nEnter the array elements one by one : \n\n");
    for(int i = 0; i < *numElements; i++){
        scanf("%d",&arr [ i ]);
    }
}

You could then do a similar thing for getting the sort function and sort order. Something like this:

void promptForSortType(SortType* sortType)
{
    do {
        printf("\n\nWhat sorting you want to use ?\n\n Insertion (1) , Selection (2) or Bubble (3)\n\nEnter choice = ");
        scanf("%d", sortType);
        if ((*sortType < ST_Insertion) || (*sortType > ST_Bubble))
        {
            printf("\nYou entered an invalid sort type. Please enter a value between 1 and 3.\n");
        }
    } while ((*sortType < ST_Insertion) || (*sortType > ST_Bubble));
}

Readability

Do the above things should improve the readability of your code, but you can do more. I recommend leaving spaces around operators (+, -, =, etc.).

This method of introducing function prototypes within main() is very odd:

void insertion(int*,int,int),selection(int*,int,int),bubble(int*,int,int);

Instead, you should put them above main and put them all on separate lines, and you should name the parameters so someone reading them knows what the parameters mean. Something like this:

void insertion(int *arr, const int length, const SortOrder ord);
void selection(int *arr, const int length, const SortOrder ord);
void bubble(int *arr, const int length, const SortOrder ord);

Use const where appropriate

You may have noticed that I made length and ord const in the above examples. They don't change, so it's best to mark them as unchanging. Then the reader and the compiler know more about the intent of the function. You could also make arr const in the print() function.

Answer 4

Use size_t for length parameters

When counting items or storing an amount of memory (i.e. cannot be less than zero), use size_t. It is unsigned and is guaranteed to hold any array index. int is limited to 2³¹-1 = ~2 billion. General sorting code should be able to handle arrays that can fill a machine's RAM. The largest Amazon instance has 244GB of RAM, which is ~30 billion 64 bit longs.

Implement a generic sort

If you are implementing sorting algorithms you should not need to know about the data types or how to compare them. The algorithm is the same if you are sorting char, int, long or any other type of array. In C this is achieved by passing in: the array as a void pointer (void*), the number of elements, the size of the elements, and a function to do the comparisons.

Comparison functions traditionally take two arguments (a,b) and return an int which is <0 if a<b, 0 if a==b and >0 if a>b. Ideally the comparison function should take a third void* pointer in order to pass any parameters required for the comparison (e.g. string encoding) or local memory required to facilitate the comparison (e.g. to avoid malloc'ing for each comparison).

Such comparison functions can be written for int like so:

// Return the comparison of 'int's pointed to by _a and _b
// <0 iff a<b, 0 iff a==b, >0 iff a>b
int cmp_ints(const void *_a, const void *_b, void *args)
{
  (void)args; // this comparison does not need extra parameters
  int a = *(const int *)_a, b = *(const int*)_b;
  return (a > b) - (b > a);
}

// Return the reverse comparison of 'int's pointed to by _a and _b
// >0 iff a<b, 0 iff a==b, <0 iff a>b
int cmp_ints_rev(const void *_a, const void *_b, void *args)
{
  (void)args; // this comparison does not need extra parameters
  int a = *(const int *)_a, b = *(const int*)_b;
  return (b > a) - (a > b);
}

A generic bubble sort can then be implemented using a void pointer, size of the elements and the comparison function:

// swap `n` bytes of non-overlapping memory pointed to by `a` and `b`
void swapm(char *a, char *b, size_t n) {
  char *end, tmp;
  for(end = a+n; a<end; a++, b++) { tmp = *a; *a = *b; *b = tmp; }
}

void bubble_sort(void *arr, size_t nel, size_t es,
                 int (compar)(const void *, const void *, void *_arg),
                 void *args)
{
  size_t i,j;
  char *ptr = arr; // need to cast void*->char* to do pointer arithmetic
  for(i=nel; i>0; i--) {
    for(j=0; j+1<i; j++) { // cannot do j<i-1 since i is unsigned and might be zero!
      if(compar(ptr+es*j, ptr+es*(j+1), args) > 0) {
        swapm(ptr+es*j, ptr+es*(j+1), es);
      }
    }
  }
}

Example using bubble_sort() to sort integers:

void foo() {
  int smallnums[] = {1,2,3,4};
  // Sort ascending
  bubble_sort(smallnums, 4, sizeof(smallnums[0]), cmp_ints, NULL);
  // Sort descending
  bubble_sort(smallnums, 4, sizeof(smallnums[0]), cmp_ints_rev, NULL);
}

Once you've implemented a sort function in this way, it can be used to sort any data type for which a comparison function can be written.

Edit: Need to cast void* to char* in bubble_sort() to do pointer de-referencing and arithmetic

Answer 5

I can suggest this website. It follow the K&R coding style which is the most accepted. Apart from that some commenting is always good even though here everything is pretty obvious. Lastly, I will suggest to better the error handling as previously pointed.

Coding Style Link

Since you are learning algorithms, a better way to see the effectiveness of the code will be to test them with large input and time their performance.

I remember once having the user enter the array size as an argument and then randomly generating a huge array. Then you can have a script to run and time your program several times with different algorithms to an output file and check the results. This will help you get a practical understanding of the algorithms and their complexity value.

It becomes satisfying when you modify an algorithm for it to achieve better results. Especially when you have an actual data to prove it to yourself rather than just having the complexity value.