อัลกอริทึมการเรียงลำดับแบบฟองคืออะไรและทำงานอย่างไร (พร้อมตัวอย่าง)

© Oselote/Shutterstock.com

อัลกอริทึมการเรียงลำดับแบบฟองเป็นตัวอย่างของอัลกอริทึมการเรียงลำดับอย่างง่าย อัลกอริทึมประเภทนี้จะจัดเรียงอักขระ สตริง หรือตัวเลขตามลำดับที่กำหนดโดยปัญหาที่คุณกำลังแก้ไขด้วยโค้ดของคุณ

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

ถ้า คุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับอัลกอริทึมการเรียงลำดับฟองและวิธีการทำงาน คุณมาถูกที่แล้ว บทความในวันนี้จะแจกแจงวิธีการทำงานของอัลกอริทึมการเรียงลำดับแบบฟองและแสดงวิธีการใช้งาน มาเริ่มกันเลย!

อัลกอริทึมการเรียงลำดับแบบฟองคืออะไร?

อัลกอริทึมการเรียงลำดับช่วยให้คุณมีวิธีในการนำเสนอข้อมูลอย่างมีเหตุผลเมื่อคุณรันโค้ด เมื่อคุณเรียนรู้การเขียนโปรแกรม Bubble sort เป็นหนึ่งในอัลกอริทึมแรกๆ ที่คุณจะได้เรียนรู้ เพราะมันช่วยให้คุณเห็นภาพว่าอัลกอริทึมการเรียงลำดับทำงานอย่างไรในระดับพื้นฐาน

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

อัลกอริทึม

ก่อนที่เราจะสำรวจวิธีสร้างการเรียงลำดับแบบฟอง ในโค้ดของคุณ มาดูวิธีการทำงานทีละขั้นตอน:

อันดับแรก เราจะระบุคอลเล็กชันของข้อมูลที่ต้องมีการจัดเรียง นี่อาจเป็นชุดของตัวเลข คำ หรือตัวอักษรที่คุณต้องการจัดเรียงด้วยวิธีใดวิธีหนึ่ง ฟังก์ชันทั่วไปอย่างหนึ่งของการเรียงลำดับแบบฟองคือการรับรายการตัวเลขและเรียงลำดับตามค่าของตัวเลข จากต่ำสุดไปสูงสุดหรือสูงสุดไปต่ำสุด อัลกอริทึมเริ่มต้นที่รายการแรกในรายการ ซึ่งจะเป็นข้อมูลที่ดัชนี 0 โดยจะเปรียบเทียบข้อมูลนั้นกับข้อมูลที่ดัชนี 1 เพื่อพิจารณาว่าจำเป็นต้องมีสวิตช์หรือไม่ หากสวิตช์ทำ เรามีแฟล็กที่เราตั้งไว้ซึ่งช่วยให้เราออกจากอัลกอริทึมเพื่อให้มีประสิทธิภาพมากขึ้น ถัดไป จะเปรียบเทียบ ดัชนี 1 ถึงดัชนี 2 และดำเนินต่อไปตามรายการจนกระทั่งถึงจุดสิ้นสุด เมื่ออัลกอริทึมผ่านไปแล้วครั้งหนึ่ง มันต้องผ่านกระบวนการอีกครั้ง เพราะยังไม่เสร็จสิ้นจนกว่าจะไม่ต้องทำการสวิตช์ โดยทั่วไปจะทำได้สำเร็จด้วยการวนซ้ำที่ซ้อนกันซึ่งดำเนินการเรียงลำดับแบบฟองผ่านรายการทั้งหมดจนกระทั่งมีเงื่อนไขซึ่งทำงานบนแฟล็ก ออกเมื่อเราดำเนินการวนซ้ำทั้งหมดโดยไม่มีการเปลี่ยนแปลง เมื่อดำเนินการวนซ้ำที่ซ้อนเหล่านั้นแล้ว รายการที่เรียงลำดับจะ ให้อยู่ในลำดับที่ต้องการเพื่อให้คุณสามารถแสดงบนหน้าจอหรือใช้สำหรับการดำเนินการเพิ่มเติมในรหัสของคุณ อัลกอริทึมการเรียงลำดับแบบฟองจะแสดงด้วยไดอะแกรม

©โดย Stefano furin – งานของตัวเอง, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=37141358

