خوارزميات JavaScript: الترتيب السريع

Quicksort هي خوارزمية بحث أكثر كفاءة مناختيار نوعوفي معظم الحالات، ويستفيد من العودية.

التكرار يعني أننا نستدعي دالة من نفس الوظيفة. إنها ممارسة مفيدة جدًا ، في بعض الأحيان ، وهذه واحدة من تلك الحالات.

لقد قلت "في معظم الحالات" ، لأنه كما سنرى ، في أسوأ الحالات ، يمكن أن يستغرق فرز الفقاعة نفس وقت نوع التحديد:O(n^2). ولكن في أفضل سيناريو ، سيتم تشغيله عندO(n log n)، الذي يقع في المنتصف بينهماO(n)وO(n^2).

كيف يعمل؟ بالنظر إلى مصفوفة ، نختار عنصرًا يسمىمحور. ثم نحصل على جميع العناصر أصغر من المحور ، والعناصر أكبر من المحور.

ثم نقوم بتشغيل نفس العملية على المصفوفة 2 التي تتكون من العناصر الأصغر والأكبر.

من الأسهل رؤية الرمز بدلاً من وصفه:

const quickSort = (originalList) => {
  const list = [...originalList]

if (list.length < 2) { return list }

const pivot = list[0]

const smaller = list.filter((item) => item < pivot) const bigger = list.filter((item) => item > pivot)

return […quickSort(smaller), pivot, …quickSort(bigger)] }

في هذه الحالة اخترت المحور ليكون العنصر الأول في المصفوفة ، ولكن يمكن أيضًا أن يكون العنصر في المنتصف ، على سبيل المثال:

const pivot = list[Math(floor(list.length / 2)]

لاحظ كيف قمنا بنسخ المصفوفة أولاً ، لذلك اتصلquickSort()لا يقوم بتعديل المصفوفة الأصلية ، بل يقوم فقط بإرجاع مصفوفة مرتبة جديدة:

const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]

console.log(quickSort(a)) //[0, 1, 1, 3, 4, 4, 5, 6, 8 console.log(a) //[1, 6, 3, 4, 5, 1, 0, 4, 8]


المزيد من دروس js: