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

-=-=-=-=-=-=-=-

كثيرٌ منّا يبحث عن بعض الـcodes على الانترنت، وقليل منّا من يقرأ ويفهم ما يجده بسرعة وسهولة، نظراً لكثرة المتغيرات في الـcode وتداخل أسماءها!
بعد قراءتك لهذا الدرس، وتعرفك على القواعد والملاحظات التي يجب أن تأخذ بعين الاعتبار حينما تختار أسماءاً للمتغيرات في برنامجك، ستكتب برامجك بطريقة احترافية، وتقرأ وتفهم برامج المحترفين بسهولة وسرعة إن شاء الله 🙂

عند كتابتك للبرنامج، لابد من ملاحظة القاعدات التالية عند تسميّة المتغيرات:

أما الملاحظات التي لابد لك من معرفتها هي:

-=-=-=-=-=-=-=-

PascalCasing Naming Convention:

لاستخدام PascalCasing Naming Convention، اجعل أول حرف من كل كلمة بشكل capital، وباقي أحرف الكلمة small. استخدم هذا الطريقة في تسمية كلاً من:

• الفئات classes.
• الطرق methods أو الدوال functions.
• الخصائص properties.
• الكائنات الجديدة enums.
• الواجهات interfaces.
• الثوابت read only and constant.
• namespaces or packages.

أمثلة على ذلك على ذلك:

[C]
void InitilaizeData ( );  /* multiple-word name*/

[Visual Basic]
Public Class FileStream /* multiple-word name*/
Public Class Button
Public Class String