การทำงานของอัลกอริทึมการเรียงลำดับฟอง

ตอนนี้เราได้กล่าวถึงตรรกะของอัลกอริทึมการเรียงลำดับแบบฟองแล้ว เรามาเจาะลึกลงไปในตัวอย่างกัน เราจะนำรายชื่อของตัวเลขที่ไม่เรียงลำดับและให้ฟองอากาศจัดเรียงตามลำดับจากน้อยไปมาก

เพื่อให้ง่าย เราจะใช้รายการของตัวเลขสี่ตัว:

29, 15, 0,-5

การคำนวณแรกที่ Bubble Sort จะทำคือการตรวจสอบค่าของดัชนี 0 และดัชนี 1 ตามที่เราได้กล่าวไว้ข้างต้น เนื่องจาก 29 มากกว่า 15 ตำแหน่งจะสลับ ทำให้เรามีลำดับของตัวเลขดังนี้:

15, 29, 0,-5

ถัดไป อัลกอริทึมจะเปรียบเทียบ 29 และ 0 นี่คือรายการผลลัพธ์:

15, 0, 29,-5

ครั้งสุดท้ายในการวนซ้ำครั้งแรกนี้ อัลกอริทึมเปรียบเทียบ 29 กับ-5 ทำให้เรามีรายการต่อไปนี้:

15, 0,-5, 29

รายการของเรายังไม่ใช่ตำแหน่งที่เราต้องการ และการวนซ้ำครั้งต่อไปจะช่วยเราจัดเรียงข้อมูลดังกล่าว เราจะเห็นรายการเปลี่ยนไปในลักษณะนี้:

0, 15,-5, 29

0,-5, 15, 29

0,-5, 15, 29

0,-5, 15, 29

การทำซ้ำครั้งที่สามจะให้ผลลัพธ์ดังนี้:

-5, 0, 15 , 29

-5, 0, 15, 29

-5, 0, 15, 29

-5, 0, 15, 29

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

การนำอัลกอริทึม Bubble Sort ไปใช้โดยใช้ For Loop

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

def bubbleSort (numArray, z): for a in range(z-1): swap=False for b in range (0, z-a-1): if numArray[b] > numArray[b+1]: swap=True numArray[b], numArray[b+1]=numArray[b+1], numArray[b] ถ้าไม่สลับ: คืนค่า numArray numberArray=[82, 67 , 0,-500,-80, 99, 2] x=len(numberArray) print (“Sorted Array:”) print (bubbleSort(numberArray, x))

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

มาแบ่งรหัสนี้ทีละขั้นตอนเพื่อให้เราเข้าใจว่าเกิดอะไรขึ้น

การเริ่มต้นอาร์เรย์

ก่อนอื่น เราต้องเริ่มต้นอาร์เรย์ของเราด้วยชุดของตัวเลขที่เรา d ต้องการเรียงลำดับ (numberArray) สิ่งเหล่านี้ถูกเริ่มต้นโดยเจตนาในลำดับสุ่มเพื่อสาธิตวิธีการทำงานของอัลกอริทึมการเรียงลำดับแบบฟอง ต่อไป เราจะเริ่มต้นตัวแปรที่โฮสต์จำนวนรายการที่เรามีในอาร์เรย์ (x) เราจะใช้ตัวแปรนี้ในภายหลังเพื่อควบคุมจำนวนครั้งที่เราวนซ้ำผ่านลูป

การกำหนดอัลกอริทึมการจัดเรียงแบบฟองสบู่

ค่าสองค่าจะถูกส่งผ่านไปยังอัลกอริทึม ซึ่งกำหนดเป็น bubbleSort. ค่าแรกคืออาร์เรย์เอง จากนั้นเราก็ผ่านความยาวของอาร์เรย์ ภายในอัลกอริทึม สิ่งเหล่านั้นถูกกำหนดใหม่เป็น numArray และ z ตามลำดับ

การวนซ้ำที่เราใช้ในการดำเนินการเรียงลำดับฟองจะวนซ้ำตามจำนวนครั้งที่กำหนด แต่ก็ไม่จำเป็นเสมอไปที่จะดำเนินการตามหลักสูตรของมัน. ดังนั้น ก่อนอื่นเราต้องตั้งค่าตัวแปรบูลีนที่จุดเริ่มต้นของวงรอบนอกซึ่งจะเปลี่ยนจาก False เป็น True ในวงในหากมีการสลับระหว่างอัลกอริทึมการเรียงลำดับของเรา

