อัลกอริทึมคือชุดของกฎที่กำหนดไว้อย่างดีซึ่งใช้ในการแก้ไขปัญหาในขั้นตอนจำนวนจำกัด พูดง่ายๆ ก็คือเป็นกระบวนการของการแก้ปัญหาด้วยคอมพิวเตอร์ ในกระบวนการนี้ ไม่ว่าคุณจะกำลังสร้างแนวคิดในการแก้ปัญหาหรือเขียนโปรแกรม คุณกำลังนำอัลกอริธึมบางอย่างไปใช้ แบบแรกคืออัลกอริทึมที่ดำเนินการโดยการใช้เหตุผล และแบบหลังคืออัลกอริทึมที่ดำเนินการโดยการดำเนินการ
อัลกอริธึมควรมีลักษณะสำคัญห้าประการดังต่อไปนี้:
1. ความจำกัด: อัลกอริธึมต้องแน่ใจว่าจะสิ้นสุดหลังจากดำเนินการตามจำนวนที่จำกัด
2. ความแน่นอน: แต่ละขั้นตอนของอัลกอริทึมจะต้องมีการกำหนดไว้อย่างชัดเจน
3. อินพุต: อัลกอริธึมมีอินพุต 0 หรือมากกว่าเพื่ออธิบายสถานการณ์เริ่มต้นของตัวถูกดำเนินการ
4. เอาท์พุต: อัลกอริธึมมีเอาท์พุตอย่างน้อยหนึ่งเอาท์พุตเพื่อสะท้อนผลลัพธ์ของการประมวลผลข้อมูลอินพุต อัลกอริธึมที่ไม่มีเอาต์พุตจะไม่มีความหมาย
5. ความเป็นไปได้: โดยหลักการแล้ว อัลกอริธึมสามารถทำงานได้อย่างแม่นยำ และสามารถทำได้โดยใช้ปากกาและกระดาษเพื่อดำเนินการในจำนวนที่จำกัด
การเรียงลำดับแบบผสาน (MERGE SORT) เป็นอีกวิธีหนึ่งในการเรียงลำดับที่แตกต่างกัน ความหมายของการผสานคือการรวมลำดับข้อมูลที่เรียงลำดับตั้งแต่สองลำดับขึ้นไปเข้าในลำดับข้อมูลที่เรียงลำดับใหม่ ดังนั้นจึงเรียกว่าอัลกอริธึมการผสาน แนวคิดพื้นฐานของมันคือสมมติว่าอาร์เรย์ A มีองค์ประกอบ N จากนั้นอาร์เรย์ A ถือได้ว่าประกอบด้วยลำดับย่อยที่มีลำดับ N แต่ละลำดับย่อยมีความยาว 1 จากนั้นจึงรวมสองคูณสองเพื่อให้ได้ N/2 ลำดับย่อยลำดับของ จากนั้นจึงรวมความยาว 2 หรือ 1 ทีละสอง และทำซ้ำจนกระทั่งได้ลำดับข้อมูลที่มีความยาว N การเรียงลำดับนี้เรียกว่าการเรียงลำดับแบบผสาน 2 ทาง
ตัวอย่างเช่น อาร์เรย์ A มีข้อมูล 7 รายการ คือ 49 38 65 97 76 13 27 จากนั้นขั้นตอนการดำเนินการโดยใช้อัลกอริธึมการเรียงลำดับแบบผสานจะแสดงในรูปที่ 7:
ค่าเริ่มต้น[49][38][65][97][76][13][27]
เห็นว่าประกอบด้วย 7 ลำดับย่อยของความยาว 1. หลังจากการควบรวมครั้งแรก [38 49] [65 97] [13 76] [27]
เห็นประกอบด้วย 4 ลำดับย่อยความยาว 1 หรือ 2 หลังจากการควบรวมกิจการครั้งที่สอง [38 49 65 97] [13 27 76]
เห็นประกอบด้วย 2 ลำดับย่อยความยาว 4 หรือ 3 หลังจากการควบรวมครั้งที่สาม [13 27 38 49 65 76 97]
รูปที่ 6 แผนภาพกระบวนการอัลกอริทึมการเรียงลำดับ การดำเนินการหลักของอัลกอริธึมการผสานคือการรวมลำดับการเรียงลำดับสองลำดับที่อยู่ติดกันในอาร์เรย์หนึ่งมิติให้เป็นลำดับเดียว อัลกอริธึมการรวมสามารถนำไปใช้ได้โดยใช้อัลกอริธึมแบบเรียกซ้ำซึ่งมีรูปแบบค่อนข้างง่าย แต่ใช้งานได้จริงไม่ดี
จำนวนการผสานในอัลกอริทึมการผสานเป็นปริมาณที่สำคัญมาก ตามการคำนวณ เมื่อมีองค์ประกอบ 3 ถึง 4 รายการในอาร์เรย์ จำนวนการผสานคือ 2 เมื่อมีองค์ประกอบ 5 ถึง 8 รายการ จำนวนการผสานคือ 3 และเมื่อมี 9 ถึง เมื่อมี 16 องค์ประกอบ จำนวนการรวมจะเป็น 4 ตามกฎนี้ เมื่อมีลำดับย่อย N ก็สรุปได้ว่าจำนวนการรวมคือ
X (2>=N ซึ่งเป็น X ที่เล็กที่สุดที่ตรงตามเงื่อนไขย่อย)
คำอธิบายอัลกอริทึมบับเบิ้ล:
ก่อนที่จะอธิบายอัลกอริธึมการเรียงลำดับแบบบับเบิ้ล เรามาแนะนำอัลกอริธึมที่ใส่จำนวนมากที่สุดจาก 10 จำนวน (ในอาร์เรย์ A) ไว้ที่ตำแหน่งสุดท้ายก่อน อัลกอริทึมอธิบายไว้ดังนี้:
(1) จากอาร์เรย์ A[1] ถึง A[10] ให้เปรียบเทียบตัวเลขที่อยู่ติดกันสองตัวเป็นคู่ นั่นคือ A[1] จะถูกเปรียบเทียบกับ A[2] และหลังการเปรียบเทียบ A[2] จะถูกเปรียบเทียบกับ A[3]...และสุดท้าย A[9] จะถูกเปรียบเทียบกับ A[10]
(2) ในระหว่างการเปรียบเทียบแต่ละครั้ง หากหมายเลขก่อนหน้ามากกว่าหมายเลขหลัง ทั้งสองหมายเลขจะถูกสลับ กล่าวคือ หมายเลขที่มากกว่าจะถูกย้ายไปด้านหลัง และหมายเลขที่น้อยกว่าจะถูกย้ายไปด้านหน้า ตัวอย่างเช่น ในการเปรียบเทียบครั้งแรก ถ้า A[1] มากกว่า A[2] ค่าของ A[1] และ A[2] จะถูกสับเปลี่ยนกัน รูปด้านล่างใช้ข้อมูล 6 รายการเพื่อแสดงอัลกอริทึมข้างต้น
สมมติว่าข้อมูลทั้ง 6 รายการคือ A[]=5 7 4 3 8 6
ก[1] ก[2] ก[3] ก[4] ก[5] ก[6]
5 7 4 3 8 6 ครั้งแรก A[1]=5 และ A[2]=7 ถูกเปรียบเทียบ 7>5 ไม่มีการดำเนินการสลับ
5 7 4 3 8 6 ครั้งที่สอง A[2]=7 และ A[3]=4 จะถูกเปรียบเทียบ 4<7 สลับ
จากนั้นข้อมูลหลังจากการเปรียบเทียบครั้งที่สองคือ 5 4 7 3 8 6
5 4 7 3 8 6 ครั้งที่สาม A[3]=7 และ A[4]=3 เปรียบเทียบกัน 3<7 สลับกัน
จากนั้นข้อมูลหลังจากการเปรียบเทียบครั้งที่สามคือ 5 4 3 7 8 6
5 4 3 7 8 6 ครั้งที่สี่ A[4]=7 และ A[5]=8 ถูกเปรียบเทียบ 8>7 ไม่มีการดำเนินการสลับ
5 4 3 7 8 6 ครั้งที่ห้า A[6]=6 และ A[5]=8 เปรียบเทียบกัน 6<8 สลับ
แล้วผลประการที่ห้าและสุดท้ายก็คือ
5 4 3 7 6 8
************************************************** * *****
คำอธิบายของอัลกอริทึมการเรียงลำดับการเลือก:
ก่อนที่จะแนะนำวิธีการเรียงลำดับแบบเลือก เรามาแนะนำอัลกอริทึมที่วางจำนวนที่น้อยที่สุดไว้ในตำแหน่งแรกก่อน แน่นอนว่า คุณยังสามารถใช้วิธีการเรียงลำดับแบบฟองที่กล่าวถึงข้างต้นได้ ตอนนี้เราใช้อัลกอริทึมใหม่: อุดมการณ์ที่เป็นแนวทางของมัน ฉันไม่ได้อยู่ใน รีบเปลี่ยนตำแหน่งในตอนแรกแต่เริ่มด้วย A[1] เริ่มตรวจสอบทีละตัว หากต้องการดูว่าตัวเลขใดมีค่าน้อยที่สุด ให้จดตำแหน่ง P ของตัวเลขไว้ หลังจากการสแกนเสร็จสิ้น ให้สลับ A[P] และ A[1] [1] ถึง A[ 10] ถูกย้ายไปยังตำแหน่งด้านหน้า ขั้นตอนของอัลกอริทึมมีดังนี้:
1) ขั้นแรก สมมติว่าตัวเลขใน A[1] มีค่าน้อยที่สุด และสังเกตตำแหน่ง P=1 ในขณะนี้
2) เปรียบเทียบ A[P] และ A[I] ตามลำดับ (I เปลี่ยนจาก 2 เป็น 10) ในระหว่างการเปรียบเทียบแต่ละครั้ง ถ้าตัวเลขใน A[I] น้อยกว่าตัวเลขใน A[P] แล้ว I ค่า ถูกกำหนดให้กับ P เพื่อให้ P ชี้ไปที่ตำแหน่งของตัวเลขที่น้อยที่สุดที่สแกนในปัจจุบันเสมอ กล่าวคือ A[P] จะเท่ากับจำนวนที่น้อยที่สุดของตัวเลขที่สแกนทั้งหมดเสมอ หลังจากเปรียบเทียบทีละตัวแล้ว P จะชี้ไปยังตำแหน่งของตัวเลขที่น้อยที่สุดในบรรดาตัวเลข 10 ตัว นั่นคือ A[P] เป็นตัวเลขที่เล็กที่สุดในบรรดาตัวเลข 10 ตัว
3) กลับตัวเลขของ A[P] และ A[1] จากนั้นจำนวนที่น้อยที่สุดจะอยู่ใน A[1] นั่นคือที่ด้านหน้า
หากคุณทำซ้ำอัลกอริธึมนี้ แต่ทุกครั้งที่ทำซ้ำ ช่วงของอนุกรมที่จะเปรียบเทียบจะถูกย้ายไปข้างหลังหนึ่งตำแหน่ง นั่นคือในการเปรียบเทียบครั้งที่สอง ช่วงคือจากหมายเลขที่ 2 ถึงหมายเลข N จำนวนที่น้อยที่สุดจากจุดเริ่มต้นถึงหมายเลข N อยู่ใน A [2] สำเร็จ ครั้งที่สามคือการหาตัวเลขที่น้อยที่สุดจากเลขตัวที่ 3 ไปเป็นเลข N แล้วจึงสลับ A[P] และ A[3]... หลังจากทำขั้นตอนนี้ซ้ำ N-1 ครั้ง เพียงจัดเรียง ตัวเลข N ในอาร์เรย์ A จากเล็กไปใหญ่ วิธีการเรียงลำดับนี้คือการเรียงลำดับแบบเลือก
************************************************** * ***************
คำอธิบายอัลกอริทึมการเรียงลำดับการแทรก:
เมื่อเรียนรู้สองวิธีข้างต้น คุณจะเข้าใจแนวคิดพื้นฐานของการเรียงลำดับได้ และคุณยังสามารถจัดเรียงอาร์เรย์ที่ไม่เรียงลำดับจากมากไปน้อย (ลำดับจากมากไปหาน้อย) หรือเล็กไปใหญ่ (เรียงลำดับจากน้อยไปหามาก) ตอนนี้สมมติว่ามีลำดับข้อมูลที่เรียงลำดับแล้ว และจำเป็นต้องแทรกตัวเลขลงในลำดับข้อมูลที่จัดเรียงไว้แล้ว แต่ลำดับข้อมูลยังคงต้องเรียงลำดับหลังจากการแทรก ในเวลานี้ วิธีการเรียงลำดับใหม่จะเป็นเช่นนั้น นำมาใช้ - วิธีการเรียงลำดับการแทรก การดำเนินการพื้นฐานของการเรียงลำดับการแทรกคือการแทรกข้อมูลลงในข้อมูลที่เรียงลำดับซึ่งได้รับการเรียงลำดับ เพื่อให้ได้ข้อมูลลำดับใหม่ที่มีตัวเลขบวกหนึ่ง
คำถาม: มีข้อมูล N ชิ้นในอาร์เรย์ A โดยจัดเรียงตามลำดับจากน้อยไปหามาก ป้อนตัวเลข X และแทรกค่า X ลงในอาร์เรย์ A เพื่อให้อาร์เรย์ A ที่แทรกยังคงจัดเรียงจากเล็กไปใหญ่ .
อัลกอริทึมในการแก้ปัญหานี้คือ:
1) หาตำแหน่งที่ควรแทรก X โดยเปรียบเทียบขนาดว่าควรวางไว้ที่ตำแหน่ง I หรือไม่
2) ย้ายองค์ประกอบอาร์เรย์ทั้งหมดโดยเริ่มจาก I (รวมถึง I) ถอยหลังหนึ่งตำแหน่ง นั่นคือ A[I+1]:=A[I];
การเรียงลำดับอย่างรวดเร็วเป็นการปรับปรุงการเรียงลำดับแบบฟอง แนวคิดพื้นฐานคือการแบ่งข้อมูลที่จะจัดเรียงออกเป็นสองส่วนแยกกันผ่านการเรียงลำดับทางเดียว ข้อมูลทั้งหมดในส่วนหนึ่งมีขนาดเล็กกว่าข้อมูลทั้งหมดในอีกส่วนหนึ่ง จากนั้นข้อมูลทั้งสองส่วนจะถูกจัดเรียงตามลำดับ เพื่อการเรียงลำดับอย่างรวดเร็ว กระบวนการเรียงลำดับทั้งหมดสามารถดำเนินการซ้ำได้ เพื่อให้ข้อมูลทั้งหมดกลายเป็นลำดับตามลำดับ
สมมติว่าอาร์เรย์ที่จะเรียงลำดับคือ A[1]...A[N] อันดับแรก สุ่มเลือกข้อมูล (โดยปกติจะเป็นข้อมูลแรก) เป็นข้อมูลหลัก จากนั้นจึงใส่ตัวเลขทั้งหมดที่มากกว่านั้นไว้ข้างหน้า และตัวเลขทั้งหมดที่มากกว่านั้น ตัวเลขจำนวนมากจะถูกวางไว้ด้านหลัง กระบวนการนี้เรียกว่าการเรียงลำดับอย่างรวดเร็ว อัลกอริทึมสำหรับการเรียงลำดับอย่างรวดเร็วคือ:
1) ตั้งค่าตัวแปรสองตัว I และ J เมื่อเริ่มการเรียงลำดับ I:=1, J:=N;
2) ใช้องค์ประกอบอาร์เรย์แรกเป็นข้อมูลสำคัญและกำหนดให้กับ X นั่นคือ X:=A[1];
3) ค้นหาไปข้างหน้าจาก J นั่นคือค้นหาไปข้างหน้าจากด้านหลัง (J:=J-1) หาค่าแรกที่น้อยกว่า X แล้วแลกเปลี่ยนทั้งสอง
4) ค้นหาย้อนหลังจาก I นั่นคือค้นหาจากด้านหน้าไปด้านหลัง (I:=I+1) ค้นหาค่าแรกที่มากกว่า X และแลกเปลี่ยนทั้งสอง
5) ทำซ้ำขั้นตอนที่ 3 และ 4 จนกระทั่ง I=J;
ตัวอย่างเช่น: ค่าของอาร์เรย์ A ที่จะเรียงลำดับคือ: (ข้อมูลคีย์เริ่มต้น X:=49)
ก[1] ก[2] ก[3] ก[4] ก[5] ก[6] ก[7]:
49 38 65 97 76 13 27
หลังการแลกเปลี่ยนครั้งแรก: 27 38 65 97 76 13 49
(หลังจากค้นหาจากด้านหลังตามขั้นตอนที่สามของอัลกอริทึมสำหรับการแลกเปลี่ยนครั้งที่สอง: 27 38 49 97 76 13 65
(ทำตามขั้นตอนที่สี่ของอัลกอริทึมแล้วเริ่มจากด้านหน้าเพื่อค้นหาค่า >
หลังการแลกเปลี่ยนครั้งที่สาม: 27 38 13 97 76 49 65
(ตามขั้นตอนที่ห้าของอัลกอริทึม ขั้นตอนที่สามของอัลกอริทึมจะถูกดำเนินการอีกครั้งจากจุดสิ้นสุดเพื่อค้นหาการแลกเปลี่ยนที่สี่: 27 38 13 49 76 97 65
(ทำตามขั้นตอนที่สี่ของอัลกอริธึมและเริ่มจากด้านหน้าเพื่อค้นหาค่าที่มากกว่า X, 97>49 แลกเปลี่ยนทั้งสอง ณ ตอนนี้ J:=4)
ขณะนี้เมื่อดำเนินการขั้นตอนที่ 3 พบว่า I=J จึงสิ้นสุดการเรียงลำดับแบบด่วน ผลลัพธ์หลังการเรียงลำดับแบบด่วนคือ 27 38 13 49 76 97 65 นั่นคือตัวเลขทั้งหมดที่มากกว่า 49 อยู่ใน 49 ดังนั้นตัวเลขที่น้อยกว่า 49 ทั้งหมดอยู่หน้า 49
การเรียงลำดับอย่างรวดเร็วคือการเรียกกระบวนการนี้ซ้ำ โดยแบ่งลำดับข้อมูลด้วย 49 เป็นจุดกึ่งกลาง ดำเนินการเรียงลำดับอย่างรวดเร็วที่คล้ายกันที่ส่วนหน้าและส่วนหลังตามลำดับ ซึ่งจะทำให้การเรียงลำดับอย่างรวดเร็วของลำดับข้อมูลทั้งหมดเสร็จสมบูรณ์ และสุดท้ายก็เปลี่ยนลำดับข้อมูล ให้เป็นลำดับตามแนวคิดนี้ กระบวนการทั้งหมดของการเรียงลำดับอาร์เรย์ A ข้างต้นอย่างรวดเร็วจะแสดงในรูปที่ 6:
สถานะเริ่มต้น {49 38 65 97 76 13 27}
หลังจากการเรียงลำดับอย่างรวดเร็ว จะแบ่งออกเป็น {27 38 13} 49 {76 97 65}
จัดเรียงส่วนหน้าและส่วนหลังอย่างรวดเร็วตามลำดับ {13} 27 {38}
ปลาย ปลาย {49 65} 76 {97} 49 {65} ปลาย ปลาย
************************************************** * ***************************
รูปที่ 6 คำอธิบายอัลกอริทึมของการเรียงลำดับอย่างรวดเร็วตลอดกระบวนการเรียงลำดับอย่างรวดเร็ว
1) สมมติว่าหมายเลข N (สมมติว่า N=10) ถูกเก็บไว้ในอาร์เรย์ S
2) ใน S[1. - ใช้องค์ประกอบใดๆ ใน N] เป็นพื้นฐานในการเปรียบเทียบ เช่น ใช้ T=S[1] จุดประสงค์เบื้องต้นคือเพื่อกำหนดตำแหน่ง K โดยที่ T ควรอยู่ในผลลัพธ์การเรียงลำดับ ตำแหน่งของ K คือ: S[1] . - K-1]<=S[K]<=S[K+1..N] นั่นคือ ตัวเลขก่อน S[K] จะน้อยกว่า S[K] ทั้งหมด และตัวเลขหลัง S[K] คือ ใหญ่กว่า S[ K];
3) การใช้แนวคิดแบ่งแยกแล้วพิชิต (นั่นคือ กลยุทธ์การทำให้ใหญ่และเล็กเล็ก) สามารถปรับปรุง S[1 ต่อไปได้ - K-1] และ S[K+1. - N] จากนั้นข้อมูลทั้งสองชุดจะถูกจัดเรียงอย่างรวดเร็วจนกว่าจะมีเพียงข้อมูลเดียวในออบเจ็กต์การจัดกลุ่ม
หากข้อมูลเฉพาะเป็นดังนี้ กระบวนการเรียงลำดับด่วนขั้นตอนแรกคือ:
ตัวห้อยอาร์เรย์: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
ฉัน
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53