[C#]
public class FileStream /* multiple-word name*/
public class Button
public class String

-=-=-=-=-=-=-=-

camelCasing Naming Convention:

لاستخدام camelCasing Naming Convention:، اجعل أول حرف من كل كلمة بشكل capital باستثناء الكلمة الأولى، استخدم هذه الطريقة في تسمية:

• المتغيرات variables.
• المعاملات parameters or arguments.

أمثلة على ذلك:

[C]
int loopCountMax; /* multiple-word name*/
char flower;

[Visual Basic]
GetType(typeName As String)As Type /* multiple-word name*/
Format(format As String, args() As object)As String

[C#]
Type GetType(string typeName) /* multiple-word name*/
string Format(string format, object[] args)

ملاحظة:
سمّيت هذه الطريقة بـcamelCasing لأن ظهور حرف كبير في وسط الاسم المركب يشبه نتوء السنام في الجمل:

-=-=-=-=-=-=-=-

وفي نهاية درسنا، تذكر أن اسم المتغير يفضّل أن يكون اسماً له معنى مختص بعمل المتغير في البرنامج، فمثلاً لو مثّل المتغيّر عداداً في البرنامج، يفضّل أن تسميه counter بدلاً من i أو j. ولو كنت تكتب class لبرنامج مختص بشركتك، يفضل أن تكتب اسم الشركة Computer4Arab مثلاً بدلاً من أن تكتب MyCompany.
وبالنسبة لصيغة الجمع او المفرد، فإن ذلك لا يشكل أي فارق ويرجع لحس المبرمج، ولكن يفضل استخدام صيغة الجمع فقط مع namespaces or packeges.

للمزيد، يمكنك قراءة مرشد تعليمات التسميات Naming Guidelines في SDK Help documentation، أو من هنا:

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpgenref/html/cpconnamingguidelines.asp

أرجو أن يكون درسي البسيط قد أضاف إليك الجديد، والسلام عليكم 🙂

-=-=-=-=-=-=-=-

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

خوارزميات الترتيب Sort Algorithms

مقدمة

إحدى أبرز المشاكل في عالم الكمبيوتر هي مشاكل الترتيب.. أي كيفية ترتيب قائمة من العناصر الغير مرتبةز،. وهنالك العديد من الحلول لهذه المشاكل تعرف باسم “خوارزميات الترتيب Sort Algorithms”، بعضٌ من هذه الخوارزميات سهلة وبديهية، بينما بعضها الآخر معقد، في النهاية كلاً منهم يعطي نتائج مذهلة وللمبرمج حرية الاختيار.

أشهر سبعة خوارزميات للترتيب هي:

1. خوارزم الفقاعة Bubble
2. خوارزم الحشر Insertion
3. خوارزم التحديد Selection
4. خوارزم التكويم Heap
5. خوارزم الدمج Merge
6. خوارزم السرعة Quick
7. خوارزم الهيكل Shell

سنتعرف في هذه السلسلة بإذن الله على كل 4 خوارزميات، نشرحها ونكتب خرائط التدفق flowcharts الخاصة بها ونقوم بتطبيق برمجي coding عليها..

س وج

س/ على ماذا يطبق الترتيب؟!

ج/ على بيانات غير مرتبة!

س/ أين توجد هذه البيانات؟!

ج/ تكون:

1. مخزنة داخلياً في الحاسوب Internal  في الذاكرة مثلاً Memory.
2. أومخزنة على وسط تخزين خارجي External في ملف مثلاً File.

س/ ماهي أنواع الترتيب؟!

ج/ يكون الترتيب إما تصاعدياً أو أبجدياً (Ascending(A->Z أو تنازلياً (Descending  (Z->A.

س/ ماهي الحزمة البرمجية التي سيتم تطبيق الدروس عليها؟!

ج/ اسم هذه الحزمة “خوارزميات الترتيب Sort Algorithms” وقد قمت بفضل الله بتصميمها بالسي شارب خصيصاً لدروس هذه السلسلة، في الصورة التالية ترى واجهة البرنامج:

برنامج بسيط يمتاز بالمرونة والأهم من ذلك سنطبق عليه الخوارزميات، مع كل درس من الدروس التالية استخدم هذا البرنامج، أدخل البيانات كاملة كما في أمثلة الدروس وسترى النتيجة، يمكنك إدخال عناصر المصفوفة التي تريد ترتيبها يدوياً في النموذج بحيث تفصل بين كل عنصر والآخر بالفاصلة (،) أو أن تقوم بتخزين العناصر في ملف نصي .txt كل عنصر في سطر منفصل. إذا خزنت العناصر في ملف لابد من أن تحفظ الملف في نفس المجلد الذي يشتغل منه هذا البرنامج.

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::1 اضغط هنا لتنزيل نسخة تنفيذية(33kb)  ( غير متوفر)

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::2 اضغط هنا لتنزيل الشيفرة المصدرية (175kb) ( غير متوفر)

حتى الآن اطبّق هذه الخزمة على بيانات رقمية numerical وباستطاعتك تطويرها ما دامت مفتوحة المصدر open source.

والآن انتقل لقراءة الدرس التالي حيث سنتعرف على أول خوارزم للترتيب 🙂

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

خوارزم الفقاعة للترتيب Bubble Sort Algorithm

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

بعبارة أخرى:
يعمل هذا الخوارزم على ترتيب عناصر مصفوفة ليست مرتبة العناصر، وتتم عملية الترتيب على مراحل أو دورات phases كل مرحلة تتضمن عملية مقارنة زوجين متجاورين من العناصر واستبدال موضعهما إذا كان ترتيبهما غير صحيح… وهكذا، انظر إلى الرسم:

مثال:

لنفرض أننا نريد ترتيب مصفوفة تحتوي س من العناصر تصاعدياً، بعد دورته الأولى في المصفوفة سيكون أكبر عنصرموضوع في مكانه الصحيح (آخر المصفوفة بمعنى [س-1])، وبعد دورته الثانية سيكون ثاني أكبر عنصر في المصفوفة في مكانه الصحيح ([س-2])، ……..وهكذا، يتوقف الخوارزم متى ما أتم دورة دون تبديل في أماكن العناصر.
تقلب الآية لو كان الترتيب تنازلياً.

والآن قد تتساءل كيف نكتب هذا الكود برمجياً؟!

الإجابة سهلة، يمكنك تمثيل الخوارزم السابق بأي لغة برمجة تتقنها، وهذا هو الكود المستخدم في برنامج “خوارزميات الترتيب” الذي حملّته من درس المقدمة:

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

// number of elements in array
private int x;

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

for( i = (x – 1); i >= 0; i– )
{
for( j = 1; j <= i; j++ )
{
if( a[j-1] > a[j] )
{
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}

والنتيجة بعد استخدام برنامجنا وتطبيق هذا الكود فيه:

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::2
::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::3	عناصر المصفوفة قبل الترتيب:<br /> <br>[1] [8] [2] [9] [3] [7] [6] [5]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 1:<br /> <br>[1] [2] [8] [3] [7] [6] [5] [9]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 2:<br /> <br>[1] [2] [3] [7] [6] [5] [8] [9]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 3:<br /> <br>[1] [2] [3] [6] [5] [7] [8] [9]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 4:<br /> <br>[1] [2] [3] [5] [6] [7] [8] [9]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 5:<br /> <br>[1] [2] [3] [5] [6] [7] [8] [9]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 6:<br /> <br>[1] [2] [3] [5] [6] [7] [8] [9]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 7:<br /> <br>[1] [2] [3] [5] [6] [7] [8] [9]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 8:<br /> <br>[1] [2] [3] [5] [6] [7] [8] [9]<br />
::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::5

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

ربما تتسآءل منذ البدايو لماذا هذا الاسم الغريب، نعن هاأنت قد عرفت الآن بعد أن رأيت طريقة الترتيب وخطواتها في البرنامج، سميت بالفقاعة لأن العنصر الأصغر يصعد كالفقاعة إلى بداية المصفوفة 🙂

معلومة إضافية متقدمة:

لو استخدمنا مفهوم Big-Oh Notation لتحليل هذا الخوارزم لاستنتجنا أن أسوأ حالات تطبيق هذا الخوارزم هي عندما يكون (O(n² وهو نفسه درجة فعالية هذا الخوارزم في الحالة القياسية.

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

هاقد وصلنا إلى خوارزم الترتيب الثاني، سنتعرف في درس اليوم على:

خوارزم الحشر Insertion Sort Algorithm

تعمل هذه الطريقة على اعتبار أن هناك مصفوفتين، في البداية تحتوي إحداهما على البيانات المطلوب ترتيبها بمعنى الغير مرتبة unsorted والأخرى فارغة. وفي النهاية ستحتوي المصفوفة الفارغة على بيانات المصفوفة الأولى ولكن مرتبه إما تصاعدياً أو تنازلياً!

الفكرة الأساسية في هذه الطريقة هي تحريك العناصر من المصفوفة الأولى (الغير مرتبة العناصر) إلى المصفوفة الثانية عنصراً كل مرة مع مراعاة وضع العنصر المتحرك في مكانه الصحيح، ولكي نضع العنصر في مكانه الصحيحة في المصفوفة الثانية المرتبة العناصر بالنسبة لجميع العناصر التي سبقت هذا العنصر المتحرك، فإن هذه العملية قد تتطلب حشر هذا العنصر الجديد بين عنصرين مرتبين مسبقاً ليأخذ  مكانه الصحيح، من هنا أتى اسم هذا الخوارزم 🙂 انظر إلى flowchart التالي والذي يحاكي العملية:

هذا أبسط تمثيل لهذا الخوارزم باستخدام مصفوفتين! ………….. نعم وكما يتبادر إلى ذهنكم الآن يمكننا أن نمثل هذا الخوارزم باستخدام مصفوفة واحدة عن طريق حشر العنصر في مكانه الصحيح فيها ثم عمل shift لبقية العناصر وهكذا ستتقسم المصفوفة الواحدة إلى قسمين، قسم به العناصر المرتبة وقسم به العناصر الغير مرتبة:

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::1

لنرى مثال على ذلك:

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::2

لنمثله الآن برمجياً ,وباستخدام مصفوفة واحدة، الكود كاملاً موجود في برنامج “خوارزميات الترتيب” الذي قمت بتحميله من درس المقدمة، هذا هو:

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

// number of elements in array
private int x;

// Insertion Sort Algorithm
public void sortArray()
{
int i;
int j;
int index;

for( i = 1; i < x; i++ )
{
index = a[i];
j = i;

while( (j > 0) && (a[j-1] > index) )
{
a[j] = a[j-1];
j = j – 1;
}

a[j] = index;
}
}

وكما رأيتم فهي من حيث السرعة مناسبة لتطبق على مصفوفة ذات ألف عنصر أو أقل. هذا الخوارزم يعتبر أسرع مرتين من طريقة الفقاعة Bubble كما أنه أسرع 40% كذلك من خوارزم التحديد Selection التي سنتعرف عليها الدرس المقبل بإذن الله.

هذه هي النتيجة باستخدام برنامجنا:

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::3
::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::4	عناصر المصفوفة قبل الترتيب:<br /> <br>[1] [8] [2] [9] [3] [7] [6] [5]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 1:<br /> <br>[1] [8] [2] [9] [3] [7] [6] [5]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 2:<br /> <br>[1] [2] [8] [9] [3] [7] [6] [5]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 3:<br /> <br>[1] [2] [8] [9] [3] [7] [6] [5]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 4:<br /> <br>[1] [2] [3] [8] [9] [7] [6] [5]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 5:<br /> <br>[1] [2] [3] [7] [8] [9] [6] [5]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 6:<br /> <br>[1] [2] [3] [6] [7] [8] [9] [5]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 7:<br /> <br>[1] [2] [3] [5] [6] [7] [8] [9]<br />
::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::6

رائع، أليس كذلك، هذه الخوارزميات تعطينا خيال برمجي كبير جداً

تابعنا في الدرس القادم ومع خوارزم جديد 🙂

معلومة إضافية متقدمة:

لو استخدمنا مفهوم Big-Oh Notation لتحليل هذا الخوارزم لاستنتجنا أن أسوأ حالات تطبيق هذا الخوارزم هي عندما يكون (O(n² وهو نفسه درجة فعالية هذا الخوارزم في الحالة القياسية.

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

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

تعمل هذه الطريقة عن طريق تحديد أو اختيار أكبر (أو أصغر) عنصر غير مرتب في المصفوفة ومن ثم تحريكه كي يشغل الحيز المتاح له في آخرها وهكذا لكل عنصر. تنتهي عملية الترتيب عندما ننتهي من تحريك جميع العناصر.

 مثال:

في هذا المثال: العناصر المظللة بالرمادي هي العناصر المختارة أو المحددة، بينما العناصر المكتوبة بالبنط العريض bold هي العناصر المرتبة في مكانها الصحيح:

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::0

من الممكن أن نستخدم مصفوفتين لعمل ذلك، بحيث تحوي الأولى العناصر غير المرتبة ويتم تخزين هذه العناصر بترتيب تصاعدي أو تنازلي في المصفوفة الثانية، سنقوم بكتابة flowchart باستخدام مصفوفتين، ثم نكتب الكود باستخدام مصفوفة واحدة:

وهاهو ذا تمثيل الخوارزم باستخدام مصفوفة واحدة بلغة السي شارب:

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

// number of elements in array
private int x;

// Selection Sort Algorithm
public void sortArray()
{
int i, j;
int min, temp;

for( i = 0; i < x-1; i++ )
{
min = i;

for( j = i+1; j < x; j++ )
{
if( a[j] < a[min] )
{
min = j;
}
}

temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}

في الحقيقة يعتبر هذا الخوارزم أفضل من خوارزم الفقاعة Bubble بقليل، لكنه ليس أفضل من خوارزم الحشر Insertion، استخدمه إن كان عدد عناصر مصفوفتك لا يتجاوز الألف ونيفاً!

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

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::2
::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::3	عناصر المصفوفة قبل الترتيب:<br /> <br>[55] [0] [4] [2] [1]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 1:<br /> <br>[0] [55] [4] [2] [1]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 2:<br /> <br>[0] [1] [4] [2] [55]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 3:<br /> <br>[0] [1] [2] [4] [55]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 4:<br /> <br>[0] [1] [2] [4] [55]<br />
::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::5

طبق المثال مباشرة على البرنامج لديك.. وتابعنا في الدرس القادم لنتعرف على خوارزم المكدّس Heap Sort Algorithm.

معلومة إضافية متقدمة:

لو استخدمنا مفهوم Big-Oh Notation لتحليل هذا الخوارزم لاستنتجنا أن أسوأ حالات تطبيق هذا الخوارزم هي عندما يكون (O(n² وهو نفسه درجة فعالية هذا الخوارزم في الحالة القياسية.

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

خوارزم التكويم 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;
}
}
}

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

	عناصر المصفوفة قبل الترتيب:<br /> <br>[1] [6] [2] [7] [3] [8] [3]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 1:<br /> <br>[7] [6] [3] [1] [3] [2] [8]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 2:<br /> <br>[6] [3] [3] [1] [2] [7] [8]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 3:<br /> <br>[3] [3] [2] [1] [6] [7] [8]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 4:<br /> <br>[3] [2] [1] [3] [6] [7] [8]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 5:<br /> <br>[2] [1] [3] [3] [6] [7] [8]<br /> <br>-=-=-=-=-=-=-=-<br /> <br>الدورة 6:<br /> <br>[1] [2] [3] [3] [6] [7] [8]<br />

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

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

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