ตามที่เราพูดถึง ก่อนหน้านี้ อัลกอริทึมการเรียงลำดับแบบฟองจะเปรียบเทียบค่าที่อยู่ติดกันสองค่าเพื่อพิจารณาว่าจำเป็นต้องเปลี่ยนอาร์เรย์หรือไม่ ดังนั้นเราจึงตั้งค่าเงื่อนไขเพื่อกำหนดว่าค่าใดมีค่าสูงสุด ถ้าค่าของตัวแปรตัวแรกสูงกว่า มันจะสลับตำแหน่งกับรายการที่อยู่ติดกันในอาร์เรย์ และเนื่องจากมีการสลับ เราจะตั้งค่าบูลีน (สลับ) เป็น True เพื่อไม่ให้ออกจากลูป

เมื่อลูปภายในผ่านอาร์เรย์แล้ว ครั้งแรกค่าบูลีนจะถูกตั้งค่าเป็น True เราจึงเข้าไปในลูปภายนอก ครั้งที่สอง ตั้งค่าบูลีน (สลับ) เป็น False อีกครั้งเพื่อเริ่มกระบวนการทั้งหมด บูลีนนี้ต้องเริ่มต้นใหม่ทุกครั้ง เนื่องจากเราต้องการให้อัลกอริทึมของเราสามารถออกจากครั้งแรกที่เราผ่านวงในโดยไม่ต้องสลับ คุณสามารถดำเนินการตามกระบวนการทั้งหมดโดยไม่มีเงื่อนไขการออก แต่โปรแกรมของคุณจะทำงานได้เร็วขึ้นเมื่อนำไปใช้งาน

การเยี่ยมชมช่วงต่างๆ

อัลกอริทึมการเรียงลำดับแบบฟองอากาศจะดำเนินการตามขั้นตอนนี้ต่อไปจนกว่าเราจะ ผ่านการวนซ้ำทั้งหมดหนึ่งครั้งโดยไม่ต้องทำการแลกเปลี่ยน ในไวยากรณ์ของ for loop ช่วงจะบอกลูปว่าเมื่อใดควรเริ่ม หยุด และจำนวนขั้นตอนที่จะเพิ่มขึ้น สามารถรับพารามิเตอร์สามตัว แต่ต้องการเพียงตัวเดียว—ที่จุดใดที่ for วนซ้ำควรหยุด

ใน for วนรอบภายนอกของเรา เราเพียงต้องบอกให้มันหยุดที่จุดใด ซึ่งก็คือค่าสุดท้าย ดัชนีของอาร์เรย์ เราต้องใช้ z-1 เป็นช่วงตรงนั้นเพราะดัชนีเริ่มเลข 0 แทนที่จะเป็น 1 ดังนั้นถ้าเราปล่อยที่ z มันจะไปมากกว่าที่เราต้องการหนึ่งเท่า

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

การอัปเดตอาร์เรย์

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

สวิตช์นี้สามารถเกิดขึ้นได้หลายวิธี แต่วิธีที่เร็วและง่ายที่สุดในการดำเนินการนี้คือการกำหนดค่าให้กับรายการที่อยู่ติดกันพร้อมกัน สิ่งนี้สำเร็จได้ด้วยคำสั่งต่อไปนี้: numArray[b], numArray[b+1]=numArray[b+1], numArray[b] อีกวิธีหนึ่งคือการสร้างตัวแปรชั่วคราวเพื่อเก็บค่าใดค่าหนึ่งที่ต้องย้าย ในขณะที่อีกค่าหนึ่งย้ายไปด้วยการมอบหมายอย่างง่าย แต่เนื่องจากต้องใช้โค้ดมากขึ้น จึงมีประสิทธิภาพมากขึ้นเมื่อเรากำหนดทั้งสองอย่างพร้อมกัน

เอาต์พุตของผลลัพธ์

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

อาร์เรย์ที่เรียงลำดับที่เราจะได้รับกลับมาจากตัวอย่างของเรา:
[-500,-80, 0, 2, 67, 82, 99]

กรณีการใช้งานที่ดีที่สุดและแย่ที่สุดของ Bubble Sort อัลกอริทึม

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

