ความแตกต่างระหว่าง Bubble Sort และ Selection Sort

ในโพสต์นี้ เราจะทำความเข้าใจความแตกต่างระหว่าง Bubble Sort และ Selection Sort

Bubble Sort

• อัลกอริทึมจัดเรียงง่าย
• วนลูปผ่านรายการ เปรียบเทียบ adjacent pairs ของ elements เพื่อจัดเรียง
• ทำ swaps ตาม adjacent elements
• มีประสิทธิภาพมากกว่า selection sort (ในบางบริบท)
• ช้ากว่า selection sort
• ใช้ item exchanging เพื่อ swap elements
• Element ถูก swap ซ้ำๆ จนทุกตัวเรียงถูกต้อง

อัลกอริทึม Bubble Sort:

begin BubbleSort(list)
    for all elements of list
        if list[i] > list[i+1]
            swap(list[i], list[i+1])
        end if
    end for
    return list
end BubbleSort

Selection Sort

• หา minimum หรือ maximum จากรายการก่อน
• จัดเรียงรายการ ascending หรือ descending
• เลือก min/max element จาก unsorted sub-array วางในตำแหน่งถัดไปของ sorted sub-array
• ถือเป็น unstable sorting algorithm
• Time complexity ทุกกรณี O(n²)
• มีประสิทธิภาพน้อยกว่า insertion sort
• จำนวน comparisons ระหว่าง iterations มากกว่า element swapping
• ตำแหน่งของทุก element ในรายการทราบล่วงหน้า
• ผู้ใช้ค้นหา element ที่ต้อง insert ที่ตำแหน่งเฉพาะ
• มีประสิทธิภาพมากกว่า bubble sort
• เร็วกว่า bubble sort
• ใช้ item selection

อัลกอริทึม Selection Sort:

Step 1 - Set MIN to location 0
Step 2 - Search the minimum element in the list
Step 3 - Swap with value at location MIN
Step 4 - Increment MIN to point to next element
Step 5 - Repeat until list is sorted