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

ในฐานะที่เป็นภาษาการเขียนโปรแกรมแบบหลายกระบวนทัศน์ที่มีแนวทางการออกแบบเชิงวัตถุที่มีโครงสร้างและไวยากรณ์และไวยากรณ์ที่เรียบง่ายและไม่กระจาย Python จึงเกิดขึ้นอย่างรวดเร็วในฐานะภาษาทางเลือกสำหรับโปรแกรมเมอร์ที่ทำงานในโครงการที่มีความซับซ้อนและขนาดที่แตกต่างกัน

Python จัดเตรียมไลบรารีโมดูลาร์ของอัลกอริทึมที่สร้างไว้ล่วงหน้าซึ่งช่วยให้ผู้ใช้สามารถดำเนินการต่างๆ ที่อาจช่วยให้พวกเขาบรรลุงานของตนเองหรือทำหน้าที่เป็นขั้นตอนในการบรรลุเป้าหมายที่ใหญ่ขึ้นและซับซ้อนมากขึ้น หนึ่งในอัลกอริทึมที่ได้รับความนิยมมากคืออัลกอริทึมที่ช่วยให้ฟังก์ชัน Merge Sort

Merge Sort คืออะไร?

เป็นเทคนิคการเรียงลำดับตามวัตถุประสงค์ทั่วไปที่ช่วยให้ผู้ใช้สามารถนำชุดข้อมูลแบบสุ่มประเภทใดก็ได้จากแหล่งใดก็ได้มาแบ่งข้อมูลออกเป็นขั้นตอนซ้ำๆ จนในที่สุดก็แยกย่อยออกเป็นส่วนประกอบแต่ละส่วน ซึ่งเป็นเทคนิคเรียกซ้ำ ซึ่งเรียกกันโดยทั่วไปว่า ' วิธีการแบ่งและพิชิต '

จากนั้นอัลกอริทึมจะรวบรวมส่วนประกอบแต่ละส่วนเข้าด้วยกันอีกครั้งในขั้นตอนที่ซ้ำกัน แต่จัดเรียงเป็นลำดับตรรกะที่ตัดสินใจล่วงหน้าในแต่ละขั้นตอนไปพร้อมกัน โดยใช้การเปรียบเทียบพื้นฐานและสลับจนกว่าชุดข้อมูลทั้งหมดจะถูกสร้างขึ้นใหม่ในลำดับตรรกะที่ต้องการ .

ดูหลักสูตรวิทยาศาสตร์ข้อมูลอื่น ๆ ของเราที่ upGrad

เทคนิคการแบ่งและพิชิต

ยกตัวอย่างเช่น ชุดข้อมูลสุ่มของตัวอักษร: N, H, V, B, Q, D, Z, R

ขั้นตอนที่ 1 : ชุดข้อมูลเดิมจะถูกแบ่งออกเป็นสองกลุ่มดังนี้:

N, H, V, B Q, D, Z, R

ขั้นตอนที่ 2 : อาร์เรย์ผลลัพธ์ทั้งสองได้รับการแบ่งย่อยเพิ่มเติมดังนี้:

N, HV , BQ, DZ, R

ขั้นตอนที่ 3 : ในที่สุด อาร์เรย์ทั้งสี่จะถูกแยกย่อยออกไปอีกจนกว่าชุดข้อมูลทั้งหมดจะแยกย่อยออกเป็นองค์ประกอบแต่ละส่วน:

N H V B Q D Z R

จากนั้นกระบวนการจะย้อนกลับ และจุดข้อมูลแต่ละจุดจะเริ่มผสานเข้าด้วยกันอย่างชาญฉลาด แต่ในระหว่างกระบวนการผสานนี้ แต่ละองค์ประกอบในอาร์เรย์ย่อยแต่ละรายการจะได้รับการประเมินและสับเปลี่ยนเพื่อให้จัดเรียงตามลำดับตรรกะ (ลำดับตัวอักษร) ดังนี้:

ขั้นตอนที่ 4 : แต่ละองค์ประกอบรวมกันเป็นคู่ในขณะที่สลับตำแหน่งตามที่จำเป็นเพื่อสร้างลำดับที่ถูกต้อง:

H, N B, V D, Q R, Z

ขั้นตอนที่ 5 : กระบวนการวนซ้ำของการรวมและการเรียงลำดับจะดำเนินต่อไปในการวนซ้ำถัดไป:

B, H, N, V ​​D, Q, R, Z

ขั้นตอนที่ 6 : ในที่สุดชุดข้อมูลทั้งหมดจะถูกสร้างขึ้นใหม่ตามลำดับตัวอักษรเชิงตรรกะ:

B, D, H, N, Q, R, V, Z

สำรวจหลักสูตรวิทยาศาสตร์ข้อมูลยอดนิยมของเรา

