การเรียงลำดับการเลือก: อัลกอริทึมอธิบายด้วย Python ตัวอย่างรหัส

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

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

สิ่งนี้เรียกได้ว่า ในสถานที่ การเรียงลำดับ การเรียงลำดับแบบเลือกจะมีความซับซ้อนของเวลาเท่ากับ O(n²) โดยที่ n คือจำนวนรายการทั้งหมดในรายการ ความซับซ้อนของเวลาจะวัดจำนวนการวนซ้ำที่จำเป็นในการเรียงลำดับรายการ รายการจะแบ่งออกเป็นสองพาร์ติชัน รายการแรกประกอบด้วยรายการที่เรียงลำดับแล้ว ในขณะที่รายการที่สองประกอบด้วยรายการที่ยังไม่ได้เรียงลำดับ

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

การเรียงลำดับการเลือกทำงานอย่างไร

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

ตัวอย่าง

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

นิยามปัญหา

รายการขององค์ประกอบที่อยู่ในลำดับสุ่มจะต้องเรียงลำดับจากน้อยไปมาก ลองดูรายการต่อไปนี้เป็นตัวอย่าง

[21,6,9,33,3]

รายการด้านบนควรได้รับการเรียงลำดับเพื่อให้ได้ผลลัพธ์ดังต่อไปนี้

[3,6,9,21,33]

โซลูชัน (อัลกอริทึม)

ขั้นตอน 1) รับค่า n ซึ่งเป็นขนาดรวมของอาร์เรย์

ขั้นตอน 2) แบ่งพาร์ติชันรายการออกเป็นส่วนที่เรียงลำดับและไม่เรียงลำดับ ส่วนที่เรียงลำดับจะว่างเปล่าในตอนแรก ในขณะที่ส่วนที่ไม่ได้เรียงลำดับจะมีรายการทั้งหมด

ขั้นตอน 3) เลือกค่าต่ำสุดจากส่วนที่ไม่ได้แบ่งพาร์ติชันแล้ววางลงในส่วนที่เรียงลำดับ

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

การแสดงภาพ

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

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

ขั้นตอน 1)

ค่าแรก 21 จะถูกเปรียบเทียบกับค่าที่เหลือเพื่อตรวจสอบว่าเป็นค่าต่ำสุดหรือไม่

3 คือค่าต่ำสุด ดังนั้นตำแหน่ง 21 และ 3 จึงสลับกัน ค่าที่มีพื้นหลังสีเขียวแสดงถึงพาร์ติชันที่เรียงลำดับของรายการ

ขั้นตอน 2)

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

ค่า 6 คือค่าต่ำสุด ดังนั้นจึงคงตำแหน่งไว้

ขั้นตอน 3)

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

ค่า 9 เป็นค่าต่ำสุด ดังนั้นจึงรักษาตำแหน่งในพาร์ติชันที่เรียงลำดับ

ขั้นตอน 4)

ค่า 33 จะถูกเปรียบเทียบกับค่าที่เหลือ

ค่า 21 ต่ำกว่า 33 ดังนั้นตำแหน่งจึงถูกสลับเพื่อสร้างรายการใหม่ด้านบน

ขั้นตอน 5)

เราเหลือเพียงค่าเดียวในรายการที่ไม่ได้แบ่งพาร์ติชัน ดังนั้นจึงมีการจัดเรียงไว้แล้ว

รายการสุดท้ายก็เหมือนกับรายการที่แสดงในภาพด้านบน

การเลือกโปรแกรมเรียงลำดับโดยใช้ Python 3

โค้ดต่อไปนี้แสดงการใช้งานการเรียงลำดับแบบเลือกโดยใช้ Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


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

print(selectionSort(el))

เมื่อรันโค้ดด้านบนจะได้ผลลัพธ์ดังต่อไปนี้

[3, 6, 9, 21, 33]

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

คำอธิบายสำหรับโค้ดมีดังนี้

นี่คือคำอธิบายรหัส:

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

ความซับซ้อนของเวลาของการเรียงลำดับแบบเลือก

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

วงรอบนอกที่เลือกค่าทีละรายการจากรายการจะถูกดำเนินการ n ครั้ง โดยที่ n คือจำนวนค่าทั้งหมดในรายการ

ลูปด้านใน ซึ่งจะเปรียบเทียบค่าจากลูปด้านนอกกับค่าที่เหลือ จะถูกดำเนินการ n ครั้ง โดยที่ n คือจำนวนองค์ประกอบทั้งหมดในรายการ

