Sorting: selection and insertion sort · Sorting: Selection และ Insertion sort
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · หน้านี้ต้องใช้เบราว์เซอร์ล่าสุด (รองรับ SharedArrayBuffer) กรุณาอัปเดต Chrome, Edge, Firefox หรือ Safari เป็นเวอร์ชันล่าสุด
English
Putting an array in order
- Sorting means putting the values of an array in order, usually from small to large.
- On the AP CSA exam you must be able to write and trace two sorts: selection sort and insertion sort.
- You also need to trace (but not write) a third sort: merge sort. We look at all three here.
ไทย
การเรียง array เป็นระเบียบ
- Sorting หมายถึงการจัดค่าของ array เป็นลำดับ โดยปกติจากน้อยไปมาก
- ในการสอบ AP CSA คุณต้องสามารถ เขียน และ trace การจัดสองแบบ: selection sort และ insertion sort
- คุณยังต้อง trace (แต่ไม่ต้องเขียน) sorting第三种: merge sort. เราจะดูทั้งหมดสามแบบที่นี่
English
Selection sort: the idea
- Walk through the array from left to right.
- At each spot
i, find the smallest value in the part that is still unsorted (fromito the end). - Swap that smallest value into spot
i. Now0..iis sorted. - Repeat until the whole array is in order.
ไทย
Selection sort: ความคิด
- เดินผ่าน array จากซ้ายไปขวา
- ที่แต่ละตำแหน่ง
i, หา最小的值 ในส่วนที่ยังไม่ได้ถูกจัด (จากiถึงปลายสุด) - Swap ค่าที่น้อยที่สุดนั้นเข้าสู่ตำแหน่ง
iตอนนี้0..iถูกจัดเรียบร้อยแล้ว - ทำซ้ำจนกว่า array ทั้งหมดจะถูกจัดเป็นระเบียบ
public class Sorter {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // index of smallest so far
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // found a smaller value
}
}
int temp = a[min]; // swap a[i] and a[min]
a[min] = a[i];
a[i] = temp;
}
}
}
English
Selection sort: a trace
- Let us sort
{5, 2, 4, 1, 3}. The bold part is already sorted. - Each pass picks the smallest value from the rest and swaps it to the front.
ไทย
Selection sort: การ trace
- มาลองจัด
{5, 2, 4, 1, 3}ส่วน ตัวหนา ถูกจัดไว้แล้ว - แต่ละรอบจะเลือกค่าที่น้อยที่สุดจากส่วนที่เหลือและ swap เข้าด้านหน้า
start: [5, 2, 4, 1, 3]
i=0 smallest=1 → swap a[0],a[3]: [1 | 2, 4, 5, 3]
i=1 smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2 smallest=3 → swap a[2],a[4]: [1, 2, 3 | 5, 4]
i=3 smallest=4 → swap a[3],a[4]: [1, 2, 3, 4 | 5]
done: [1, 2, 3, 4, 5]
English
Insertion sort: the idea
- Think of holding playing cards and adding one card at a time into the right place.
- Start at index
1. Call this value the key. - Slide bigger values on the left one step to the right, until the key fits.
- Drop the key into the gap. Now everything to the left is sorted.
ไทย
Insertion sort: ความคิด
- คิดถึงการถือไพ่และเพิ่มไพ่ทีละใบเข้าไปในตำแหน่งที่ถูกต้อง
- เริ่มต้นที่ index
1. เรียกค่านีວ key - เลื่อนค่าที่ใหญ่กว่าทาง ซ้าย ไปทางขวาหนึ่งขั้น จนกว่า key จะเข้าที่
- วาง key ลงในช่องว่าง ตอนนี้ทุกอย่างทางซ้ายถูกจัดเรียบร้อยแล้ว
public class Sorter {
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i]; // the value to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger values right
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key; // drop key into the gap
}
}
}
English
Insertion sort: a trace
- Sort
{5, 2, 4, 1, 3}again. The bold part stays sorted as we go. - The
keyis the value we are inserting on each pass.
ไทย
Insertion sort: การ trace
- จัด
{5, 2, 4, 1, 3}อีกครั้ง ส่วน ตัวหนา จะยังคงถูกจัด mientras avanzamos keyคือค่าที่เราจะแทรกในแต่ละรอบ
start: [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2: [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4: [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3: [1, 2, 3, 4, 5]
done: [1, 2, 3, 4, 5]
English
Merge sort: trace only
- Merge sort uses recursion (lesson 15). You do not write it on the exam, but you must trace it.
- Split the array in half again and again, until each piece has one value.
- Merge pairs of pieces back together, always keeping them in order.
ไทย
Merge sort: Trace Only
- Merge sort ใช้ recursion (lesson 15). คุณ ไม่ เขียนมันในการสอบ แต่คุณต้อง trace มัน
- Split array ออกเป็นครึ่งอีกครั้งและอีกครั้ง จนกว่าแต่ละชิ้นจะมีค่าเดียว
- Merge คู่ของชิ้นส่วนกลับเข้าด้วยกัน โดยรักษาความเป็นระเบียบเสมอ
English
Merge sort: a trace
- One value is already "sorted". Merging two sorted pieces gives a bigger sorted piece.
- Selection and insertion sort are slow on big arrays (they do about n² steps).
- Merge sort is faster on big arrays (about n·log n steps). That is why it matters.
ไทย
Merge sort: A Trace
- ค่าหนึ่งถูก "เรียง" อยู่แล้ว การรวมสองส่วนที่เรียงแล้วเข้าด้วยกันจะได้ส่วนที่เรียงใหญ่ขึ้น
split: [5, 2, 4, 1]
[5, 2] [4, 1]
[5] [2] [4] [1]
merge: [2, 5] [1, 4]
merge: [1, 2, 4, 5]
- Selection และ insertion sort ช้าใน arrays ขนาดใหญ่ (ทำประมาณ n² ขั้นตอน)
- Merge sort เร็วกว่าใน arrays ขนาดใหญ่ (ประมาณ n·log n ขั้นตอน) นั่นคือเหตุผลว่ามันสำคัญ
English
Common mistakes
- Selection and insertion sort are both O(n²).
- Trace a small array by hand to check your sort.
ไทย
ข้อผิดพลาดที่พบบ่อย
- Selection and insertion sort are both O(n²).
- ทดสอบ array เล็กๆ ด้วยมือเพื่อตรวจสอบการ sort ของคุณ
English
Now you try
- Each task gives you a method skeleton with a TODO. Sort the array in place (change
aitself). - A hidden Harness sorts several arrays and checks the result.
- Press Run to compile, then Check answer.
ไทย
ลองดูเลย
- แต่ละโจทย์ให้ method skeleton พร้อม TODO. Sort array โดยตรง (แก้ไข
aเอง) - Hidden Harness จะ sort several arrays และตรวจสอบผลลัพธ์
- กด Run เพื่อคอมไพล์ แล้วกด Check answer
Explore · สำรวจ
Selection / insertion sort · Selection / Insertion sort
Sorting compares and swaps until the list is ordered. · การ Sort เปรียบเทียบและสลับจนกว่า list จะเรียงลำดับ.
Complete selectionSort(int[] a) so it sorts the array in place from small to large, using selection sort. The checker tests several arrays. · เติม selectionSort(int[] a) ให้สมบูรณ์เพื่อจัดเรียง array in place จากเล็กไปใหญ่, using selection sort. ตัวตรวจสอบทดสอบหลาย arrays.
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete insertionSort(int[] a) so it sorts the array in place from small to large, using insertion sort. The checker tests several arrays. · เติม insertionSort(int[] a) ให้สมบูรณ์เพื่อจัดเรียง array in place จากเล็กไปใหญ่, using insertion sort. ตัวตรวจสอบทดสอบหลาย arrays.
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete isSorted(int[] a) returning true if the array is in order from small to large (each item is <= the next), else false. An empty or one-item array counts as sorted. · เติม isSorted(int[] a) เพื่อกลับคืน true ถ้า array เรียงลำดับจากเล็กไปใหญ่ (แต่ละ item คือ <= Itemถัดไป), อื่นๆ กลับคืน false. Arrayว่างหรือมี(itemเดียว)นับว่าเป็น sorted.
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่