ผสานการใช้งานการเรียงลำดับ

มีสองวิธีในการนำ Merge Sort ไปใช้ใน Python แนวทางจากบนลงล่างและแนวทางจากล่างขึ้นบน

วิธีการจากบนลงล่าง:

วิธีการจากบนลงล่างที่ใช้บ่อยกว่าคือวิธีที่อธิบายไว้ข้างต้น ใช้เวลานานกว่าและใช้หน่วยความจำมากขึ้น ดังนั้นจึงไม่มีประสิทธิภาพเมื่อทำงานกับชุดข้อมูลขนาดเล็ก อย่างไรก็ตาม มีความน่าเชื่อถือมากกว่ามาก โดยเฉพาะอย่างยิ่งเมื่อใช้กับชุดข้อมูลขนาดใหญ่

อ่านบทความวิทยาศาสตร์ข้อมูลยอดนิยมของเรา

รหัสอินพุต:

def merge_sort (inp_arr):

ขนาด = เลน (inp_arr)

ถ้าขนาด > 1:

กลาง = ขนาด // 2

left_arr = inp_arr (: กลาง)

rIght_arr = inp_arr (กลาง :)

merge_sort (left_arr)

รวม _sort (right_arr)

ฉัน = 0

เจ = 0

k = 0

(โดยที่ i และ j เป็นตัววนซ้ำสำหรับการข้ามซีกซ้ายและขวาของชุดข้อมูลตามลำดับ และ k เป็นตัววนซ้ำของชุดข้อมูลโดยรวม)

left_size = เลน (left_arr)

ขวา _size = len(right_arr)

ในขณะที่ i < left_size และ j < ขนาดด้านขวา:

ถ้า left_arr(i) < right_arr (j):

inp_arr(k) – left_arr(ผม)

ฉัน >= 1

อื่น:

inp_arr(k) = right_arr (ญ)

เจ += 1

k += 1

ในขณะที่ฉัน < left_size:

inp_arr (k) = left_arr (ผม)

ฉัน += 1

k += 1

ในขณะที่ j < right_size:

inp_arr (k) = right_arr (ญ)

เจ += 1

k += 1

inp_arr = (ไม่มี, H, V, B, Q, D, Z, R)

พิมพ์(:อินพุตอาร์เรย์:\n”)

พิมพ์ (inp_arr)

merge_sort (inp_arr)

พิมพ์("อาร์เรย์ที่เรียงลำดับ:\n")

พิมพ์ (inp_arr)

เอาท์พุต:

อาร์เรย์อินพุต: N, H, V, B, Q, D, Z, R

อาร์เรย์เอาต์พุต: B, D, H, N, Q, R, V, Z

วิธีการจากล่างขึ้นบน:

วิธีการจากล่างขึ้นบนนั้นรวดเร็วกว่า ใช้หน่วยความจำน้อยกว่า และทำงานได้อย่างมีประสิทธิภาพกับชุดข้อมูลขนาดเล็ก แต่อาจประสบปัญหาเมื่อทำงานกับชุดข้อมูลขนาดใหญ่ ดังนั้นจึงใช้ไม่บ่อยนัก

รหัสอินพุต:

def ผสาน (ซ้าย, ขวา):

ผลลัพธ์ = [] x, y = 0, 0

สำหรับ k ในช่วง (0, len (ซ้าย) + len (ขวา)):

ถ้าฉัน == เลน (ซ้าย): # ถ้าในตอนท้ายของครึ่งแรก

result.append(right[j]) # เพิ่มค่าทั้งหมดของครึ่งหลัง

เจ += 1

elif j == len(ขวา): # ถ้าจบครึ่งหลัง

result.append(left[x]) # เพิ่มค่าทั้งหมดของครึ่งแรก

ฉัน += 1

elif ขวา[j] < ซ้าย[i]:

ผลลัพธ์ต่อท้าย (ขวา [j])

เจ += 1

อื่น:

ผลลัพธ์ ต่อท้าย (ซ้าย [i])

ฉัน += 1

ส่งคืนผลลัพธ์

def การผสาน (ar_list):

ความยาว = เลน (ar_list)

ขนาด = 1

ในขณะที่ขนาด < ความยาว:

size+=size # เริ่มต้นที่ 2 ตามที่อธิบายไว้

สำหรับตำแหน่งในช่วง (0, ความยาว, ขนาด):

เริ่มต้น = ตำแหน่ง

กลาง = pos + int(ขนาด / 2)

ปลาย = pos + ขนาด

ซ้าย = ar_list[ เริ่มต้น : กลาง ] ขวา = ar_list[ กลาง : สิ้นสุด ]

ar_list[start:end] = ผสาน (ซ้าย, ขวา)

ส่งคืน ar_list

ar_list = [N, H, V, B, Q, D, Z, R] พิมพ์ (ผสาน (ar_list))

