We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you a podcast all about Citrix Workspace, moving to the cloud, and analytics & intelligence. Episode 2 coming soon!Listen Now

x

Sorting Integers -- Quick Sort and Heap Sort

on
Medium Priority
470 Views
Can anyone help me with an alogrithm that will produce a random set of numbers and then sort them in ascending and descending order with a Quick Sort and a Heap Sort?
Comment
Watch Question

View Solution Only

Commented:
If You want, I can send you my solution of a Quick Sort combined with a Straight Sort.

Commented:
If you tell us what help you want, then I can help you.  If you don't say what the problem is then it is a bit hard !!! :-)

Commented:
The problem is creating a random number data set of 10000 integers, printing out the unsorted list, sorting with a Quick sort routine and a Heap sort routine in both ascending and descending order.  I've pretty much got the Quick sort and creating the random number data set today.  Still don't have a clue on the Heap sort routine.

Commented:
OK - so you're really after a HeapSort alogirthm.

BTW: you can always use the c-standard quick sort library function which does quick sort for you - but if this is a programming assignment then that won't help

I'll see what I can sind on HeapSort.

Roger

Commented:
//define __L_IS_G for descending order Heap Sort

#ifndef __L_IS_G       //ascending order
#define __less          <
#define __less_equal    <=
#else   //#ifndef __L_IS_G   descending order
#define __less          >
#define __less_equal    >=
#endif   //#else #ifndef __L_IS_G

#define __before              <
#define __before_same         <=
#define __plus                +
#define __minus               -
#define __receed(x)           ((x)--)
#define __distance(x, y)      ((y) - (x))

//adjust heap subtree (root = max)
template <class PKEY> inline
void _SiftHeap(PKEY f, PKEY l, PKEY v)
{
for(register PKEY c = f __plus ((__distance(f, v) + 1) << 1);
c __before_same l;
v = c, c = f __plus ((__distance(f, v) + 1) << 1))
{
if(c == l ||
*c __less *(c __minus 1))
__receed(c);

if(*v __less *c)
_Swap(v, c);
else
break;
}
}  //_SiftHeap()

//make heap (root = max)
template <class PKEY> INLINE
void _MakeHeap(PKEY f, PKEY l)
{
for(register PKEY p = f __plus ((__distance(f, l) - 1) >> 1); f __before_same p; __receed(p))
_SiftHeap(f, l, p);
}  //_MakeHeap

//heap sort (ascending order), O(n*ln(n))
template <class PKEY> INLINE
void _SortHeap(PKEY f, PKEY l)
{
for(_MakeHeap(f, __receed(l)); f __before l; __receed(l))
{
_Swap(f, l);
_SiftHeap(f, l, f);
}
}      //_SortHeap()

Commented:
//sorry, forgot 2 functions:

template <class KEY, class PKEY> inline
void __Swap(PKEY x, PKEY y, KEY*)
{
register KEY tmp = *x;
*x = *y;
*y = tmp;
}  //__Swap()

template <class PKEY> inline
void _Swap(PKEY x, PKEY y)
{
__Swap(x, y, (PKEY)0);
}  //_Swap()

Commented:
Alexxx,

The code does not compile with my Borland 4.52 compiler.  Keep getting an error at line 23 (template <class PKEY> inline) stating a declaration error.

Don't know if there are more because I can't fix that oneand compile stops there.

Also, I, being inexperienced and learning, have a difficult figuring out what is going on with every variable as they are cryptically named.

Joe

Commented:
Compile it as C++, not C.

Commented:
if you want c-version remove the lines starting from the word 'template' and add two typedef's:
typedef int* PKEY
typedef int KEY
Commented:
if you want c-version remove the lines starting from the word 'template' and add two typedef's:
typedef int* PKEY
typedef int KEY

Not the solution you were looking for? Getting a personalized solution is easy.

Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile