خوارزميات جافا سكريبت: فرز الفقاعات

الفرز الفقاعي عبارة عن خوارزمية بسيطة للفرز ، ولكنه أيضًا غير فعال تمامًا ، كما هو الحال في أسوأ حالاتهO(n^2)تعقيد.

لكن الأمر يستحق التعلم عنه.

نحن نمرّر عبر مصفوفة ، ونواصل مقارنة عنصر واحد بالعنصر المجاور له مباشرةً.

إذا كان العنصر الموجود على اليمين أصغر ، فإننا نتبادل الموضعين.

هذا هو تطبيقنا:

const bubbleSort = (originalArray) => {
  let swapped = false

const a = […originalArray]

for (let i = 1; i < a.length - 1; i++) { swapped = false

<span style="color:#66d9ef">for</span> (<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">j</span> <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; <span style="color:#a6e22e">j</span> <span style="color:#f92672">&lt;</span> <span style="color:#a6e22e">a</span>.<span style="color:#a6e22e">length</span> <span style="color:#f92672">-</span> <span style="color:#a6e22e">i</span>; <span style="color:#a6e22e">j</span><span style="color:#f92672">++</span>) {
  <span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>] <span style="color:#f92672">&lt;</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span>]) {
    ;[<span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span>], <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>]] <span style="color:#f92672">=</span> [<span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>], <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span>]]
    <span style="color:#a6e22e">swapped</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">true</span>
  }
}

<span style="color:#66d9ef">if</span> (<span style="color:#f92672">!</span><span style="color:#a6e22e">swapped</span>) {
  <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">a</span>
}

}

return a }

يمكنك ان ترا الO(n^2)يأتي من حقيقة أننا نقوم بتكرار المصفوفة مرتين ، للتحقق مما إذا كنا بحاجة إلى تبديل العنصر بالعنصر الموجود على اليمين.

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

هذا مثال:

لنفترض أننا نجريbubbleSort([2, 1, 3]).

نقارن أولاً 2 بـ 1. 2 هي> 1 ، لذلك نتبادلها:

1 2 3

then we compare 2 with 3. 2 < 3, so we leave it as-is. We skip the last element, since we know that due to our workflow, it’s always going to be the biggest element.


More js tutorials: