Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรม Python สำหรับ Iterative Quick Sort


ในบทความนี้ เราจะเรียนรู้เกี่ยวกับวิธีแก้ปัญหาตามที่ระบุด้านล่าง

แจ้งปัญหา − เราได้รับอาร์เรย์ เราจำเป็นต้องจัดเรียงโดยใช้แนวคิดของการเรียงลำดับอย่างรวดเร็วโดยใช้วิธีการวนซ้ำ

ที่นี่เราแบ่งพาร์ติชั่นอาร์เรย์ก่อนและจัดเรียงพาร์ติชั่นแยกกันเพื่อรับอาร์เรย์ที่จัดเรียง

ทีนี้มาดูวิธีแก้ปัญหาในการใช้งานด้านล่างกัน:

ตัวอย่าง

# iterative way
def partition(arr,l,h):
   i = ( l - 1 )
   x = arr[h]
   for j in range(l , h):
      if arr[j] <= x:
         # increment
         i = i+1
         arr[i],arr[j] = arr[j],arr[i]
   arr[i+1],arr[h] = arr[h],arr[i+1]
   return (i+1)
# sort
def quickSortIterative(arr,l,h):
   # Creation of a stack
   size = h - l + 1
   stack = [0] * (size)
   # initialization
   top = -1
   # push initial values
   top = top + 1
   stack[top] = l
   top = top + 1
   stack[top] = h
   # pop from stack
   while top >= 0:
      # Pop
      h = stack[top]
      top = top - 1
      l = stack[top]
      top = top - 1
      # Set pivot element at its correct position
      p = partition( arr, l, h )
      # elements on the left
      if p-1 > l:
         top = top + 1
         stack[top] = l
         top = top + 1
         stack[top] = p - 1
      # elements on the right
      if p+1 < h:
         top = top + 1
         stack[top] = p + 1
         top = top + 1
         stack[top] = h
# main
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

โปรแกรม Python สำหรับ Iterative Quick Sort

ตัวแปรทั้งหมดได้รับการประกาศในขอบเขตท้องถิ่นและการอ้างอิงของตัวแปรนั้นดูได้จากรูปด้านบน

บทสรุป

ในบทความนี้ เราได้เรียนรู้เกี่ยวกับวิธีการสร้างโปรแกรม Python สำหรับ Iterative Quick Sort