- بواسطة x32x01 ||
يعنى ايه Insertion sort وليه يعتبر من اسهل ال Sorting algorithms ؟!!
اهلا بيك عزيزى المبرمج النهاردة هنتكلم عن ال Insertion sort وايه مميزاته وايه عيوبه وليه يعتبر من اسهل ال Sorting algorithms
خلينا الاول نفترض انك عايز تستخدمه علشان ترتب ال Array بتاعتك تصاعديا
ال Insertion sort فكرته شبه فكرة ترتيب مجموعة من اوراق اللعب ( اللى اسمها الشعبى كوتشينه ) وهو عبارة عن بتمسك كل عنصر وبتخليه فى مكانه الصحيح بين بقية العنصر بغض النظر عن بقية العناصر مترتبة ولا لأ
وعملية وضع كل عنصر فى مكانه الصحيح بتتم بناء على reference احنا اللى بنحدده ( وفى الغالب بيكون اول عنصر فى ال Array )
وبنشوف العنصر اللى احنا عايزين نخليه فى مكانه الصحيح المفروض يكون قبل ال Reference بتاعنا ولا بعده ( بناء على ان احنا عايزين نرتبها تصاعديا ولا تنازليا )
وبعد كدا بنخليه فى مكانه الصحيح بين العناصر يعنى اللى على شماله بيكون اقل منه واللى على يمينه بيكون اكبر منه ( لو عايزين نرتب تصاعدى )
والعنصر لما بنيجى نغير مكانه علشان نخليه فى مكانه الصحيح مسموح ليه انه يتحرك فى اتجاه واحد بس وهو للخلف ( يعنى لو هو العنصر 5 مسموح ليه انه يكون رقم 2 ومش مسموح ليه انه يكون رقم 7 )
ولما بتوصل لاخر عنصر وحطيته فى مكانه الصحيح بتكون انتا كدا رتبت ال Array بتاعتك
خلينا نضرب مثال على Array مش مترتبة وعايزين نرتبها باستخدام ال Insertion sort وبردو عايزين نرتبها تصاعديا
-- تخيل كدا انك معاك Array مش مترتبه وموجود فيها 10 ارقام وانتا عايز ترتبها باستخدام ال Insertion sort فهيحصل التالى :
- هتعتبر ان اول رقم فى ال Array بتاعتك موجود فى مكانه الصحيح وهيكون هو ال Reference بتاعنا
- طالما اول رقم موجود فى مكانه الصحيح فالمفروض تكون كل الارقام اللى على شماله اقل منه, وتكون كل الارقام اللى على يمينه اكبر منه ( ده علشان عايزين نرتب ال Array ترتيب تصاعدى )
- هنشوف تانى رقم فى ال Array لو اكبر من اول رقم هنسيبه فى مكانه ومش هنغير مكانه
- لو اقل من اول رقم فى ال Array فهننقله من مكانه ونخليه موجود قبل اول عنصر فى ال Array ( وكدا هيكون هو اول عنصر )
- هنشوف تالت عنصر فى ال Array لو اقل من ال Reference هنروح نخليه فى مكانه الصحيح بين العناصر ( يعنى اللى على شماله اقل منه واللى على يمينه اكبر منه )
وهنكرر العملية دى على كل عناصر ال Array بتاعتنا
- لما نخلص العمليات دى بنكون كدا خلاص عملنا ترتيب لل Array بتاعتنا
-- طب ايه ال Time complexity بتاعة ال Algorithm ده ؟!!
- O( n^2 )
طب ايه بقا مميزات ال Insertion sort ؟!!
- انه بعتبر من اسهل ال Sorting algorithms فى كتابته وتنفيذه
- انه مش بيحتاج extra space ( مساحة زيادة من ال Memory ) وهو شغال علشان يخزن فيها اى بيانات
طب ايه بقا عيوب ال Insertion sort ؟!!
- انه بيكون بطئ مقارنة بانواع تانيه من ال Sorting algorithms
- انه مش بيكون مناسب مع مجموعات البيانات الكبيرة نظرا لأنه بطئ فى عمله
اهلا بيك عزيزى المبرمج النهاردة هنتكلم عن ال Insertion sort وايه مميزاته وايه عيوبه وليه يعتبر من اسهل ال Sorting algorithms
خلينا الاول نفترض انك عايز تستخدمه علشان ترتب ال Array بتاعتك تصاعديا
ال Insertion sort فكرته شبه فكرة ترتيب مجموعة من اوراق اللعب ( اللى اسمها الشعبى كوتشينه ) وهو عبارة عن بتمسك كل عنصر وبتخليه فى مكانه الصحيح بين بقية العنصر بغض النظر عن بقية العناصر مترتبة ولا لأ
وعملية وضع كل عنصر فى مكانه الصحيح بتتم بناء على reference احنا اللى بنحدده ( وفى الغالب بيكون اول عنصر فى ال Array )
وبنشوف العنصر اللى احنا عايزين نخليه فى مكانه الصحيح المفروض يكون قبل ال Reference بتاعنا ولا بعده ( بناء على ان احنا عايزين نرتبها تصاعديا ولا تنازليا )
وبعد كدا بنخليه فى مكانه الصحيح بين العناصر يعنى اللى على شماله بيكون اقل منه واللى على يمينه بيكون اكبر منه ( لو عايزين نرتب تصاعدى )
والعنصر لما بنيجى نغير مكانه علشان نخليه فى مكانه الصحيح مسموح ليه انه يتحرك فى اتجاه واحد بس وهو للخلف ( يعنى لو هو العنصر 5 مسموح ليه انه يكون رقم 2 ومش مسموح ليه انه يكون رقم 7 )
ولما بتوصل لاخر عنصر وحطيته فى مكانه الصحيح بتكون انتا كدا رتبت ال Array بتاعتك
خلينا نضرب مثال على Array مش مترتبة وعايزين نرتبها باستخدام ال Insertion sort وبردو عايزين نرتبها تصاعديا
-- تخيل كدا انك معاك Array مش مترتبه وموجود فيها 10 ارقام وانتا عايز ترتبها باستخدام ال Insertion sort فهيحصل التالى :
- هتعتبر ان اول رقم فى ال Array بتاعتك موجود فى مكانه الصحيح وهيكون هو ال Reference بتاعنا
- طالما اول رقم موجود فى مكانه الصحيح فالمفروض تكون كل الارقام اللى على شماله اقل منه, وتكون كل الارقام اللى على يمينه اكبر منه ( ده علشان عايزين نرتب ال Array ترتيب تصاعدى )
- هنشوف تانى رقم فى ال Array لو اكبر من اول رقم هنسيبه فى مكانه ومش هنغير مكانه
- لو اقل من اول رقم فى ال Array فهننقله من مكانه ونخليه موجود قبل اول عنصر فى ال Array ( وكدا هيكون هو اول عنصر )
- هنشوف تالت عنصر فى ال Array لو اقل من ال Reference هنروح نخليه فى مكانه الصحيح بين العناصر ( يعنى اللى على شماله اقل منه واللى على يمينه اكبر منه )
وهنكرر العملية دى على كل عناصر ال Array بتاعتنا
- لما نخلص العمليات دى بنكون كدا خلاص عملنا ترتيب لل Array بتاعتنا
-- طب ايه ال Time complexity بتاعة ال Algorithm ده ؟!!
- O( n^2 )
طب ايه بقا مميزات ال Insertion sort ؟!!
- انه بعتبر من اسهل ال Sorting algorithms فى كتابته وتنفيذه
- انه مش بيحتاج extra space ( مساحة زيادة من ال Memory ) وهو شغال علشان يخزن فيها اى بيانات
طب ايه بقا عيوب ال Insertion sort ؟!!
- انه بيكون بطئ مقارنة بانواع تانيه من ال Sorting algorithms
- انه مش بيكون مناسب مع مجموعات البيانات الكبيرة نظرا لأنه بطئ فى عمله