کمک فوری : لطفا تو رو خدا کمک کنید در خواست پروژه haepsort ,radixsort

کمک فوری : لطفا تو رو خدا کمک کنید
در خواست پروژه haepsort ,radixsort میخوام چون پروژه 6 نمره داره اگه کمک کنید براتون دعا می کنم

نقل قول:

---

نوشته شده توسط mohamad sadgh [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

کمک فوری : لطفا تو رو خدا کمک کنید
در خواست پروژه haepsort ,radixsort میخوام چون پروژه 6 نمره داره اگه کمک کنید براتون دعا می کنم

---

سلام
دوست عزیز این دو تا سورتی که شما خواستی بسیار معروف هستن و در تمامه کتاب های ساختمان داده پیدا می شه و فرقی نمی کنه چه کتا بی با شه حتی توی کتاب ساختمان داده ی اقای جعفر نژاد قمی هم هستش(جلدش مشکیه یعنی قدیما که مشکی بود)

در ضمن کد heap برات می ذارم شاید به درد ت بخوره
/*
-------------------------------------------------------------------
| |
| HeapTree Class |
| ================================================== ========= |
| This HeapTree Class has been implemented with templates. |
| |
| To use the HeapSort that is built into the class, two |
| seperate steps must be taken. The first is the constructor: |
| |
| HeapTree<Type> HeapName(Array, Num, MaxNum); |
| |
| 'Type' is the data type of the Array elements, 'Array' is a |
| standard C++ array to be sorted and 'Num' is the number of |
| elements in the array. MaxNum sets the limit on the number |
| of data nodes that the Heap can have. If you are only using |
| the heap for sorting, you can set MaxNum to Num. (However, |
| MaxNum should not be set less than Num). |
| |
| When the constructor is called, the Heap *copies* the Array. |
| Thus, neither the Array variable nor what it points to will |
| be modified. |
| |
| The second step is to call the actual sort: |
| |
| NewArray *Sort(); |
| |
| This sort will return a pointer to another array, which is |
| the sorted array. Any modifications done to NewArray or its |
| contents will not affect the heap. |
| |
-------------------------------------------------------------------
*/

#ifndef __HeapTreeClassH__
#define __HeapTreeClassH__

#include <assert.h> // For error-checking purposes

//-------------------------------------------------
// Main structure of HeapTree Class:
//-------------------------------------------------

template <class Elem>
class HeapTree
{
public:
HeapTree(int MaxSize=500);
HeapTree(const HeapTree<Elem> &OtherTree);
HeapTree(Elem *Array, int ElemNum, int MaxSize);
Elem *Sort(void); // Built-in HeapSort Algorithm
~HeapTree(void);

bool Add(const Elem &Item); // Add the Item to Heap
Elem Remove(void); // Remove and return Item from Heap

inline int GetSize(void); // Returns the number of nodes in the Heap

protected:
Elem *Data; // Actual Data array
int CurrentNum; // Current number of elements
const int MAX_SIZE; // The maximum number of elements

void ShiftUp(int Node); // Shift Node up into place
void ShiftDown(int Node); // Shift Node down into place

inline int ParentOf(int Node); // Returns Parent location
inline int LeftChildOf(int Node); // Returns Left Child location
};

//-------------------------------------------------
// Implementation of HeapTree Class:
//-------------------------------------------------

// HeapTree constructor function
template <class Elem>
HeapTree<Elem>::HeapTree(int MaxSize)
: MAX_SIZE(MaxSize)
{
Data = new Elem[MAX_SIZE];
CurrentNum = 0;
}

// HeapTree copy constructor function
template <class Elem>
HeapTree<Elem>::HeapTree(const HeapTree<Elem> &OtherTree)
: MAX_SIZE(OtherTree.MAX_SIZE)
{
Data = new Elem[MAX_SIZE];
CurrentNum = OtherTree.CurrentNum;

// Copy the array
for (int i = 0; i < OtherTree.CurrentNum; ++i)
Data[i] = OtherTree.Data[i];
}

// HeapTree array constructor
template <class Elem>
HeapTree<Elem>::HeapTree(Elem *Array, int ElemNum, int MaxSize)
: MAX_SIZE(MaxSize)
{
Data = new Elem[MAX_SIZE];
CurrentNum = ElemNum;

// This copies the array into the heap's internal array
for (int i = 0; i < ElemNum; ++i)
Data[i] = Array[i];

// This organizes the Array into a proper HeapTree
for (int i = ParentOf(CurrentNum - 1); i >= 0; --i)
ShiftDown(i);
}

// Built-in Heap Sort algorithm
template <class Elem>
Elem *HeapTree<Elem>::Sort(void)
{
// This is the array that will be returned
Elem *NewArray = new Elem[CurrentNum];

// The algorithm works back to front, with the sorted
// elements being stored in NewArray
for (int ElemNum = CurrentNum-1; ElemNum >=0; --ElemNum)
{
// Since the Remove() function alters CurrentNum by subtracting 1
// from it each time, we must use a seperate variable to
// index NewArray.
NewArray[ElemNum] = Remove();
}
return NewArray;
}

// HeapTree destructor function
template <class Elem>
HeapTree<Elem>::~HeapTree(void)
{
if (Data)
delete Data;
}

// Add() function
template <class Elem>
bool HeapTree<Elem>::Add(const Elem &Item)
{
if (CurrentNum >= MAX_SIZE) // If we have reached our maximum capacity
return false;
Data[ CurrentNum ] = Item;
ShiftUp(CurrentNum++);
return true;
}

// Remove() function
template <class Elem>
Elem HeapTree<Elem>::Remove(void)
{
assert(CurrentNum > 0);

Elem Temp = Data[0];
Data[0] = Data[--CurrentNum]; // Replace with the last element
ShiftDown(0);
return Temp;
}

// GetSize() function
template <class Elem>
inline int HeapTree<Elem>::GetSize(void)
{
return CurrentNum;
}

// ShiftUp() function
template <class Elem>
void HeapTree<Elem>::ShiftUp(int Node)
{
int Current = Node,
Parent = ParentOf(Current);
Elem Item = Data[Current];

while (Current > 0) // While Current is not the RootNode
{
if (Data[Parent] < Item)
{
Data[Current] = Data[Parent];
Current = Parent;
Parent = ParentOf(Current);
}
else
break;
}
Data[Current] = Item;
}

// ShiftDown() function
template <class Elem>
void HeapTree<Elem>::ShiftDown(int Node)
{
int Current = Node,
Child = LeftChildOf(Current);
Elem Item = Data[Current]; // Used to compare values

while (Child < CurrentNum)
{
if (Child < (CurrentNum - 1))
if (Data[Child] < Data[Child+1]) // Set Child to largest Child node
++Child;

if (Item < Data[Child])
{ // Switch the Current node and the Child node
Data[Current] = Data[Child];
Current = Child;
Child = LeftChildOf(Current);
}
else
break;
}
Data[Current] = Item;
}

// ParentOf() function
template <class Elem>
inline int HeapTree<Elem>::ParentOf(int Node)
{
assert(Node > 0);
// This uses the fact that decimals are truncated during
// the division of integers. Thus, (12 - 1) / 2 == 5
return (Node - 1) / 2;
}

// LeftChildOf() function
template <class Elem>
inline int HeapTree<Elem>::LeftChildOf(int Node)
{
return (Node * 2) + 1;
}

#endif /*__HeapTreeClassH__*/

انم نحوه ی عمل کرد ش(به صورت شکل)

کد:

---

http://upload.wikimedia.org/wikipedia/en/1/1b/Sorting_heapsort_anim.gif

---

جواب شما در تاپيك جوجه مهندسان ..........

کد:

---

http://www.forum.p30world.com/showthread.php?t=184141

---