Solved

Sorting Integers -- Quick Sort and Heap Sort

Posted on 1997-09-22
10
398 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
Optimizing Cloud Backup for Low Bandwidth

With cloud storage prices going down a growing number of SMBs start to use it for backup storage. Unfortunately, business data volume rarely fits the average Internet speed. This article provides an overview of main Internet speed challenges and reveals backup best practices.

 
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

What is SQL Server and how does it work?

The purpose of this paper is to provide you background on SQL Server. It’s your self-study guide for learning fundamentals. It includes both the history of SQL and its technical basics. Concepts and definitions will form the solid foundation of your future DBA expertise.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
memory leak detection 9 70
Describe order of operation while copying text 11 115
First character of input string truncated with scanf 3 94
Finding a good hash function 4 120
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

920 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

17 Experts available now in Live!

Get 1:1 Help Now