Python - อัลกอริทึมการเรียงลำดับ
การเรียงลำดับหมายถึงการจัดเรียงข้อมูลในรูปแบบเฉพาะ อัลกอริทึมการเรียงลำดับระบุวิธีการจัดเรียงข้อมูลตามลำดับเฉพาะ คำสั่งทั่วไปส่วนใหญ่อยู่ในลำดับตัวเลขหรือพจนานุกรม
ความสำคัญของการจัดเรียงอยู่ที่ความจริงที่ว่าการค้นหาข้อมูลสามารถปรับให้เหมาะสมได้ในระดับที่สูงมากหากข้อมูลถูกจัดเก็บในลักษณะที่เรียงลำดับ การเรียงลำดับยังใช้เพื่อแสดงข้อมูลในรูปแบบที่อ่านได้มากขึ้น ด้านล่างนี้เราจะเห็นการใช้งานการเรียงลำดับใน python ห้าแบบ
- เรียงฟอง
- ผสานการเรียง
- เรียงลำดับการแทรก
- การจัดเรียงเชลล์
- เรียงลำดับการเลือก
เรียงฟอง
เป็นอัลกอริทึมที่ใช้การเปรียบเทียบซึ่งแต่ละคู่ขององค์ประกอบที่อยู่ติดกันจะถูกเปรียบเทียบและองค์ประกอบจะถูกสลับหากไม่เรียงตามลำดับ
def bubblesort(list):
# Swap the elements to arrange in order
for iter_num in range(len(list)-1,0,-1):
for idx in range(iter_num):
if list[idx]>list[idx+1]:
temp = list[idx]
list[idx] = list[idx+1]
list[idx+1] = temp
list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[2, 6, 11, 19, 27, 31, 45, 121]
ผสานการเรียง
การจัดเรียงการผสานก่อนอื่นจะแบ่งอาร์เรย์ออกเป็นครึ่งเท่า ๆ กันจากนั้นจึงรวมเข้าด้วยกันในลักษณะที่เรียงลำดับ
def merge_sort(unsorted_list):
if len(unsorted_list) <= 1:
return unsorted_list
# Find the middle point and devide it
middle = len(unsorted_list) // 2
left_list = unsorted_list[:middle]
right_list = unsorted_list[middle:]
left_list = merge_sort(left_list)
right_list = merge_sort(right_list)
return list(merge(left_list, right_list))
# Merge the sorted halves
def merge(left_half,right_half):
res = []
while len(left_half) != 0 and len(right_half) != 0:
if left_half[0] < right_half[0]:
res.append(left_half[0])
left_half.remove(left_half[0])
else:
res.append(right_half[0])
right_half.remove(right_half[0])
if len(left_half) == 0:
res = res + right_half
else:
res = res + left_half
return res
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(unsorted_list))
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[11, 12, 22, 25, 34, 64, 90]
เรียงลำดับการแทรก
การเรียงลำดับการแทรกเกี่ยวข้องกับการค้นหาตำแหน่งที่เหมาะสมสำหรับองค์ประกอบที่กำหนดในรายการที่เรียงลำดับ ดังนั้นในการเริ่มต้นเราจะเปรียบเทียบสององค์ประกอบแรกและจัดเรียงโดยการเปรียบเทียบ จากนั้นเราเลือกองค์ประกอบที่สามและหาตำแหน่งที่เหมาะสมขององค์ประกอบที่เรียงลำดับสองรายการก่อนหน้านี้ ด้วยวิธีนี้เราจะค่อยๆเพิ่มองค์ประกอบเพิ่มเติมในรายการที่จัดเรียงแล้วโดยวางไว้ในตำแหน่งที่เหมาะสม
def insertion_sort(InputList):
for i in range(1, len(InputList)):
j = i-1
nxt_element = InputList[i]
# Compare the current element with next one
while (InputList[j] > nxt_element) and (j >= 0):
InputList[j+1] = InputList[j]
j=j-1
InputList[j+1] = nxt_element
list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[2, 11, 19, 27, 30, 31, 45, 121]
การจัดเรียงเชลล์
Shell Sort เกี่ยวข้องกับการจัดเรียงองค์ประกอบที่อยู่ห่างจาก ech อื่น ๆ เราจัดเรียงรายการย่อยขนาดใหญ่ของรายการที่กำหนดและลดขนาดของรายการจนกว่าองค์ประกอบทั้งหมดจะเรียงลำดับ โปรแกรมด้านล่างนี้จะค้นหาช่องว่างโดยการเทียบกับครึ่งหนึ่งของความยาวของขนาดรายการจากนั้นจึงเริ่มจัดเรียงองค์ประกอบทั้งหมด จากนั้นเราจะรีเซ็ตช่องว่างต่อไปจนกว่ารายการทั้งหมดจะเรียงลำดับ
def shellSort(input_list):
gap = len(input_list) // 2
while gap > 0:
for i in range(gap, len(input_list)):
temp = input_list[i]
j = i
# Sort the sub list for this gap
while j >= gap and input_list[j - gap] > temp:
input_list[j] = input_list[j - gap]
j = j-gap
input_list[j] = temp
# Reduce the gap for the next element
gap = gap//2
list = [19,2,31,45,30,11,121,27]
shellSort(list)
print(list)
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[2, 11, 19, 27, 30, 31, 45, 121]
เรียงลำดับการเลือก
ในการเรียงลำดับการเลือกเราเริ่มต้นด้วยการค้นหาค่าต่ำสุดในรายการที่กำหนดและย้ายไปยังรายการที่เรียงลำดับ จากนั้นเราทำซ้ำขั้นตอนสำหรับแต่ละองค์ประกอบที่เหลือในรายการที่ไม่ได้เรียงลำดับ องค์ประกอบถัดไปที่เข้าสู่รายการที่เรียงลำดับจะถูกเปรียบเทียบกับองค์ประกอบที่มีอยู่และวางไว้ในตำแหน่งที่ถูกต้อง ดังนั้นในตอนท้ายองค์ประกอบทั้งหมดจากรายการที่ไม่ได้เรียงลำดับจะถูกจัดเรียง
def selection_sort(input_list):
for idx in range(len(input_list)):
min_idx = idx
for j in range( idx +1, len(input_list)):
if input_list[min_idx] > input_list[j]:
min_idx = j
# Swap the minimum value with the compared value
input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]
l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)
เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -
[2, 11, 19, 27, 30, 31, 45, 121]