อธิบาย bubble sort, insertion sort และ selection sort

Question

IT Interview Practice · Accepted Answer

นี่คือการเรียงลำดับแบบเปรียบเทียบง่ายๆ **O(n²)** สามแบบ พวกมันช้าสำหรับอินพุตที่มีขนาดใหญ่ แต่ง่ายต่อการเข้าใจ และมีประโยชน์สำหรับการสอนกลไกของการเรียงลำดับ

## วิธีการทำงานของแต่ละอัน

- **Bubble sort:** สลับคู่ที่อยู่ติดกันที่ไม่ได้เรียงลำดับซ้ำๆ ค่าขนาดใหญ่ "ลอยขึ้น" ไปที่ส่วนท้ายในแต่ละรอบ
- **Selection sort:** หาค่าต่ำสุดของส่วนที่ยังไม่ได้เรียงลำดับและสลับไปยังตำแหน่ง
- **Insertion sort:** ขยายคำนำหน้าที่เรียงลำดับแล้วโดยแทรกแต่ละองค์ประกอบใหม่ไปยังตำแหน่งที่ถูกต้อง

## ตัวอย่าง (insertion sort)

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # element to place
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # shift bigger elements right
            j -= 1
        arr[j + 1] = key              # drop key into the gap
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]
```

## การเปรียบเทียบ

| เรียงลำดับ | ดีที่สุด | แย่ที่สุด | มีเสถียรภาพ | ในที่เดิม |
|-----------|---------|---------|----------|----------|
| Bubble | O(n) | O(n²) | ใช่ | ใช่ |
| Selection | O(n²) | O(n²) | ไม่ใช่ | ใช่ |
| Insertion | O(n) | O(n²) | ใช่ | ใช่ |

## เมื่อใดควรใช้ / ข้อบกพร่อง

Insertion sort มีความเร็วจริงสำหรับอาร์เรย์ **ขนาดเล็กหรือเกือบเรียงลำดับแล้ว** และใช้ภายในการเรียงลำดับแบบไฮบริด หลีกเลี่ยงทั้งสามบนข้อมูลขนาดใหญ่ที่ยังไม่เรียงลำดับ — ใช้การเรียงลำดับ O(n log n) แทน

## เหตุใดจึงสำคัญ

การเรียงลำดับเหล่านี้สร้างสัญชาตญาณสำหรับค่าคงที่ การสลับ และเสถียรภาพก่อนที่คุณจะเผชิญกับอัลกอริทึมขั้นสูง

Insertion sort โดยเฉพาะปรากฏอยู่ในการเรียงลำดับระดับการผลิต (เช่น Timsort) สำหรับ subarray ขนาดเล็ก

การรู้ว่าทำไมพวกมันถึงเป็น O(n²) ทำให้การกระโดดไปยังการเรียงลำดับ O(n log n) มีความหมาย

เรียงลำดับ	ดีที่สุด	แย่ที่สุด	มีเสถียรภาพ	ในที่เดิม
Bubble	O(n)	O(n²)	ใช่	ใช่
Selection	O(n²)	O(n²)	ไม่ใช่	ใช่
Insertion	O(n)	O(n²)	ใช่	ใช่

วิธีการทำงานของแต่ละอัน

ตัวอย่าง (insertion sort)

การเปรียบเทียบ

เมื่อใดควรใช้ / ข้อบกพร่อง

เหตุใดจึงสำคัญ

คำถามที่เกี่ยวข้อง