bubble sort
วางเวลาสั้นที่สุดไว้ก่อน
- เวลาแข่งสามเวลาอยู่ใน Array:
14,9,11ค่าที่น้อยที่สุดควรมาก่อน - เปรียบเทียบคู่เพื่อนบ้านแต่ละคู่ เมื่อค่าทางซ้ายมากกว่า ให้สลับที่กัน
- การเปรียบเทียบครั้งเดียวนี้ไม่จบรายการ คู่ถัดไปจะถูกเปรียบเทียบหลังจากนั้น
DECLARE Score : ARRAY[1:3] OF INTEGER
DECLARE J, Temp : INTEGER
Score[1] ← 14
Score[2] ← 9
Score[3] ← 11
FOR J ← 1 TO 2
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
ทำซ้ำรอบ
- การวนรอบภายในหนึ่งรอบจะดันค่าที่ใหญ่ที่สุดที่พบไปทางท้ายรายการ
- ลูปภายนอกทำซ้ำการ pass สำหรับสี่ค่า สามรอบก็พอ
- นี่คือ Bubble sort ของ syllabus Linear search ที่คุณเขียนไว้ก่อนหน้านี้แค่ดู แต่ Sort จัดเรียงใหม่
DECLARE Score : ARRAY[1:4] OF INTEGER
DECLARE I, J, Temp : INTEGER
Score[1] ← 4
Score[2] ← 1
Score[3] ← 3
Score[4] ← 2
FOR I ← 1 TO 3
FOR J ← 1 TO 3
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
NEXT I
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
OUTPUT Score[4]
ระวัง
- สลับกับตัวแปร
TempScore[J] ← Score[J + 1]เพียงอย่างเดียวลบค่าทางซ้ายออก NEXTภายในตั้งชื่อJNEXTนอกตั้งชื่อI
หยุดเมื่อไม่มีสลับค่า
- เวอร์ชันที่แก้ไขแล้วจะวนทุกรอบเสมอ แม้รายการจะถูกเรียงลำดับไว้ล่วงหน้า
- ตัวบ่งชี้
BOOLEANที่ตั้งชื่อSwapจำไว้ว่ามีการสลับค่าในรอบนั้นหรือไม่ การวนรอบที่ไม่มีการสลับหมายความว่ารายการถูกเรียงลำดับแล้ว ลูปจึงหยุด - หลังแต่ละรอบ ค่าที่เหลือมากที่สุดจะถูกวางตำแหน่งไว้แล้ว ทำให้
Lastลดลงหนึ่ง
DECLARE Score : ARRAY[1:5] OF INTEGER
DECLARE J, Last, Temp : INTEGER
DECLARE Swap : BOOLEAN
Score[1] ← 2
Score[2] ← 1
Score[3] ← 3
Score[4] ← 4
Score[5] ← 5
Last ← 4
REPEAT
Swap ← FALSE
FOR J ← 1 TO Last
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
Swap ← TRUE
ENDIF
NEXT J
Last ← Last - 1
UNTIL NOT Swap OR Last = 0
FOR J ← 1 TO 5
OUTPUT Score[J]
NEXT J
ในที่นี้ รอบแรกสลับ 2 กับ 1 และรอบที่สองไม่มีการสลับเลย จึงหยุดการเรียงลำดับหลังจากสองรอบแทนที่จะสี่รอบ
ข้อผิดพลาดที่พบบ่อย
- การทดสอบคือ "ซ้ายมากกว่า" ดังนั้นค่าที่น้อยกว่าจะย้ายไปทางซ้าย ทิศทางตรงกันข้ามจัดเรียงตามลำดับย้อนกลับ
- Arrays ใน Course นี้เริ่มนับที่ 1 คู่สุดท้ายคือเซลล์ก่อนท้ายและเซลล์สุดท้าย
- การเข้าถึง
FOR J ← 1 TO 4ในอาร์เรย์ขนาด 4 จะอ่านค่าScore[5]ซึ่งไม่มีอยู่จริง ลูปด้านในจะหยุดก่อนถึงจุดสุดท้ายหนึ่งตำแหน่ง - ตั้งค่า
Swap ← FALSEเพียงครั้งเดียว ก่อนเริ่มREPEATต้องรีเซ็ตใหม่เมื่อเริ่มต้นทุกรอบ
ลองดูเลย
- งานแรกคือการวนรอบหนึ่งรอบ งานที่สองคือการเรียงลำดับทั้งหมด งานที่สามคืออ่านค่าห้าตัวและเรียงจากมากไปน้อยโดยใช้ตัวบ่งชี้
Swapแสดงผลแต่ละค่าในบรรทัดใหม่ - กด Check answer เพื่อทดสอบ
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
อาร์เรย์ Score เก็บค่า 14, 9, 11. ทำ หนึ่ง รอบเพื่อสลับเพื่อนบ้านเมื่อค่าทางซ้ายมากกว่า. แสดงผลสามค่า, อย่างละบรรทัด (9, แล้ว 11, แล้ว 14).
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
The array Score มีไว้ 4, 1, 3, 2. Bubble-sort it into ascending order and output the four values, one per line.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 3/5 · 200 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
อ่านจำนวนเต็มห้าจำนวนลงใน Score : ARRAY[1:5] OF INTEGER. เรียงลำดับด้วย Bubble-sort เป็น ลำดับลดลง, ใช้ flag BOOLEAN Swap เพื่อหยุดเมื่อรอบใดไม่มีการสลับ Output ค่าทั้งห้า, ตัวต่อตัวบนบรรทัดเดียว
คลิก Run เพื่อดูผลลัพธ์ที่นี่