Rajeev - 6 months ago 55

C Question

`a=[1,3,6,7,1,2]`

Which is the best sorting technique to sort the following array and if there are duplicates how to handle them.

Also which is the best sorting technique of all....

`void BubbleSort(int a[], int array_size)`

{

int i, j, temp;

for (i = 0; i < (array_size - 1); ++i)

{

for (j = 0; j < array_size - 1 - i; ++j )

{

if (a[j] > a[j+1])

{

temp = a[j+1];

a[j+1] = a[j];

a[j] = temp;

}

}

}

}

Answer

In C, you can use the built in `qsort`

command:

```
int compare( const void* a, const void* b)
{
int int_a = * ( (int*) a );
int int_b = * ( (int*) b );
if ( int_a == int_b ) return 0;
else if ( int_a < int_b ) return -1;
else return 1;
}
qsort( a, 6, sizeof(int), compare )
```

see: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

To answer the second part of your question: an optimal (comparison based) sorting algorithm is one that runs with O(n log(n)) comparisons. There are several that have this property (including quick sort, merge sort, heap sort, etc.), but which one to use depends on your use case.

As a side note, you can sometime do better than O(n log(n)) if you know something about your data - see the wikipedia article on Radix Sort