อัลกอริทึมการเรียงลำดับและการค้นหา
เราจะเริ่มวิเคราะห์อัลกอริธึมการเรียงลำดับบางอย่าง ตามชื่อที่แนะนำ เป้าหมายของพวกเขาคือการเรียงลำดับรายการภายในโครงสร้างข้อมูล
การเรียงลำดับฟอง
Bubble sort เป็นอัลกอริทึมที่ง่ายที่สุดที่เสนอในบทความนี้ การมีรายการจะเปรียบเทียบตัวเลขสองตัวที่อยู่ติดกัน และหากตัวเลขที่ใหญ่กว่าอยู่ในตำแหน่งแรก ก็จะเปลี่ยนตำแหน่งเป็นตัวเลขสองตัว มันเลื่อนดูรายการทั้งหมดด้วยวิธีนี้ เพื่อให้ได้ผลถูกต้อง การเรียงลำดับแบบฟองจะต้องดำเนินการหลายครั้งในรายการเดียวกัน ดังนั้นจึงประกอบด้วยสองรอบ:
● ภายใน ต้องใช้กี่ครั้งในการทำซ้ำอัลกอริทึมภายนอกในรายการ
● ภายนอก การเปรียบเทียบระหว่างหมายเลขที่อยู่ติดกัน
อัลกอริธึมนี้จะได้เปรียบเมื่อรายการเป็นแบบกึ่งเรียงลำดับแล้ว และแนะนำเฉพาะกับรายการขนาดเล็กเท่านั้น ถ้าขนาดถูกขยายมากเกินไป เวลาดำเนินการก็อาจเพิ่มขึ้นอย่างมากเช่นกัน
ตัวอย่างพร้อมรูปภาพ:
ในตัวอย่าง รายการแปดรายการจะถูกจัดเรียง ตามที่คุณเห็นแต่ละรายการจะถูกเปรียบเทียบกับรายการถัดไป และหากรายการถัดไปมีขนาดใหญ่กว่า ตำแหน่งจะถูกซื้อขาย
ดังที่คุณเห็นว่าผลลัพธ์สุดท้ายยังจัดเรียงไม่ครบถ้วน ดังนั้นคุณจะต้องทำการเปรียบเทียบคู่กันจนกว่ารายการทั้งหมดจะถูกจัดเรียง
การเรียงลำดับการแทรก
การเรียงลำดับการแทรกจะเริ่มต้นด้วยการเลือกสองรายการแรกในรายการ ทำการเปรียบเทียบ และดันรายการที่ใหญ่ที่สุดไปยังตำแหน่งที่ถูกต้อง จากนั้นยังเลือกองค์ประกอบที่สามเพื่อจดจำสององค์ประกอบก่อนหน้า และทำซ้ำขั้นตอนเดียวกัน ดังนั้นจึงเปลี่ยนลำดับขององค์ประกอบตามค่า
แนะนำให้ใช้อัลกอริทึมนี้กับชุดข้อมูลขนาดเล็ก ประสิทธิภาพจะลดลงมากเมื่อขนาดชุดข้อมูลเพิ่มขึ้น
ตัวอย่างพร้อมรูปภาพ:
ดังที่เห็นได้ในกรณีนี้ ไม่เพียงแต่พิจารณาสององค์ประกอบเท่านั้น แต่หลังจากสององค์ประกอบแรก การเปรียบเทียบจะขยายเป็นสามองค์ประกอบ จากนั้นจึงขยายเป็นสี่องค์ประกอบ แต่ละครั้งที่จำนวนรายการที่พิจารณาขยาย รายการจะถูกจัดเรียง
ในตัวอย่างในการเปรียบเทียบครั้งแรก ไม่มีการเปลี่ยนแปลงใดๆ เนื่องจาก 25 และ 26 อยู่ในตำแหน่งที่ถูกต้องแล้ว อย่างไรก็ตาม ในการเลือก 22 รายการจะเปลี่ยนไปเนื่องจาก 22 ถูกย้ายไปยังตำแหน่งแรกโดยพิจารณาว่าเป็นตัวเลขที่น้อยที่สุดในบรรดาตัวเลขที่เลือก
ในกรณีนี้ ไม่จำเป็นต้องรันอัลกอริธึมหลายครั้งเหมือนในกรณีของการเรียงลำดับแบบฟอง เมื่อเลือกรายการทั้งหมดแล้ว รายการจะถูกจัดเรียง
ผสานการเรียงลำดับ
ประสิทธิภาพของ Merge Sort ไม่ได้ขึ้นอยู่กับลำดับขององค์ประกอบในโครงสร้างข้อมูล แต่จะทำงานในสองขั้นตอน:
● การแยก รายการจะถูกแบ่งครึ่งและแบ่งครึ่งอีกครั้งจนกว่าจะสร้างรายการเล็กๆ ที่มีความยาว 1
● การรวม รายการความยาว 1 จะถูกนำมารวมกัน และในขณะที่รวบรวมองค์ประกอบต่างๆ จะถูกจัดเรียง
ตัวอย่างพร้อมรูปภาพ:
ดังที่คุณเห็น รายการจะถูกแบ่งครึ่งเสมอโดยสร้างรายการเล็กๆ ที่ประกอบด้วยสองซีก กระบวนการนี้ ซึ่งก็คือการแยก จะมีผลจนกว่าจะเหลือรายการเล็กๆ ที่มีความยาว 1 เมื่อเหลือเพียงรายการความยาวรายการเดียว การผสานจะเริ่มต้นขึ้นและรายการต่างๆ จะถูกนำมารวมกันโดยการเรียงลำดับรายการ
เชลล์เรียงลำดับ
รายการจะแบ่งออกเป็นรายการเล็กๆ ที่ประกอบด้วยสององค์ประกอบที่ระยะมาตรฐาน
ตัวอย่างเช่น การมีรายการองค์ประกอบ 12 รายการ ถ้าองค์ประกอบแรกอยู่ในรายการที่สองพร้อมกับองค์ประกอบที่ 4 องค์ประกอบที่สองก็จะอยู่ในรายการที่มีองค์ประกอบถัดไป ด้วยวิธีนี้ ระยะห่างขององค์ประกอบที่ประกอบกันเป็นเช่นนี้ ทั้งสองรายการไม่แตกต่างกัน
กระบวนการนี้เกิดขึ้นกับทุกรายการในรายการ
องค์ประกอบจะได้รับการพิจารณาโดยพิจารณาจากคู่ที่สร้างขึ้น
ในขั้นตอนที่สอง จะไม่มีคู่รักอีกต่อไป แต่จะมีการเปรียบเทียบทั้งสามคู่ แม้ว่าในกรณีนี้ระยะห่างในรายการของแต่ละองค์ประกอบจะต้องเท่ากันในรายการย่อยทั้งหมดที่ถูกสร้างขึ้น
สิ่งนี้จะดำเนินต่อไปจนกว่าจะเหลือเพียงรายการเดียวที่ประกอบด้วยรายการทั้งหมดในค่าเริ่มต้นแต่อยู่ในรายการที่เรียงลำดับแล้ว
ขอแนะนำให้ใช้การเรียงลำดับเชลล์ในรายการที่มีองค์ประกอบน้อยกว่าหมื่นรายการ
ตัวอย่างพร้อมรูปภาพ:
แต่ละสีแสดงถึงรายการ โดยในแต่ละสีองค์ประกอบจะอยู่ห่างจากกันเสมอ ดังที่สังเกตได้ รายการต่างๆ ภายในแต่ละรายการจะถูกจัดเรียง การเรียงลำดับจะสิ้นสุดลงเมื่อมีรายการเดียวที่มีขนาดของรายการเดิม ด้วยวิธีนี้ รายการจะถูกจัดลำดับแบบกึ่งแล้ว และเวลาในการเรียงลำดับสุดท้ายจะสั้นลงมาก
เรียงลำดับการเลือก
คล้ายกับการเรียงลำดับฟอง แต่ไม่ได้เลือกองค์ประกอบสองรายการที่อยู่ติดกัน ในการโต้ตอบครั้งแรก ระบบจะเลือกองค์ประกอบแรกและองค์ประกอบสุดท้าย เปรียบเทียบและวางองค์ประกอบที่ใหญ่ที่สุดไว้ที่ด้านบนสุดของรายการ ในการโต้ตอบครั้งที่สอง ระบบจะเลือกองค์ประกอบแรกและองค์ประกอบที่ตำแหน่งสุดท้าย จากนั้นจะทำการเปรียบเทียบและแลกเปลี่ยนอีกครั้ง
ไม่แนะนำอีกครั้งในรายการขนาดใหญ่
ตัวอย่างพร้อมรูปภาพ:
ตามตัวอย่างที่แสดง มันคล้ายกับ Bubble Sort มาก แต่องค์ประกอบที่เลือกไม่ใช่องค์ประกอบแรกและองค์ประกอบถัดไป แต่เป็นองค์ประกอบแรกและสุดท้าย — 1 ในการวนซ้ำแต่ละครั้ง
อัลกอริทึมการค้นหา
ค้นหาเชิงเส้น
โดยจะไล่ไปตามรายการตั้งแต่รายการแรกจนถึงรายการสุดท้าย เวลาดำเนินการขึ้นอยู่กับความยาวของรายการ แต่ไม่จำเป็นต้องเรียงลำดับรายการเพื่อให้ทำงานได้
การค้นหาแบบไบนารี
สำหรับการค้นหาประเภทนี้ จะต้องเรียงลำดับรายการ จากนั้นจึงแบ่งออกเป็นสองจุด จุดแรกคือองค์ประกอบแรก ในขณะที่จุดที่สองคือองค์ประกอบที่อยู่ตรงกลางรายการ เมื่อพิจารณาถึงค่าขององค์ประกอบที่หนึ่งและที่สอง สามารถยกเว้นครึ่งหนึ่งของรายการได้แล้ว ตัวอย่างเช่น หากองค์ประกอบแรกคือ 0 และองค์ประกอบที่สอง (ดังนั้นองค์ประกอบที่อยู่ตรงกลางของรายการ) คือ 10 และองค์ประกอบที่ฉันกำลังมองหาคือ 17 ฉันรู้ว่าฉันไม่สามารถพิจารณาทุกอย่างระหว่าง 0 ถึง 10 ได้เนื่องจากรายการ ได้รับคำสั่ง
ตอนนี้องค์ประกอบที่สองยังคงเหมือนเดิม 10 องค์ประกอบแรกจะกลายเป็นองค์ประกอบที่อยู่ตรงกลางของรายการใหม่ เช่น 15
อีกครั้งสามารถยกเว้นองค์ประกอบทั้งหมดตั้งแต่ 10 ถึง 15 ได้เนื่องจากฉันรู้ว่า 17 มากกว่า 15 ดังนั้นมันจะอยู่ในส่วนที่มีจำนวนมากกว่า 15 การเลือกจะดำเนินต่อไปในลักษณะนี้จนกว่าจะพบค่าที่ค้นหา
ตัวอย่างพร้อมรูปภาพ:
ในตัวอย่างนี้ รายการจะถูกจัดเรียงและเรารู้ว่าเราต้องค้นหาค่า 2 รายการที่อยู่ตรงกลางของรายการคือ 5 2 น้อยกว่า 5 ดังนั้นรายการที่คุณกำลังมองหาจะอยู่ทางด้านซ้ายของรายการ รายการดังนั้นจึงไม่รวมด้านขวา จากนั้นคุณเลือกครึ่งใหม่ของรายการที่พิจารณาซึ่งในกรณีนี้สอดคล้องกับค่าที่ค้นหา
ค้นหาโดยการแก้ไข
อีกครั้ง จะต้องเรียงลำดับรายการและจำเป็นต้องมีค่าสองค่า รายการแรกในรายการและรายการสุดท้ายในรายการ หากค่าที่ค้นหาสูงกว่าค่าขององค์ประกอบที่อยู่ตรงกลางรายการ ค่าแรกจะกลายเป็นองค์ประกอบที่อยู่ตรงกลางของรายการ
ตัวอย่างเช่น:
มีรายการตั้งแต่ 0 ถึง 10 ซึ่งฉันมองหาค่า 7
a (องค์ประกอบแรก) จะเท่ากับ 0
B (องค์ประกอบที่สอง) จะเท่ากับ 10
ครึ่งหนึ่งของรายการคือ 5
เจ็ดมีค่ามากกว่าห้า ดังนั้นองค์ประกอบ a จะกลายเป็น 5 และรายการจะกลายเป็น 5 ถึง 10 ครึ่งใหม่คือ 8 ดังนั้นองค์ประกอบ b จะกลายเป็น 8 และตอนนี้คุณมีรายการระหว่าง 5 ถึง 8 การหารนี้เกิดขึ้นจนกระทั่ง พบรายการที่คุณกำลังมองหา
ตัวอย่างพร้อมรูปภาพ:
แม้ว่าในกรณีนี้ รายการจะถูกเรียงลำดับและทราบค่าที่ต้องการค้นหา ค่ากลางจะถูกเลือก และเช่นเดียวกับในการค้นหาแบบไบนารี ส่วนของรายการที่ไม่เข้าใจค่าที่ต้องการจะถูกแยกออก เมื่อแบ่งค่าสุดท้ายแล้ว ระบบจะไม่เลือกจุดกึ่งกลาง แต่ค่าแรกและค่าสุดท้ายของรายการใหม่จะถูกเลือก หากค่าไม่ตรงกัน ค่าเหล่านั้นจะถูกแยกออก และเลือกค่าใกล้เคียงจนกว่าค่าใดค่าหนึ่งจะตรงกับค่าที่ค้นหา
