Sorting: bubble, selection, and insertion · Sorting: bubble, selection, และ insertion
Putting an array in order
- Sorting rearranges an array so the items go from smallest to largest.
- We sort in place: we move items around inside the same array, with no return value.
- Three classic methods do this: bubble, insertion, and selection sort.
การเรียง array เป็นระเบียบ
- การเรียงลำดับ (Sorting) จัดเรียงอาร์เรย์เพื่อให้รายการเรียงจากน้อยไปมาก
- เรารับ Sort ในสถานที่ (In place): เราย้ายข้อมูลภายในอาร์เรย์เดิม โดยไม่มีค่าที่คืนกลับมา
- มีวิธีคลาสสิกสามแบบที่ทำสิ่งนี้: Bubble, Insertion และ Selection sort
Swapping two elements
- Every sort needs to swap two items. Save one in a temporary, then overwrite.
int t = a[i]; a[i] = a[j]; a[j] = t;exchanges positionsiandj.- Forgetting the temporary loses one of the values — always keep it.
การสลับสององค์ประกอบ
- การ Sort ทุกชนิดจำเป็นต้อง สลับ (Swap) สองรายการ เก็บไว้ในตัวแปรชั่วคราว แล้วจึงทับด้วยค่าใหม่
int t = a[i]; a[i] = a[j]; a[j] = t;สลับตำแหน่งiและj- หากลืมใช้ตัวแปรชั่วคราว จะสูญเสียค่าหนึ่งไป — ต้องเก็บไว้เสมอ
Bubble sort
- Go through the array and compare each pair of neighbours:
a[j]anda[j + 1]. - If they are in the wrong order, swap them. The biggest value "bubbles" to the end.
- Repeat the passes until the whole array is in order.
บับเบิลซอร์ต
- looping ผ่านอาร์เรย์และเปรียบเทียบคู่ของ เพื่อนบ้าน (Neighbours):
a[j]และa[j + 1] - ถ้าเรียงผิดให้สลับกัน ค่าที่ใหญ่สุดจะ "ฟู่" ไปทางปลายอาร์เรย์
- ทำซ้ำรอบLoop จนกว่าอาร์เรย์ทั้งหมดจะเรียงเป็นระเบียบ
Insertion sort
- Treat the left part of the array as already sorted, and grow it one item at a time.
- Take the next item as a key, shift bigger sorted items to the right, then drop the key into the gap.
- This is how many people sort playing cards in their hand.
อินเซอร์ชันซอร์ต
- มองส่วนซ้ายของอาร์เรย์ว่าเป็นส่วนที่เรียงแล้ว และขยายมันทีละ(item)item
- นำรายการถัดมาเป็น คีย์ (Key) เลื่อนรายการที่เรียงแล้วซึ่งมีค่ามากกว่าไปทางขวา แล้ววางคีย์ลงในช่องว่าง
- นี่คือวิธีการ很多人的จัดเรียงไพ่ในมือ
#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;
}
Common mistakes
- Bubble, selection and insertion sort are all O(n²).
- Trace a small array by hand to check your sort.
ข้อผิดพลาดที่พบบ่อย
- Bubble, Selection และ Insertion sort ล้วนเป็น O(n²)
- ทดสอบ array เล็กๆ ด้วยมือเพื่อตรวจสอบการ sort ของคุณ
Now you try
- Sort ascending (smallest first), in place, with no return value.
- The checker tries several arrays, including negatives and an already-sorted one.
- Do not write a
main— the checker provides one.
ลองดูเลย
- Sort ตามลำดับเพิ่มขึ้น (Ascending) (น้อยก่อน), In place, ไม่มีค่าที่คืนกลับมา
- ตัวตรวจสอบลองกับหลายอาร์เรย์ รวมถึงที่มีเลขติดลบและเรียงเรียบร้อยแล้ว
- อย่า เขียน
main— ตัวตรวจสอบจะจัดเตรียมให้
Watch a sort run · ดูการจัดเรียงทำงาน
Bubble / selection / insertion all compare and swap into order. · Bubble / selection / insertion เปรียบเทียบและสลับเข้าที่
Complete void swap(int a[], int i, int j) so it exchanges the items at index i and j, in place (no return). Do not write a main. · เติม void swap(int a[], int i, int j) สลับตำแหน่งที่ index i และ j โดยตรง (ไม่ส่งค่ากลับ) ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do not write a main. · เติม void bubble_sort(int a[], int n) เรียง array จากน้อยไปมากโดยตรงใช้ Bubble sort ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete void insertion_sort(int a[], int n) so it sorts the array ascending, in place, using insertion sort (take each item as a key and shift bigger items right). Do not write a main. · เติม void insertion_sort(int a[], int n) เรียง array จากน้อยไปมากโดยตรงใช้ Insertion sort (ดึงรายการเป็น key เลื่อนรายการที่ใหญ่กว่าไปทางขวา) ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่