As an additional note, yourinsertion function does not actually implement an insertion sort, but agnome 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 fromRosetta 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;    }}

• \$\begingroup\$Whoa! MIND=BLOWN! I actually thought swapping would be similar to what the original insertion sort does and that it would be just a different implementation of insertion sort. Never knew it had an entirely different name. Even Wikipedia says it's similar to insertion sort which explains how I thought it to be an implementation of insertion sort. Thanks for taking the time to actually read through the code and providing actual interesting feedback unlike the other answers. I'm accepting this answer and upvoting it too. Cheers! :)\$\endgroup\$

  learner

  – learner

  2016-01-24 10:00:52 +00:00

  CommentedJan 24, 2016 at 10:00
• \$\begingroup\$@learner No problem, I have been learning things about sorting algorithms these last months, so I generally know how a standard sorting algorithm should look like. I'm glad I could help :)\$\endgroup\$

  Morwenn

  – Morwenn

  2016-01-24 21:36:48 +00:00

  CommentedJan 24, 2016 at 21:36

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 sortbool ascending_int_sort(const void *a, const void *b){     return (*(int *)a) > (*(int *)b);}// Descending sort implementationbool 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 sortbubble_sort(array, length, ascending_int_sort);

The rest of your functions can follow this pattern.

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 usingarr as the name for an array and name it after what's stored in the array. (Something likegrades ornames or whatever was being sorted.) In this example case, it's acceptable, but keep that in mind for the future.

It's tradition fori andj to be used for loop control variables, and I don't mind those. But I would changen tonumElements. (Or if you have a better name for the array, name itnum<whatever's in the array> such asnumGrades,numNames, etc.)

The function parametersa andl should be named with more readable names, likearr andlength.ord is reasonable, but I'd preferorder.

Useenum when appropriate

ch is presumably supposed to hold a character, which would be a reasonable name, except that it holds anint. 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 inmain() 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 withinmain() 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);

Useconst where appropriate

You may have noticed that I madelength andordconst 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 makearr const in theprint() function.

• 1
  \$\begingroup\$Aboutconst, his arrays are changing, so thearr arguments shouldn't be marked asconst.\$\endgroup\$

  JS1

  – JS1

  2016-01-19 04:27:41 +00:00

  CommentedJan 19, 2016 at 4:27
• \$\begingroup\$Ah yes,ch was initially supposed to hold a character ('a' or 'd') but I had some input buffer problems usingscanf(), so I simply changed it toint but forgot to change the variable name.\$\endgroup\$

  learner

  – learner

  2016-01-19 07:23:20 +00:00

  CommentedJan 19, 2016 at 7:23
• \$\begingroup\$However, regarding thearr being constant, that's not the case since I'm swapping the elements of the array directly usingswap() in the sorting algorithms.\$\endgroup\$

  learner

  – learner

  2016-01-19 07:25:59 +00:00

  CommentedJan 19, 2016 at 7:25
• \$\begingroup\$D'oh! Of course. I'll fix that. Sorry for the confusion.\$\endgroup\$

  user1118321

  – user1118321

  2016-01-19 17:12:16 +00:00

  CommentedJan 19, 2016 at 17:12

Usesize_t for length parameters

When counting items or storing an amount of memory (i.e. cannot be less than zero), usesize_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 bitlongs.

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 sortingchar,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 anint which is<0 ifa<b,0 ifa==b and>0 ifa>b. Ideally the comparison function should take a thirdvoid* 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 forint 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>bint 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>bint 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 usingbubble_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 castvoid* tochar* inbubble_sort() to do pointer de-referencing and arithmetic

• 1
  \$\begingroup\$Welcome to Code Review! Good job on your first answer.\$\endgroup\$

  SirPython

  – SirPython

  2016-01-21 00:02:07 +00:00

  CommentedJan 21, 2016 at 0:02

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.

• c
• sorting