# Finding the order of sorting of an array

I am finding the order of sorting of an array. The code works but can it be made better especially the return values of the function findSortOrder.

#include <stdio.h>
#include <stdlib.h>

// Returns 0 for unsorted, 1 for sorted in increasing order, 2 for sorted in decreasing order
int findSortOrder(int array[], int len)
{
// holds the sorting order of the subarray array[0...i]
// 0 represents no information about sorting order
// 1 represents sorting in increasing order
// 2 represents sorting in decreasing order
int order = 0;
int i;
for (i = 1; i < len; i++)
{
if (order == 0)
{
if (array[i] > array[i - 1])
{
order = 1;
}
else if (array[i] < array[i - 1])
{
order = 2;
}
}
else if (order == 1)
{
if (array[i] < array[i - 1])
{
return 0;
}
}
else
{
if (array[i] > array[i - 1])
{
return 0;
}
}
}
if (order == 0 || order == 1)
{
return 1;
}
else
{
return 2;
}
}

int main()
{
printf("Enter length of the array: ");
int len;
scanf("%d", &len);
int* input = malloc(len * sizeof(*input));
int i;
for (i = 0; i < len; i++)
{
scanf("%d", &input[i]);
}
int order = findSortOrder(input, len);
switch (order)
{
case 0:
printf("Unsorted\n");
break;
case 1:
printf("Sorted in increasing order\n");
break;
case 2:
printf("Sorted in decreasing order\n");
break;
}
free(input);
return 0;
}


Edit:
I will be using this function to merge two sorted arrays in their sorting order. So I think if no. of elements is 1 or all are equal then sort order could be returned as increasing.

• What should be returned if the array is one element long? – Federico Poloni Aug 20 '15 at 10:08

The cleanest would be an enum and a switch (current) with three cases:

In each case you can then check if you stay in the current_order or if you switch to another or if you can return 0/1/-1.

Simplified:

current=NONE;
for()
a=... b= ..
switch(current)
case NONE: if (a>b) current=DEC; else if (a<b) current=INC; break;
case INC:  if (a>b) return NONE; break;
case DEC:  if (a<b) return NONE; break;
return current;


I don't know if it's the right term, but I think that is a finite state machine. You could read about those to get more information; it's always good to use for parsing stuff.

What should be returned if the array is one element long?

Good point. I would introduce another return value MIXED:

current=NONE;
for()
a=... b= ..
switch(current)
case NONE: if (a>b) current=DEC; else if (a<b) current=INC; break;
case INC:  if (a>b) return MIXED; break;
case DEC:  if (a<b) return MIXED; break;
return current;


A few tips; firstly, localise loop variables. i.e. Instead of

int i;
for (i = 0; i < len; i++)
{
scanf("%d", &input[i]);
}


Use

for(int i = 0; i < len; i++)
{
scanf("%d", &input[i]);
}


This is mostly a readability thing as it makes it clear what the variable i is used for. (Make sure to enable c99 mode on your compiler though)

Secondly, don't use 'magic numbers'. This is another point for readibility, but it can make writing the program much easier, and for longer projects, it can be a huge help on debugging. Also, if you change it's value, you only need to do it once and it's changed everywhere. i.e. just after the header files add something like

#define NONE 0
#define INC 1
#define DEC 2


And then in your function, return these symbolic values instead of the actual values.

Thirdly, I'd use a set of 'if' statements instead of the switch in your main function as you only have 3 possible outcomes. For example, I'd use

if(order == 1)
printf("Sorted in increasing order\n");
else if(order == 2)
printf("Sorted in decreasing order\n");
else
printf("Unsorted\n");


Fourthly, I noticed you added a user input for the length and used this value in a malloc(). You should change len from an int to an unsigned int to prevent any attempts at allocating a negative number of bytes. You also assume that the malloc() will be successful. You should add a check for that, and some error handling for if it fails. i.e.

int* input;
if( !(input = malloc(len * sizeof(*input))) ) {  //If the malloc() fails
fprintf(stderr, "Memory allocation faliure\n");
return 1;
}


Here is a somewhat rewritten version of your code with comments explaining all the changes I made that I didn't mention above:

#include <stdio.h>
#include <stdlib.h>

#define NONE 0
#define INC 1
#define DEC -1

int find_sort_order(int array[], int len) //I renamed your function because caps in names are a bad idea (debugging issues)
{
int order = NONE;
int order_prev = NONE; //Compare this to order at the end of every increment to see if the order changed

if(array[1] > array[0]) //Determines the initial order of the array for comparison later
order_prev = order = INC;
else if(array[1] < array[0])
order_prev = order = DEC;

for(int i = 2; i < len; i++) {
if(array[i] > array[i - 1]) //Determine the current order of the array
order = INC;
else if(array[i] < array[i - 1])
order = DEC;

if(order != NONE)
if(order != order_prev && order_prev != NONE) { //If order was not NONE initially and it has changed, set order to NONE, and break out of the loop
order = NONE;
break;
}
}
return order;
}

int main()
{
unsigned int len;
int* input;

printf("Enter length of the array: ");
scanf("%d", &len);

if(len < 2) {
fprintf(stderr, "Can't have an array of of less than 2 elements!\n");
return 1;
}

if( !( input = malloc(len * sizeof(*input)) ) ) {
fprintf(stderr, "Memory allocation faliure!\n");
return 1;
}

for(int i = 0; i < len; i++)
scanf("%d", &input[i]);

int order = find_sort_order(input, len);

if(order == INC)
printf("Sorted in increasing order\n");
else if(order == DEC)
printf("Sorted in decreasing order\n");
else
printf("Unsorted\n");

free(input);
return 0;
}


NOTE: I removed as many of the braces as possible as I thought that they made the function look bloated, and my personal preference is to use indentation only for 1 liner 'if' statements, but that's entirely up to your preference.

EDIT: I noticed a couple of small bugs in my code causing odd behaviour and have fixed them

• Hope this helps, I am currently seeing if I can in anyway optimise your 'findSortOrder' function. – jess-turner Aug 20 '15 at 1:48
• Should I use an enum for the order types? – In78 Aug 20 '15 at 3:08
• No reason why not; in this case it doesn't really matter as you're dealing with only 3 values. That said, enum is type-safe whereas #define is not, but again, that isn't likely to be an issue here. – jess-turner Aug 20 '15 at 3:22