Selection Sort Python:A Guide

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

การเรียงลำดับรายการเป็นการดำเนินการทั่วไปในโปรแกรมต่างๆ

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

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

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

Python Selection Sort คืออะไร

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

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

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

81% ของผู้เข้าร่วมกล่าวว่าพวกเขารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสในการทำงานด้านเทคโนโลยีหลังจากเข้าร่วม bootcamp จับคู่กับ Bootcamp วันนี้

ผู้สำเร็จการศึกษาจากหลักสูตร bootcamp โดยเฉลี่ยใช้เวลาน้อยกว่าหกเดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มต้น bootcamp ไปจนถึงหางานแรก

คู่มือการจัดเรียงการเลือก Python

ไม่มีวิธีใดที่จะเรียนรู้เกี่ยวกับการเรียงลำดับการเลือกได้ดีไปกว่าการดูตัวอย่าง มาดูและเรียงลำดับรายการเกรดนักเรียนจากน้อยไปมากกัน พิจารณารายการที่ไม่เรียงลำดับนี้:

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

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

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

เราจะเปรียบเทียบ 73 กับ 62 73 มากกว่า 62 ซึ่งหมายความว่าค่าต่ำสุดใหม่ของเราคือ 62 จากนั้นรายการของเราจะพิจารณาตัวเลขอื่นๆ ทั้งหมดในรายการของเรา:

• เป็น 61 มากกว่า 62 (ค่าต่ำสุดของเรา)? ไม่เลย สลับเลขกัน ขั้นต่ำกลายเป็น 61.
• เป็น 69 มากกว่า 61 (ค่าต่ำสุดของเรา)? ใช่ ดังนั้นอย่าทำอะไรเลย เข้าพักขั้นต่ำ 61.

รายการของเรามีลักษณะเหมือนกัน:

เมื่อคุณไปถึงจุดสิ้นสุดของรายการ คุณสามารถย้ายขั้นต่ำไปที่จุดเริ่มต้นของรายการ:

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

การทำซ้ำแต่ละรายการของเราจะส่งคืนข้อมูลต่อไปนี้:

1. 73, 62, 61, 69
2. 61, 73, 62, 69
3. 61, 62, 73, 69
4. 61, 62, 69, 73

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

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

วิธีการดำเนินการเรียงลำดับส่วนที่เลือกใน Python

ตอนนี้คุณคุ้นเคยกับทฤษฎีแล้ว:ทำได้ดีมาก! ถึงเวลาสำหรับความท้าทายครั้งใหญ่ เราจะใช้อัลกอริทึมการเรียงลำดับการเลือกใน Python มาเขียนโปรแกรมที่ใช้อาร์เรย์ Python และเรียงลำดับจากน้อยไปมาก

กำหนดฟังก์ชันการจัดเรียง

เราจะเริ่มต้นด้วยการกำหนดฟังก์ชัน Python ที่ดำเนินการเรียงลำดับการเลือกของเรา:

def sortList(array):
	length = len(array)

	for item in range(length):
		minimum = item

		for i in range(item + 1, length):
			if array[i] < array[minimum]:
				minimum = i

		(array[item], array[minimum]) = (array[minimum], array[item])

เราได้เริ่มต้นโดยใช้วิธี Python len() เพื่อดูความยาวของรายการของเรา จากนั้นเราใช้สิ่งนี้เพื่อเริ่มต้น Python for วนซ้ำทุกรายการในรายการของเรา

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

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

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

เรียกฟังก์ชันการเรียงลำดับ

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

numbers = [73, 62, 61, 69]
sortList(numbers)
print("Sorted list:", numbers)

เมื่อเราเรียกใช้โปรแกรม ค่าต่อไปนี้จะถูกส่งคืน:

[61, 62, 69, 73]

รายการของเราได้รับการจัดเรียง ตบหลังตัวเอง คุณทำได้!

สามารถใช้การเรียงลำดับการเลือกเพื่อเรียงลำดับรายการจากมากไปหาน้อย ถ้าคุณต้องการเรียงลำดับรายการด้วยวิธีนี้ คุณสามารถเปลี่ยนคำสั่ง "if" ในการเรียงลำดับการเลือกดังต่อไปนี้:

if array[i] > array[minimum]:

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

คุณควรใช้การเรียงลำดับการเลือกเมื่อใด

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

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

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

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

O(n2) คือความซับซ้อนที่แย่ที่สุด ปานกลาง และดีที่สุดสำหรับอัลกอริทึมนี้ หากคุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับการจัดเรียงความซับซ้อน โปรดดูคำแนะนำเกี่ยวกับ Big O Notation

บทสรุป

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

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

คุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับ Python หรือไม่? อ่านคู่มือ How to Learn Python ฉบับสมบูรณ์สำหรับคำแนะนำจากผู้เชี่ยวชาญเพื่อช่วยให้คุณพัฒนาความรู้