Bubble เรียงลำดับอัลกอริทึมด้วย Python โดยใช้ตัวอย่างรายการ

อะไรคือ a Bubblเรียงลำดับ?

Bubblอีเรียงลำดับ เป็นอัลกอริธึมการเรียงลำดับที่ใช้ในการเรียงลำดับรายการจากน้อยไปหามากโดยการเปรียบเทียบค่าสองค่าที่อยู่ติดกัน หากค่าแรกสูงกว่าค่าที่สอง ค่าแรกจะเข้ารับตำแหน่งค่าที่สอง ในขณะที่ค่าที่สองจะเข้ารับตำแหน่งค่าแรก หากค่าแรกต่ำกว่าค่าที่สอง จะไม่มีการแลกเปลี่ยนเกิดขึ้น

กระบวนการนี้จะถูกทำซ้ำจนกว่าจะเปรียบเทียบค่าทั้งหมดในรายการและสลับหากจำเป็น การวนซ้ำแต่ละครั้งมักเรียกว่าการส่งผ่าน จำนวนการส่งผ่านในการจัดเรียงแบบบับเบิลเท่ากับจำนวนองค์ประกอบในรายการลบหนึ่งรายการ

ในการนี​​้ Bubble การเรียงลำดับ Python เกี่ยวกับการสอน คุณจะได้เรียนรู้:

การใช้งาน Bubble อัลกอริทึมการเรียงลำดับ

เราจะแบ่งการใช้งานออกเป็นสาม (3) ขั้นตอน ได้แก่ ปัญหา วิธีแก้ไข และอัลกอริทึมที่เราสามารถใช้เพื่อเขียนโค้ดสำหรับภาษาใดก็ได้

ปัญหา

รายการสินค้าจะถูกสุ่มตามลำดับ และเราต้องการจัดเรียงสินค้าให้เป็นระเบียบ

ลองพิจารณารายการต่อไปนี้:

[21,6,9,33,3]

การแก้ไขปัญหา

วนซ้ำรายการโดยเปรียบเทียบสององค์ประกอบที่อยู่ติดกัน และสลับกันหากค่าแรกสูงกว่าค่าที่สอง

ผลลัพธ์ควรเป็นดังนี้:

[3,6,9,21,33]

ขั้นตอนวิธี

อัลกอริธึมการเรียงลำดับแบบบับเบิ้ลทำงานดังนี้

ขั้นตอน 1) รับจำนวนองค์ประกอบทั้งหมด รับจำนวนรายการทั้งหมดในรายการที่กำหนด

ขั้นตอน 2) กำหนดจำนวนรอบด้านนอก (n – 1) ที่จะทำ ความยาวของมันคือรายการลบหนึ่ง

ขั้นตอน 3) ดำเนินการส่งผ่านภายใน (n – 1) ครั้งสำหรับการส่งผ่านด้านนอก 1 รับค่าองค์ประกอบแรกและเปรียบเทียบกับค่าที่สอง หากค่าที่สองน้อยกว่าค่าแรก ให้สลับตำแหน่ง

ขั้นตอน 4) ทำซ้ำขั้นตอนที่ 3 ผ่านจนกระทั่งถึงบัตรด้านนอก (n – 1) รับองค์ประกอบถัดไปในรายการ จากนั้นทำซ้ำขั้นตอนที่ดำเนินการในขั้นตอนที่ 3 จนกว่าค่าทั้งหมดจะถูกวางไว้ในลำดับจากน้อยไปมากที่ถูกต้อง

ขั้นตอน 5) ส่งคืนผลลัพธ์เมื่อผ่านทั้งหมดเสร็จแล้ว ส่งกลับผลลัพธ์ของรายการที่เรียงลำดับ

ขั้นตอน 6) ปรับอัลกอริทึมให้เหมาะสม

หลีกเลี่ยงการผ่านภายในที่ไม่จำเป็น หากรายการหรือค่าที่อยู่ติดกันถูกเรียงลำดับแล้ว ตัวอย่างเช่น หากรายการที่ให้ไว้มีองค์ประกอบที่เรียงลำดับจากน้อยไปหามาก เราก็สามารถแยกลูปตั้งแต่เนิ่นๆ ได้

ปลดข้อจำกัด Bubble อัลกอริทึมการเรียงลำดับ

