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

jbuck092297
jbuck092297 asked
on
Medium Priority
470 Views
Last Modified: 2006-11-17
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

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 !!! :-)

Author

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 __advance(x)          ((x)++)
   #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()

Author

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.

Ask the Experts
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

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

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.