• C

Sorting Integers -- Quick Sort and Heap Sort

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?
jbuck092297Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Paul SinnemaCommented:
If You want, I can send you my solution of a Quick Sort combined with a Straight Sort.
0
RONSLOWCommented:
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 !!! :-)

0
jbuck092297Author 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.
0
Top Threats of Q1 & How to Defend Against Them

WEBINAR: Join WatchGuard CTO and our Threat Research Team on Aug. 2nd to hear the findings from our Q1 Internet Security Report! Learn more about the top threats detected in the first quarter and how you can defend your business against them!

RONSLOWCommented:
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

0
alexxxCommented:
//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()

0
alexxxCommented:
//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()

0
jbuck092297Author 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
0
twh270Commented:
Compile it as C++, not C.

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

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.