Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Sorting Integers -- Quick Sort and Heap Sort

Posted on 1997-09-22
10
Medium Priority
?
408 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?
0
Comment
Question by:jbuck092297
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 2
  • 2
  • +2
10 Comments
 

Expert Comment

by:Paul Sinnema
ID: 1255036
If You want, I can send you my solution of a Quick Sort combined with a Straight Sort.
0
 
LVL 10

Expert Comment

by:RONSLOW
ID: 1255037
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
 

Author Comment

by:jbuck092297
ID: 1255038
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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 10

Expert Comment

by:RONSLOW
ID: 1255039
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
 
LVL 2

Expert Comment

by:alexxx
ID: 1255040
//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
 
LVL 2

Expert Comment

by:alexxx
ID: 1255041
//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
 

Author Comment

by:jbuck092297
ID: 1255042
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
 
LVL 1

Expert Comment

by:twh270
ID: 1255043
Compile it as C++, not C.

0
 
LVL 2

Expert Comment

by:alexxx
ID: 1255044
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
 
LVL 2

Accepted Solution

by:
alexxx earned 100 total points
ID: 1255045
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

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

688 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question