Solved

Sorting Integers -- Quick Sort and Heap Sort

Posted on 1997-09-22
10
397 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
  • 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
 
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
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 
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 50 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

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
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 and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

762 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

Need Help in Real-Time?

Connect with top rated Experts

24 Experts available now in Live!

Get 1:1 Help Now