ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:
ข้อความปัญหา — กำหนดอาร์เรย์ ให้จัดเรียงโดยใช้แนวคิดของ Quick Sort แบบวนรอบ (iterative)
ที่นี่เราจะแบ่งพาร์ติชันอาร์เรย์ก่อน แล้วจัดเรียงพาร์ติชันแยกกันเพื่อให้ได้อาร์เรย์ที่จัดเรียงแล้ว
มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:
ตัวอย่างโค้ด
# วิธีแบบวนรอบ (iterative)
def partition(arr, l, h):
i = (l - 1)
x = arr[h]
for j in range(l, h):
if arr[j] <= x:
# เพิ่มดัชนี
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[h] = arr[h], arr[i+1]
return (i + 1)
# ฟังก์ชันจัดเรียง
def quickSortIterative(arr, l, h):
# สร้างสแต็ก (stack)
size = h - l + 1
stack = [0] * (size)
# เริ่มต้น
top = -1
# push ค่าเริ่มต้น
top = top + 1
stack[top] = l
top = top + 1
stack[top] = h
# pop จากสแต็ก
while top >= 0:
# Pop
h = stack[top]
top = top - 1
l = stack[top]
top = top - 1
# ตั้ง pivot element ให้อยู่ตำแหน่งที่ถูกต้อง
p = partition(arr, l, h)
# องค์ประกอบทางซ้าย
if p-1 > l:
top = top + 1
stack[top] = l
top = top + 1
stack[top] = p - 1
# องค์ประกอบทางขวา
if p+1 < h:
top = top + 1
stack[top] = p + 1
top = top + 1
stack[top] = h
# โปรแกรมหลัก
arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
quickSortIterative(arr, 0, n-1)
print("Sorted array is:")
for i in range(n):
print(arr[i], end=" ")
ผลลัพธ์
Sorted array is 2 3 4 5 5 6 7 8
ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน
สรุป
ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ Iterative Quick Sort
