خوارزم التحديد أو الاختيار Selection Sort Algorithm

Spread the love

خوارزم التكويم Heap Sort Algorithm

(بواسطة : رسيــــس | بتاريخ : 10 أغسطس 2004 )

بسم الله الرحمن الرحيم

خوارزم التكويم Heap Sort Algorithm

هذا الخوارزم لا يتطلب أكثر من مصفوفة كي يرتب عناصر مصفوفة ما، ولا يحتاج كذلك لعمليات التكرار والإعادة العديدة massive recursion، لذلك يعتبر مناسب لترتيب مصفوفات تحوي ملايين العناصر.

طريقة عمله كما يوحي لك اسمه، يبدأ ترتيبه ببناء كومة خارجية مكدسة من مجموعة بيانات المصفوفة (لنقل أنه يحفظها على القرص Hard Disk)، ثم ينقل أكبر عنصر من هذه الكومة ويكومه في آخر المصفوفة المرتبة، وبعد إخراج أكبر عنصر من الكومة heap يعيد بناء الكومة من جديد ويخرج منها أكبر عنصر متبقي فيها وينقله إلى المكان ما قبل الأخير في المصفوفة المرتبة ….. وهكذا حتى يكتمل ترتيب المصفوفة المرتبة ولا يبقى بيان واحد في الكومة heap!

البناء الأولي لهذا الخوارزم برمجياً يتطلب وجود مصفوفتين، الأولى تعمل كالكومة والثانية تعمل لحفظ البيانات المرتبة، ولكننا سنمثل هذا الخوارزم بخدعة ونستخدم مصفوفة واحدة تعمل كالمكوم ويتم ترتيب العناصر فيها في نفس الوقت، فعندما نخرج أي عنصر أو بيان من هذه المصفوفة نقوم بتحرير مكان خالي في آخر المصفوفة كي يحتوي هذا العنصر!

إليكم تمثيل هذا الخوارزم بلغة السي شارب:

// array of integers to hold values
private int[] a = new int[100];

// number of elements in array
private int x;

// Heap Sort Algorithm
public void sortArray()
{
int i;
int temp;

for( i = (x/2)-1; i >= 0; i– )
{
siftDown( i, x );
}

for( i = x-1; i >= 1; i– )
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
siftDown( 0, i-1 );
}
}

public void siftDown( int root, int bottom )
{
bool done = false;
int maxChild;
int temp;

while( (root*2 <= bottom) && (!done) )
{
if( root*2 == bottom )
maxChild = root * 2;
else if( a[root * 2] > a[root * 2 + 1] )
maxChild = root * 2;
else
maxChild = root * 2 + 1;

if( a[root] < a[maxChild] )
{
temp = a[root];
a[root] = a[maxChild];
a[maxChild] = temp;
root = maxChild;
}
else
{
done = true;
}
}
}

 

لنطبق البرنامج ونرى النتيجة بعد استخدامنا لبرنامجنا “خوارزميات الترتيب” كالتالي مثلاً:

كما لاحظت، استطعنا أن نكوم بعض العناصر في طرف المصفوفة ونرتب العناصر الآخرى في طرفها الآخر 🙂

حتى هنا نكون قد شرحنا أربعة خوارزميات من أشهر خوارزميات الترتيب، نكتفي بذلك في هذه الآونة وإن شاء الله إذا أتت فرصة أخرى سنكمل شرح الثلاثة خوارزميات المتبقية أو نترك المجال لمن يحب أن يشارك بشرحها..

أرجوا أن تكونوا استمتعتم بهذه السلسلة، ووفق الله الجميع لما يحب ويرضى..

الكاتب geek4arab

geek4arab

مواضيع متعلقة

التعليقات مغلقة