เอาท์พุต:

อาร์เรย์อินพุต: N, H, V, B, Q, D, Z, R

อาร์เรย์เอาต์พุต: B, D, H, N, Q, R, V, Z

การนำ Merge Sort ไปใช้กับชุดข้อมูลในชีวิตจริงที่ซับซ้อนมากขึ้น

ลองใช้วิธีจากบนลงล่างกับรถออฟโรดแบบสุ่มสี่คันในอินเดีย:

รหัสอินพุต:

รถ คลาส :

def __init__(ตัวเอง ยี่ห้อ รุ่น ราคา):

self.brand = แบรนด์

self.model = นางแบบ

self.price = ราคา

def __str__(ตัวเอง):

return str.format(“ยี่ห้อ: {}, รุ่น: {}, ราคา: {}”, self.brand,

self.model, self.price)

def ผสาน (list1, i, j, k, comp_fun):

left_copy = list1[i:k + 1]

r_sublist = list1[k+1:r+1]

left_copy_index = 0

j_sublist_index = 0

sorted_index = ฉัน

ในขณะที่ left_copy_index < len(left_copy) และj_sublist_index <

เลน (j_sublist):

ถ้า comp_fun (left_copy[left_copy_index], j_sublist[j_sublist_index]):

list1[sorted_index] = left_copy[left_copy_index]

left_copy_index = left_copy_index + 1

อื่น ๆ :

list1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

sorted_index = sorted_index + 1

ในขณะที่ left_copy_index < len (left_copy):

list1[sorted_index] = left_copy[left_copy_index]

left_copy_index = left_copy_index + 1

sorted_index = sorted_index + 1

ในขณะที่ j_sublist_index < len(j_sublist):

list1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

sorted_index = sorted_index + 1

def merge_sort(list1, i, j, comp_fun):

ถ้า ฉัน >= j:

กลับ

k = (i + j)//2

merge_sort(list1, i, k, comp_fun)

merge_sort(list1, k + 1, j, comp_fun)

รวม (list1, i, j, k, comp_fun)

car1 = รถยนต์("รถจี๊ป", "แรงเลอร์", 0.58)

car2 = รถยนต์("ฟอร์ด", "ความพยายาม", 0.35)

car3 = รถยนต์("จากัวร์แลนด์โรเวอร์", "เรนจ์โรเวอร์สปอร์ต", 1.76)

car4 = รถยนต์("Mercedes Benz", "G-class", 2.42)

list1 = [รถ1, รถ2, รถ3, รถ4]

merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.brand < carB.brand)

พิมพ์ (“รถยนต์เรียงตามยี่ห้อ:”)

สำหรับ รถ ในlist1:

พิมพ์ (รถ)

พิมพ์ ()

merge_sort(list1, 0, len(list1) -1, แลมบ์ดา carA, carB: carA.price< carB.price)

พิมพ์ (“รถยนต์เรียงตามราคา:”)

สำหรับ รถ ในlist1:

พิมพ์ (รถ)

เอาท์พุต:

รถยนต์แยกตามยี่ห้อ:

ฟอร์ด เอ็นเดฟเวอร์

จากัวร์ แลนด์โรเวอร์ เรนจ์ โรเวอร์ สปอร์ต

จี๊ป แรงเลอร์

เมอร์เซเดซ เบนซ์ จี-คลาส

รถเรียงตามราคา:

ฟอร์ด เอ็นเดฟเวอร์

จี๊ป แรงเลอร์

จากัวร์ แลนด์โรเวอร์ เรนจ์โรเวอร์

เมอร์เซเดซ เบนซ์ จี-คลาส

คุณสามารถเรียนรู้ทั้งด้านทฤษฎีและปฏิบัติของ Python ด้วยประกาศนียบัตรวิชาชีพด้านวิทยาศาสตร์ข้อมูลและการวิเคราะห์ธุรกิจของ upGrad จาก University of Maryland หลักสูตรนี้ช่วยให้คุณเรียนรู้ Python ตั้งแต่เริ่มต้น แม้ว่าคุณจะยังใหม่ต่อการเขียนโปรแกรมและการเขียนโค้ด upGrad จะเสนอหลักสูตรเตรียมความพร้อมสองสัปดาห์ให้คุณ เพื่อให้คุณได้เรียนรู้พื้นฐานการเขียนโปรแกรม คุณจะได้เรียนรู้เกี่ยวกับเครื่องมือต่างๆ เช่น Python, SQL, ในขณะที่ทำงานในโครงการอุตสาหกรรมต่างๆ

วางแผนอาชีพการพัฒนาซอฟต์แวร์ของคุณตอนนี้!

สมัครหลักสูตรประกาศนียบัตรวิชาชีพด้านวิทยาศาสตร์ข้อมูลและการวิเคราะห์ธุรกิจ