การเรียงลำดับการแทรกในโปรแกรม Python

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับการใช้งานการจัดเรียงการแทรกใน Python 3.x หรือก่อนหน้านั้น

อัลกอริทึม

• วนซ้ำองค์ประกอบอินพุตโดยขยายอาร์เรย์ที่เรียงลำดับในแต่ละการวนซ้ำ

• เปรียบเทียบองค์ประกอบปัจจุบันกับค่าที่มากที่สุดที่มีอยู่ในอาร์เรย์ที่จัดเรียง

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

• ซึ่งทำได้โดยการย้ายองค์ประกอบทั้งหมดไปทางขวา ซึ่งใหญ่กว่าองค์ประกอบปัจจุบัน ในอาร์เรย์ที่จัดเรียงไปยังตำแหน่งหนึ่งข้างหน้า

ตอนนี้เรามาดูการแสดงภาพของอัลกอริทึม

มาดูการใช้งานกัน

ตัวอย่าง

def insertionSort(arr):
   for i in range(1, len(arr)):
      key = arr[i]
      # Move elements of arr[0..i-1], that are greater
      than key,
      # to one position ahead of their current position
      j = i-1
      while j >=0 and key < arr[j] :
         arr[j+1] = arr[j]
         j -= 1
      arr[j+1] = key
# main
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print ("The sorted array is:")
for i in range(len(arr)):
   print (arr[i])

ผลลัพธ์

The sorted array is:
a
i
l
o
r
t
t
u

ความซับซ้อนของเวลา: โอ(n*2)

พื้นที่เสริม: O(1)

ตัวแปรทั้งหมดถูกประกาศในกรอบสากลดังแสดงในรูปด้านล่าง -

บทสรุป

ในบทความนี้ เราได้เรียนรู้เกี่ยวกับการจัดเรียงการแทรกและการนำไปใช้งานใน Python 3.x หรือก่อนหน้านั้น