โดยค่าเริ่มต้นอัลกอริทึมสำหรับการเรียงลำดับแบบฟองสบู่ใน Python เปรียบเทียบรายการทั้งหมดในรายการโดยไม่คำนึงว่ารายการนั้นได้รับการเรียงลำดับแล้วหรือไม่ หากรายการที่กำหนดได้รับการเรียงลำดับแล้ว การเปรียบเทียบค่าทั้งหมดจะเป็นการเสียเวลาและทรัพยากรโดยเปล่าประโยชน์

การเพิ่มประสิทธิภาพการจัดเรียงแบบบับเบิลช่วยให้เราหลีกเลี่ยงการทำซ้ำที่ไม่จำเป็น และประหยัดเวลาและทรัพยากร

ตัวอย่างเช่น หากรายการแรกและรายการที่สองได้รับการจัดเรียงแล้ว ก็ไม่จำเป็นต้องวนซ้ำค่าที่เหลือ การวนซ้ำสิ้นสุดลง และเริ่มการวนซ้ำครั้งถัดไปจนกว่ากระบวนการจะเสร็จสิ้นดังแสดงด้านล่าง Bubblตัวอย่างการเรียงลำดับ

การเพิ่มประสิทธิภาพทำได้โดยใช้ขั้นตอนต่อไปนี้

ขั้นตอน 1) สร้างตัวแปรแฟล็กที่ตรวจสอบว่ามีการสลับเกิดขึ้นในลูปด้านในหรือไม่

ขั้นตอน 2) หากค่ามีการสลับตำแหน่ง ให้ดำเนินการวนซ้ำครั้งถัดไป

ขั้นตอน 3) หากผลประโยชน์ไม่ได้สลับตำแหน่ง ให้ยุติวงใน และทำต่อกับวงนอก

การเรียงลำดับแบบบับเบิลที่ได้รับการปรับปรุงจะมีประสิทธิภาพมากกว่า เนื่องจากจะดำเนินการตามขั้นตอนที่จำเป็นเท่านั้น และข้ามขั้นตอนที่ไม่จำเป็นออกไป

การแสดงภาพ

เมื่อกำหนดรายการองค์ประกอบทั้งห้า รูปภาพต่อไปนี้จะแสดงให้เห็นว่าการเรียงลำดับแบบฟองจะวนซ้ำผ่านค่าต่างๆ อย่างไรเมื่อเรียงลำดับองค์ประกอบเหล่านั้น

รูปภาพต่อไปนี้แสดงรายการที่ไม่ได้เรียงลำดับ

การทำซ้ำครั้งแรก

ขั้นตอน 1)

มีการเปรียบเทียบค่า 21 และ 6 เพื่อตรวจสอบว่าค่าใดมากกว่าค่าอื่น

21 มากกว่า 6 ดังนั้น 21 จึงเข้ารับตำแหน่งที่ถูกครอบครองโดย 6 ในขณะที่ 6 เข้ารับตำแหน่งที่ถูกครอบครองโดย 21

รายการที่แก้ไขของเราตอนนี้ดูเหมือนรายการด้านบน

ขั้นตอน 2)

มีการเปรียบเทียบค่า 21 และ 9

21 มากกว่า 9 ดังนั้นเราจึงสลับตำแหน่ง 21 และ 9

รายการใหม่อยู่ในขณะนี้ดังข้างต้น

ขั้นตอน 3)

มีการเปรียบเทียบค่า 21 และ 33 เพื่อหาค่าที่มากกว่า

ค่า 33 มากกว่า 21 ดังนั้นจึงไม่มีการสลับเกิดขึ้น

ขั้นตอน 4)

มีการเปรียบเทียบค่า 33 และ 3 เพื่อหาค่าที่มากกว่า

ค่า 33 มากกว่า 3 ดังนั้นเราจึงสลับตำแหน่งของพวกเขา

รายการที่จัดเรียงในตอนท้ายของการวนซ้ำครั้งแรกจะเหมือนกับรายการด้านบน

การทำซ้ำครั้งที่สอง

รายการใหม่หลังจากการวนซ้ำครั้งที่สองมีดังนี้

การทำซ้ำครั้งที่สาม

รายการใหม่หลังจากการวนซ้ำครั้งที่สามมีดังนี้

การทำซ้ำครั้งที่สี่

รายการใหม่หลังจากการวนซ้ำครั้งที่สี่มีดังนี้

Python ตัวอย่าง

โค้ดต่อไปนี้จะแสดงวิธีการใช้งาน Bubble เรียงลำดับอัลกอริทึมใน Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