มาดูความซับซ้อนของเวลาและพื้นที่เพื่อทำความเข้าใจเกี่ยวกับประสิทธิภาพ

ความซับซ้อนของเวลาของอัลกอริทึมการเรียงฟองสบู่

<ตาราง >กรณีความซับซ้อนของเวลาดีที่สุด0 (N)เฉลี่ย0 (N^2)แย่ที่สุด0 (N^2)

(N หมายถึงจำนวนรายการในชุดข้อมูล)

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

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

ความซับซ้อนของพื้นที่ของอัลกอริทึมการเรียงฟองสบู่

<ตาราง >กรณีความซับซ้อนของพื้นที่BestO(1)AverageO(1)WorstO(1)

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

สรุป

อัลกอริทึมการเรียงลำดับแบบฟองจะมีประสิทธิภาพเมื่อคุณต้องการเรียงลำดับเท่านั้น ข้อมูลจำนวนน้อย แต่จริงๆ แล้วมันไม่ได้มีประสิทธิภาพสูงสุด และไม่เหมาะเนื่องจากประสิทธิภาพของมัน แต่จะมีประโยชน์มากที่สุดในฐานะเครื่องมือการเรียนรู้สำหรับผู้เริ่มเขียนโปรแกรมเพื่อเรียนรู้ว่าคอมพิวเตอร์ดำเนินการอัลกอริทึมอย่างไร หากคุณกำลังเรียนหลักสูตรโครงสร้างข้อมูลและอัลกอริทึม คุณจะต้องเชี่ยวชาญในหลักสูตรนี้ เมื่อคุณเข้าใจพื้นฐานของอัลกอริทึมการเรียงลำดับแล้ว คุณสามารถเปลี่ยนไปใช้อัลกอริทึมที่มีประสิทธิภาพมากขึ้นได้

อัลกอริทึมการเรียงลำดับแบบ Bubble คืออะไร และทำงานอย่างไร (พร้อมตัวอย่าง) คำถามที่พบบ่อย (คำถามที่พบบ่อย) 

อัลกอริทึมการเรียงลำดับแบบฟองคืออะไร

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

อัลกอริทึมการเรียงลำดับแบบฟองมีข้อจำกัดอะไรบ้าง

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

เวลาที่ซับซ้อนของอัลกอริทึมการเรียงลำดับแบบฟองคืออะไร

ความซับซ้อนของเวลามีตั้งแต่ 0 (N) ถึง 0 (N^2) ซึ่งกรณีตัวอย่างที่ดีที่สุดจะเกิดขึ้นเมื่อชุดข้อมูลถูกจัดเรียงแล้ว N แสดงถึงจำนวนรายการในชุดข้อมูล ดังนั้นความซับซ้อนของเวลาจึงเพิ่มขึ้นอย่างมากเมื่อทำงานกับชุดข้อมูลขนาดใหญ่

อัลกอริทึมการจัดเรียงแบบฟองซ้อนความซับซ้อนของพื้นที่คืออะไร

ความซับซ้อนของพื้นที่ ไม่ว่าชุดข้อมูลของเราจะใหญ่แค่ไหนก็คือ O(1) ซึ่งหมายความว่ายังคงเหมือนเดิม ในทางทฤษฎี หากคุณมีชุดข้อมูล 200 รายการ ก็จะต้องใช้พื้นที่เท่ากับชุดข้อมูลที่มี 100 รายการ

ควรใช้อัลกอริทึมการจัดเรียงแบบฟองเมื่อใด

เนื่องจากมีประสิทธิภาพมากที่สุดกับชุดข้อมูลขนาดเล็ก อัลกอริทึมการเรียงลำดับแบบฟองจึงมีประโยชน์มากที่สุดในการตั้งค่าการศึกษา เมื่อผู้เขียนโปรแกรมเริ่มต้นเรียนรู้วิธีโค้ดอัลกอริทึมการเรียงลำดับ

อะไร มีวิธีต่างๆ ในการใช้อัลกอริทึมการเรียงลำดับแบบฟองหรือไม่

เนื่องจากเราจำเป็นต้องทำซ้ำผ่านชุดข้อมูลทั้งหมดเพื่อดำเนินการอัลกอริทึมการเรียงลำดับแบบฟอง หรือวนรอบขณะหนึ่ง

ทางเลือกอื่นๆ ของอัลกอริทึมการเรียงลำดับแบบฟองคืออะไร

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