ในบทความนี้ เราจะเรียนรู้เกี่ยวกับ Selection Sort และการนำไปใช้งานใน Python 3.x หรือเวอร์ชันก่อนหน้า
ในอัลกอริทึม Selection Sort อาร์เรย์จะถูกเรียงโดยการหาองค์ประกอบน้อยที่สุดจากส่วนที่ยังไม่เรียงลำดับแล้วนำไปวางที่จุดเริ่มต้น ซับอาร์เรย์สองชุดจะถูกสร้างขึ้นระหว่างการทำงานของ Selection Sort บนอาร์เรย์ที่กำหนด
- ซับอาร์เรย์ที่เรียงลำดับแล้ว
- ซับอาร์เรย์ที่ยังไม่เรียงลำดับ
ในแต่ละรอบของ Selection Sort องค์ประกอบน้อยที่สุดจากซับอาร์เรย์ที่ยังไม่เรียงลำดับจะถูกนำออกและแทรกเข้าไปในซับอาร์เรย์ที่เรียงลำดับแล้ว
มาดูการแสดงภาพของอัลกอริทึม
ตอนนี้มาดูการนำไปใช้งานของอัลกอริทึม
ตัวอย่าง
A = ['t', 'u', 't', 'o', 'r', 'i', 'a', 'l']
for i in range(len(A)):
min_idx = i
for j in range(i + 1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
# สลับ
A[i], A[min_idx] = A[min_idx], A[i]
# main
for i in range(len(A)):
print(A[i])
ผลลัพธ์
a i l o r t t u
ที่นี่เราได้รับผลลัพธ์จากอัลกอริทึมในลำดับน้อยไปมาก ตัวแปร Min_idx คือค่าปัจจุบันที่กำลังถูกเปรียบเทียบกับค่าอื่นๆ พารามิเตอร์การวิเคราะห์ของอัลกอริทึมแสดงด้านล่าง −
Time Complexity − O(n²)
Auxiliary Space − O(1)
ตัวแปรทั้งหมดถูกประกาศในเฟรมส่วนกลาง ตามที่แสดงในภาพด้านล่าง
สรุป
ในบทความนี้ เราได้เรียนรู้เกี่ยวกับ Selection Sort และการนำไปใช้งานใน Python 3.x หรือเวอร์ชันก่อนหน้า