การดำเนินการโปรแกรมเรียงลำดับฟองสบู่ข้างต้นใน Python ก่อให้เกิดผลลัพธ์ต่อไปนี้

[6, 9, 21, 3, 33]

คำอธิบายรหัส

คำอธิบายสำหรับ Python Bubble รหัสโปรแกรม Sort มีดังนี้

ที่นี่

1. กำหนดฟังก์ชัน bubbleSort ที่ยอมรับพารามิเตอร์ theSeq รหัสไม่แสดงผลอะไรเลย
2. รับค่าความยาวของอาร์เรย์และกำหนดค่าให้กับตัวแปร n รหัสไม่แสดงผลอะไรเลย
3. เริ่มต้น for loop ที่รันอัลกอริธึมการเรียงลำดับแบบฟอง (n – 1) ครั้ง นี่คือวงรอบนอก รหัสไม่แสดงผลอะไรเลย
4. กำหนดตัวแปรแฟล็กที่จะใช้เพื่อตรวจสอบว่ามีการสลับเกิดขึ้นหรือไม่ นี่คือเพื่อวัตถุประสงค์ในการเพิ่มประสิทธิภาพ รหัสไม่แสดงผลอะไรเลย
5. เริ่มลูปด้านในที่เปรียบเทียบค่าทั้งหมดในรายการตั้งแต่ค่าแรกจนถึงค่าสุดท้าย โค้ดจะไม่แสดงผลลัพธ์ใดๆ
6. ใช้คำสั่ง if เพื่อตรวจสอบว่าค่าทางด้านซ้ายมือมากกว่าค่าทางด้านขวามือหรือไม่ รหัสไม่แสดงผลอะไรเลย
7. กำหนดค่าของ theSeq[j] ให้กับตัวแปรชั่วคราว tmp หากเงื่อนไขประเมินเป็นจริง รหัสไม่แสดงผลอะไรเลย
8. ค่าของ theSeq[j + 1] ถูกกำหนดให้กับตำแหน่งของ theSeq[j] รหัสไม่แสดงผลอะไรเลย
9. ค่าของตัวแปร tmp ถูกกำหนดให้กับตำแหน่ง theSeq[j + 1] รหัสไม่แสดงผลอะไรเลย
10. ตัวแปรแฟล็กถูกกำหนดให้เป็นค่า 1 เพื่อระบุว่ามีการสลับเกิดขึ้น รหัสไม่แสดงผลอะไรเลย
11. ใช้คำสั่ง if เพื่อตรวจสอบว่าค่าของแฟล็กตัวแปรเป็น 0 หรือไม่ โค้ดจะไม่แสดงผลลัพธ์ใดๆ
12. หากค่าเป็น 0 เราจะเรียกคำสั่งแบ่งที่ออกจากวงใน
13. ส่งกลับค่าของ theSeq หลังจากที่เรียงลำดับแล้ว รหัสจะแสดงรายการที่เรียงลำดับ
14. กำหนดตัวแปร el ที่มีรายการตัวเลขสุ่ม โค้ดไม่แสดงผลลัพธ์ใดๆ
15. กำหนดค่าของฟังก์ชัน bubbleSort ให้กับผลลัพธ์ของตัวแปร
16. พิมพ์ค่าของผลลัพธ์ของตัวแปร

Bubblข้อดีการเรียงลำดับ

ต่อไปนี้เป็นข้อดีบางประการของอัลกอริธึมการเรียงลำดับแบบฟองสบู่

• มันเป็นเรื่องง่ายที่จะเข้าใจ
• จะทำงานได้ดีมากเมื่อรายการถูกจัดเรียงแล้วหรือเกือบจะถูกจัดเรียงแล้ว
• ไม่จำเป็นต้องมีหน่วยความจำที่กว้างขวาง
• ง่ายต่อการเขียนโค้ดสำหรับอัลกอริทึม
• ความต้องการพื้นที่มีน้อยมากเมื่อเทียบกับอัลกอริธึมการเรียงลำดับอื่น

Bubblข้อเสียประเภท e

ต่อไปนี้เป็นข้อเสียบางประการของอัลกอริธึมการเรียงลำดับแบบฟองสบู่

• มันทำงานได้ไม่ดีเมื่อเรียงลำดับรายการขนาดใหญ่ ใช้เวลาและทรัพยากรมากเกินไป
• ส่วนใหญ่จะใช้เพื่อวัตถุประสงค์ทางวิชาการไม่ใช่การใช้งานจริง
• จำนวนขั้นตอนที่จำเป็นในการเรียงลำดับรายการอยู่ในลำดับที่ n²