ดังนั้น จำนวนการดำเนินการคือ (n * n) ซึ่งสามารถแสดงเป็น O(n)²).

การเรียงลำดับแบบเลือกมี 3 หมวดหมู่ความซับซ้อน ได้แก่

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

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

เมื่อใดจึงจะใช้การเรียงลำดับการเลือก?

การเรียงลำดับการเลือกจะใช้ดีที่สุดเมื่อคุณต้องการ:

• คุณต้องเรียงลำดับรายการเล็กๆ ตามลำดับจากน้อยไปมาก
• เมื่อต้นทุนการแลกเปลี่ยนค่าไม่มีนัยสำคัญ
• นอกจากนี้ยังใช้เมื่อคุณต้องการตรวจสอบให้แน่ใจว่าได้ตรวจสอบค่าทั้งหมดในรายการแล้ว

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

ต่อไปนี้เป็นข้อดีของการเรียงลำดับแบบเลือก

• มันทำงานได้ดีมากในรายการเล็กๆ
• มันเป็นอัลกอริธึมแบบแทนที่ ไม่ต้องใช้พื้นที่ในการจัดเรียงมากนัก จำเป็นต้องมีช่องว่างเพิ่มเติมเพียงช่องเดียวเพื่อเก็บตัวแปรชั่วคราว
• ทำงานได้ดีกับรายการที่ได้รับการจัดเรียงแล้ว

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

ข้อเสียของการเรียงลำดับแบบเลือกมีดังต่อไปนี้

• มันทำงานได้ไม่ดีเมื่อทำงานกับรายการจำนวนมาก
• จำนวนการวนซ้ำระหว่างการเรียงลำดับคือ n-squared โดยที่ n คือจำนวนองค์ประกอบทั้งหมดในรายการ
• อัลกอริทึมอื่น เช่น การเรียงลำดับแบบรวดเร็ว มีประสิทธิภาพที่ดีกว่าการเรียงลำดับแบบเลือก

สรุป

• การเรียงลำดับแบบเลือกเป็นอัลกอริทึมการเปรียบเทียบภายในที่ใช้เพื่อเรียงลำดับรายการแบบสุ่มลงในรายการที่มีลำดับ มีความซับซ้อนของเวลาเท่ากับ O(n²)
• รายการแบ่งออกเป็นสองส่วน เรียงลำดับและไม่เรียงลำดับ ค่าต่ำสุดจะถูกเลือกจากส่วนที่ไม่ได้เรียงลำดับและวางไว้ในส่วนที่เรียงลำดับ
• สิ่งนี้จะถูกทำซ้ำจนกว่ารายการทั้งหมดจะถูกจัดเรียง
• การนำรหัสเทียมไปใช้ใน Python 3 เกี่ยวข้องกับการใช้สอง for ลูปและคำสั่ง if เพื่อตรวจสอบว่าจำเป็นต้องมีการสลับหรือไม่
• ความซับซ้อนของเวลาจะวัดจำนวนขั้นตอนที่จำเป็นในการเรียงลำดับรายการ
• ความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดจะเกิดขึ้นเมื่อรายการอยู่ในลำดับจากมากไปน้อย ซึ่งมีความซับซ้อนของเวลาเท่ากับ [Big-O] O(n²)
• ความซับซ้อนของเวลาที่ดีที่สุดเกิดขึ้นเมื่อรายการอยู่ในลำดับจากน้อยไปมากแล้ว ความซับซ้อนของเวลาคือ [Big-Omega] ?(n²)
• ความซับซ้อนของเวลาเฉลี่ยเกิดขึ้นเมื่อรายการอยู่ในลำดับสุ่ม มีความซับซ้อนของเวลาเท่ากับ [Big-theta] ?(n²)
• การเรียงลำดับการเลือกจะใช้ดีที่สุดเมื่อคุณมีรายการเล็กๆ ที่จะเรียงลำดับ ค่าใช้จ่ายในการสลับค่าไม่สำคัญ และจำเป็นต้องตรวจสอบค่าทั้งหมด
• การเรียงลำดับการเลือกทำงานได้ไม่ดีกับรายการจำนวนมาก
• อัลกอริทึมการเรียงลำดับอื่น เช่น การเรียงลำดับแบบรวดเร็ว มีประสิทธิภาพที่ดีกว่าเมื่อเปรียบเทียบกับการเรียงลำดับแบบเลือก