- بواسطة x32x01 ||
يعنى ايه Quick sort وازاى يعتبر من افضل ال Algorithms فى ال Sorting ؟!!
فى الاول احنا محتاجين نتكلم عن Algorithm مهم اسمه divide and conquer
- ال Algorithm ده ببساطة هو عبارة عن انك بتقسم المشكلة بتاعتك لاجزاء صغيرة لحد ما توصل لجزء بيكون اسمه base case وده عبارة عن الحل بتاعنا
- لما بتوصل لل base case فانتا كدا بتكون وصلت للحل بتاع المشكلة
- وبعد كدا بتروح تجمع كل الاجزاء الصغيرة دى مع بعض وبكدا انتا بتكون حليت المشكلة بتاعتك
طب احنا هنستفاد ايه من ال Algorithm ده فى ال Quick sort ؟!!
- ال Algorithm ده هو المبدأ اللى بيمشى بيه ال Quick sort فى حل المشكلة وبيمشى بيه كالتالى :
- انه بيقسم ال Array بتاعتنا لمجموعة من الاجزاء الصغيرة بيكون اسمها base case
- ال base case بتاعتنا بتكون فى ال Array اللى احنا عايزين نرتبها عبارة عن عنصر واحد منها سواء بيحتوى قيمة او لأ
- كل جزء من الاجزاء دى بتكون موجودة فى مكانها الصحيح فى ال Array لو ال Array بتاعتنا مترتبة
- بعد كدا بيروح يجمع الاجزاء الصغيرة دى مع بعضها وعلشان كل عنصر بيكون فى مكانه الصحيح فالناتج بتاع تجميع الاجزاء دى بتكون ال Array بتاعتنا مترتبة
خلينا بقا نضرب مثال على Array مش مترتبة وعايزين نرتبها بيه
- تخيل كدا انك معاك Array مش مترتبة وفيها 7 عناصر عبارة عن ارقام من 1 الى 7 وانتا عايز ترتبها باستخدام ال Quick sort :
-- هتاخد رقم عشوائى من ال Array بتاعتك وليكن مثلا الرقم الاول فيها ( والعنصر ده بيكون اسمه pivot )
-- نفترض ان الرقم اللى انتا اخترت هو الرقم 4
-- انتا هتحاول تخلى الرقم بتاعك ده فى مكانه الصحيح فى ال Array بتاعتك
-- وده هيحصل لما يكون كل الارقام اللى على يمين الرقم ده تكون اكبر منه والارقام اللى على شماله هتكون اصغر منه
-- وعلشان ال Array بتاعتنا مش مترتبه فهتكون الارقام اللى على يمين الرقم 4 اكبر منه بس مش مترتبين
-- و هتكون الارقام اللى على شمال الرقم 4 اقل منه بس مش مترتبين
-- لما نوصل للمرحلة دى فهيكون الرقم 4 بقا فى مكانه الصحيح فى ال Array لو كانت ال Array بتاعتنا مترتبه
-- وهنا بقا يجى دور ال Recursion
-- هنكرر نفس الخطوات اللى فاتت على كل العناصر فى ال Array بتاعتنا وده هيحصل كالتالى :
-- هنكرر نفس الخطوات اللى عملناها مع الرقم 4 على الجزئين بتوع ال Array بتاعتنا اللى مش مترتبين ( مجموعة الارقام اللى على شمال الرقم 4 - ومجموعة الارقام اللى على يمين الرقم 4 )
-- لما نخلص مجموعة الخطوات بتاعتنا فهتكون ال Array بتاعتنا اتقسمت لمجموعة من الارقام وكل رقم موجود فى مكانه الصحيح لو كانت ال Array مترتبه
-- هنجمع مجموعة الارقام دى مع بعضها فى ال Array وكدا بقت ال Array بتاعتنا مترتبه
طب ايه بقا مميزات ال Quick sort ؟!!
- انه مش بيحتاج extra space ( مساحة زيادة من ال Memory ) وهو شغال علشان يخزن فيها اى بيانات
- انه بيكون اسرع من ال Selection sort وكمان بيكون اسرع من ال Merge sort ( هنشرح ال Merge sort فى مقالة لوحده ان شاء الله وهنشرح ليه ال Quick sort اسرع منه فى بعض الحالات )
فى الاول احنا محتاجين نتكلم عن Algorithm مهم اسمه divide and conquer
- ال Algorithm ده ببساطة هو عبارة عن انك بتقسم المشكلة بتاعتك لاجزاء صغيرة لحد ما توصل لجزء بيكون اسمه base case وده عبارة عن الحل بتاعنا
- لما بتوصل لل base case فانتا كدا بتكون وصلت للحل بتاع المشكلة
- وبعد كدا بتروح تجمع كل الاجزاء الصغيرة دى مع بعض وبكدا انتا بتكون حليت المشكلة بتاعتك
طب احنا هنستفاد ايه من ال Algorithm ده فى ال Quick sort ؟!!
- ال Algorithm ده هو المبدأ اللى بيمشى بيه ال Quick sort فى حل المشكلة وبيمشى بيه كالتالى :
- انه بيقسم ال Array بتاعتنا لمجموعة من الاجزاء الصغيرة بيكون اسمها base case
- ال base case بتاعتنا بتكون فى ال Array اللى احنا عايزين نرتبها عبارة عن عنصر واحد منها سواء بيحتوى قيمة او لأ
- كل جزء من الاجزاء دى بتكون موجودة فى مكانها الصحيح فى ال Array لو ال Array بتاعتنا مترتبة
- بعد كدا بيروح يجمع الاجزاء الصغيرة دى مع بعضها وعلشان كل عنصر بيكون فى مكانه الصحيح فالناتج بتاع تجميع الاجزاء دى بتكون ال Array بتاعتنا مترتبة
خلينا بقا نضرب مثال على Array مش مترتبة وعايزين نرتبها بيه
- تخيل كدا انك معاك Array مش مترتبة وفيها 7 عناصر عبارة عن ارقام من 1 الى 7 وانتا عايز ترتبها باستخدام ال Quick sort :
-- هتاخد رقم عشوائى من ال Array بتاعتك وليكن مثلا الرقم الاول فيها ( والعنصر ده بيكون اسمه pivot )
-- نفترض ان الرقم اللى انتا اخترت هو الرقم 4
-- انتا هتحاول تخلى الرقم بتاعك ده فى مكانه الصحيح فى ال Array بتاعتك
-- وده هيحصل لما يكون كل الارقام اللى على يمين الرقم ده تكون اكبر منه والارقام اللى على شماله هتكون اصغر منه
-- وعلشان ال Array بتاعتنا مش مترتبه فهتكون الارقام اللى على يمين الرقم 4 اكبر منه بس مش مترتبين
-- و هتكون الارقام اللى على شمال الرقم 4 اقل منه بس مش مترتبين
-- لما نوصل للمرحلة دى فهيكون الرقم 4 بقا فى مكانه الصحيح فى ال Array لو كانت ال Array بتاعتنا مترتبه
-- وهنا بقا يجى دور ال Recursion
-- هنكرر نفس الخطوات اللى فاتت على كل العناصر فى ال Array بتاعتنا وده هيحصل كالتالى :
-- هنكرر نفس الخطوات اللى عملناها مع الرقم 4 على الجزئين بتوع ال Array بتاعتنا اللى مش مترتبين ( مجموعة الارقام اللى على شمال الرقم 4 - ومجموعة الارقام اللى على يمين الرقم 4 )
-- لما نخلص مجموعة الخطوات بتاعتنا فهتكون ال Array بتاعتنا اتقسمت لمجموعة من الارقام وكل رقم موجود فى مكانه الصحيح لو كانت ال Array مترتبه
-- هنجمع مجموعة الارقام دى مع بعضها فى ال Array وكدا بقت ال Array بتاعتنا مترتبه
طب ايه بقا مميزات ال Quick sort ؟!!
- انه مش بيحتاج extra space ( مساحة زيادة من ال Memory ) وهو شغال علشان يخزن فيها اى بيانات
- انه بيكون اسرع من ال Selection sort وكمان بيكون اسرع من ال Merge sort ( هنشرح ال Merge sort فى مقالة لوحده ان شاء الله وهنشرح ليه ال Quick sort اسرع منه فى بعض الحالات )