การวิเคราะห์ความซับซ้อนของ Bubblอีเรียงลำดับ

ประเภทความซับซ้อนมีอยู่ 3 ประเภท:

1) การเรียงลำดับความซับซ้อน

ความซับซ้อนของการเรียงลำดับใช้เพื่อแสดงจำนวนเวลาและพื้นที่ในการดำเนินการที่ใช้ในการเรียงลำดับรายการ การเรียงลำดับแบบฟองสบู่จะทำซ้ำ (n – 1) ครั้งเพื่อเรียงลำดับรายการ โดยที่ n คือจำนวนองค์ประกอบทั้งหมดในรายการ

2) ความซับซ้อนของเวลา

ความซับซ้อนของเวลาในการเรียงลำดับแบบฟองสบู่คือ O(n²)

ความซับซ้อนของเวลาสามารถแบ่งประเภทได้ดังนี้:

• กรณีที่เลวร้ายที่สุด – นี่คือรายการที่ให้ไว้โดยเรียงลำดับจากมากไปน้อย อัลกอริธึมดำเนินการตามจำนวนสูงสุดของการประมวลผลซึ่งแสดงเป็น [Big-O] O(n²)
• กรณีที่ดีที่สุด – สิ่งนี้เกิดขึ้นเมื่อรายการที่ระบุได้รับการเรียงลำดับแล้ว อัลกอริทึมจะดำเนินการตามจำนวนขั้นต่ำของการดำเนินการซึ่งแสดงเป็น [Big-Omega] Ω(n)
• กรณีเฉลี่ย – สิ่งนี้เกิดขึ้นเมื่อรายการอยู่ในลำดับแบบสุ่ม ความซับซ้อนโดยเฉลี่ยจะแสดงเป็น [Big-theta] ⊝(n²)

3) ความซับซ้อนของพื้นที่

ความซับซ้อนของพื้นที่วัดปริมาณพื้นที่เพิ่มเติมที่จำเป็นสำหรับการเรียงลำดับรายการ การเรียงลำดับแบบฟองสบู่ต้องการพื้นที่เพิ่มเติมเพียงหนึ่ง (1) พื้นที่สำหรับตัวแปรชั่วคราวที่ใช้ในการสลับค่า ดังนั้นจึงมีความซับซ้อนของพื้นที่เท่ากับ O (1)

สรุป

• อัลกอริทึมการจัดเรียงแบบบับเบิ้ลทำงานโดยการเปรียบเทียบค่าสองค่าที่อยู่ติดกัน และสลับค่าเหล่านั้นหากค่าทางด้านซ้ายน้อยกว่าค่าทางด้านขวา
• การนำอัลกอริธึมการเรียงลำดับแบบฟองสบู่ไปใช้ค่อนข้างตรงไปตรงมาด้วย Python- สิ่งที่คุณต้องใช้คือคำสั่ง for loops และ if
• ปัญหาที่อัลกอริธึมการเรียงลำดับแบบฟองแก้ไขคือการสุ่มรายการของรายการและเปลี่ยนให้เป็นรายการที่เรียงลำดับ
• อัลกอริธึมการเรียงลำดับแบบบับเบิ้ลในโครงสร้างข้อมูลจะทำงานได้ดีที่สุดเมื่อมีการจัดเรียงรายการแล้ว เนื่องจากดำเนินการวนซ้ำในจำนวนน้อยที่สุด
• อัลกอริทึมการเรียงลำดับแบบฟองทำงานได้ไม่ดีเมื่อรายการอยู่ในลำดับย้อนกลับ
• การเรียงลำดับแบบบับเบลอร์มีความซับซ้อนของเวลาเท่ากับ O (n²) และความซับซ้อนของพื้นที่ O (1)
• อัลกอริธึมการเรียงลำดับบับเบิ้ลเหมาะที่สุดสำหรับวัตถุประสงค์ทางวิชาการ ไม่ใช่การใช้งานในโลกแห่งความเป็นจริง
• การจัดเรียงแบบบับเบิ้ลที่ได้รับการปรับปรุงจะทำให้อัลกอริทึมมีประสิทธิภาพมากขึ้น โดยการข้ามการวนซ้ำที่ไม่จำเป็นเมื่อตรวจสอบค่าที่ได้รับการจัดเรียงแล้ว