Sorting: bubble, selection, และ insertion
หน้านี้ต้องใช้เบราว์เซอร์ล่าสุด (รองรับ SharedArrayBuffer) กรุณาอัปเดต Chrome, Edge, Firefox หรือ Safari เป็นเวอร์ชันล่าสุด
การเรียง array เป็นระเบียบ
- การเรียงลำดับ (Sorting) จัดเรียงอาร์เรย์เพื่อให้รายการเรียงจากน้อยไปมาก
- เรารับ Sort ในสถานที่ (In place): เราย้ายข้อมูลภายในอาร์เรย์เดิม โดยไม่มีค่าที่คืนกลับมา
- มีวิธีคลาสสิกสามแบบที่ทำสิ่งนี้: Bubble, Insertion และ Selection sort
การสลับสององค์ประกอบ
- การ Sort ทุกชนิดจำเป็นต้อง สลับ (Swap) สองรายการ เก็บไว้ในตัวแปรชั่วคราว แล้วจึงทับด้วยค่าใหม่
int t = a[i]; a[i] = a[j]; a[j] = t;สลับตำแหน่งiและj- หากลืมใช้ตัวแปรชั่วคราว จะสูญเสียค่าหนึ่งไป — ต้องเก็บไว้เสมอ
บับเบิลซอร์ต
- looping ผ่านอาร์เรย์และเปรียบเทียบคู่ของ เพื่อนบ้าน (Neighbours):
a[j]และa[j + 1] - ถ้าเรียงผิดให้สลับกัน ค่าที่ใหญ่สุดจะ "ฟู่" ไปทางปลายอาร์เรย์
- ทำซ้ำรอบLoop จนกว่าอาร์เรย์ทั้งหมดจะเรียงเป็นระเบียบ
อินเซอร์ชันซอร์ต
- มองส่วนซ้ายของอาร์เรย์ว่าเป็นส่วนที่เรียงแล้ว และขยายมันทีละ(item)item
- นำรายการถัดมาเป็น คีย์ (Key) เลื่อนรายการที่เรียงแล้วซึ่งมีค่ามากกว่าไปทางขวา แล้ววางคีย์ลงในช่องว่าง
- นี่คือวิธีที่หลายคนเรียงไพ่ในมือ
English
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
ข้อผิดพลาดที่พบบ่อย
- Bubble, Selection และ Insertion sort ล้วนเป็น O(n²)
- ทดลองทำด้วยมือกับข้อมูลขนาดเล็กเพื่อตรวจสอบการเรียงลำดับของคุณ
ลองดูเลย
- Sort ตามลำดับเพิ่มขึ้น (Ascending) (น้อยก่อน), In place, ไม่มีค่าที่คืนกลับมา
- ตัวตรวจสอบลองกับหลายอาร์เรย์ รวมถึงที่มีเลขติดลบและเรียงเรียบร้อยแล้ว
- อย่า เขียน
main— ตัวตรวจสอบจะจัดเตรียมให้
สำรวจ
ดูการจัดเรียงทำงาน
Bubble / selection / insertion เปรียบเทียบและสลับเข้าที่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม void swap(int a[], int i, int j) สลับตำแหน่งที่ index i และ j โดยตรง (ไม่ส่งค่ากลับ) ห้าม เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม void bubble_sort(int a[], int n) เรียง array จากน้อยไปมากโดยตรงใช้ Bubble sort ห้าม เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม void insertion_sort(int a[], int n) เรียง array จากน้อยไปมากโดยตรงใช้ Insertion sort (ดึงรายการเป็น key เลื่อนรายการที่ใหญ่กว่าไปทางขวา) ห้าม เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่