การเรียงลำดับในโครงสร้างข้อมูล: หมวดหมู่และประเภท [พร้อมตัวอย่าง]

การจัดเรียงข้อมูลในลำดับที่ต้องการเรียกว่าการเรียงลำดับในโครงสร้างข้อมูล การจัดเรียงข้อมูลทำให้ง่ายต่อการค้นหาอย่างรวดเร็วและง่ายดาย ตัวอย่างที่ง่ายที่สุดของการเรียงลำดับคือพจนานุกรม ก่อนยุคของอินเทอร์เน็ต เมื่อคุณต้องการค้นหาคำในพจนานุกรม คุณจะต้องเรียงลำดับตัวอักษร นี้ทำให้มันง่าย

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

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

ในโพสต์นี้ เราจะพาคุณผ่านโครงสร้างข้อมูลและอัลกอริธึมการจัดเรียงต่างๆ แต่ก่อนอื่น มาทำความเข้าใจว่าอัลกอริธึมการเรียงลำดับคืออะไรและการเรียงลำดับในโครงสร้างข้อมูล

อัลกอริทึมการเรียงลำดับคืออะไร?

อัลกอริทึมการเรียงลำดับเป็นเพียงชุดคำสั่งหรือคำสั่ง ในที่นี้ อาร์เรย์คืออินพุต ซึ่งอัลกอริธึมการเรียงลำดับดำเนินการดำเนินการเพื่อให้อาร์เรย์ที่เรียงลำดับออกมา

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

นี่คือตัวอย่างของการเรียงลำดับ

สมมติว่าคุณมีอาร์เรย์ของสตริง: [h,j,k,i,n,m,o,l]

ตอนนี้ การเรียงลำดับจะให้ผลลัพธ์เป็นอาร์เรย์เอาต์พุตตามลำดับตัวอักษร

เอาต์พุต: [h,i,j,k,l,m,n,o]

มาเรียนรู้เพิ่มเติมเกี่ยวกับการเรียงลำดับในโครงสร้างข้อมูลกัน

ชำระเงิน: ประเภทของไบนารีทรี

การจัดเรียงหมวดหมู่

การเรียงลำดับมีสองประเภทที่แตกต่างกัน:

• การเรียงลำดับภายใน : หากข้อมูลที่ป้อนเข้านั้นสามารถปรับได้ในหน่วยความจำหลักในครั้งเดียว จะเรียกว่าการเรียงลำดับภายใน
• การเรียงลำดับภายนอก : หากข้อมูลที่ป้อนเข้าจนไม่สามารถปรับเปลี่ยนในหน่วยความจำได้ทั้งหมดในคราวเดียว จะต้องจัดเก็บไว้ในฮาร์ดดิสก์ ฟลอปปีดิสก์ หรืออุปกรณ์จัดเก็บข้อมูลอื่นๆ สิ่งนี้เรียกว่าการเรียงลำดับภายนอก

อ่าน: แนวคิดและหัวข้อโครงการโครงสร้างข้อมูลที่น่าสนใจ

ประเภทของการเรียงลำดับในโครงสร้างข้อมูล

ต่อไปนี้เป็นอัลกอริธึมการเรียงลำดับทั่วไปบางส่วน

1. ผสานการเรียงลำดับ

อัลกอริธึมนี้ทำงานโดยแยกอาร์เรย์ออกเป็นสองส่วนที่มีขนาดใกล้เคียงกัน จากนั้นแต่ละครึ่งจะถูกจัดเรียงและรวมเข้าด้วยกันโดยใช้ฟังก์ชันผสาน ()

นี่คือวิธีการทำงานของอัลกอริทึม:

MergeSort(arr[], l, r)

ถ้า r > l

1. แบ่งอาร์เรย์ออกเป็นสองส่วนเท่า ๆ กันโดยหาจุดกึ่งกลาง:

m กลาง = (l+r)/2

2. ใช้ฟังก์ชัน mergeSort เพื่อเรียกครึ่งแรก:

โทร mergeSort(arr, l, m)

3. โทร mergeSort สำหรับครึ่งหลัง:

โทร mergeSort(arr, m+1, r)

4. ใช้ฟังก์ชันผสาน () เพื่อรวมสองส่วนที่จัดเรียงไว้ในขั้นตอนที่ 2 และ 3:

รวมการโทร (arr, l, m, r)

ตรวจสอบภาพด้านล่างเพื่อให้ได้ภาพที่ชัดเจนเกี่ยวกับวิธีการทำงาน

แหล่งที่มา

โปรแกรม Python สำหรับการใช้งานการเรียงลำดับแบบผสาน

def mergeSort (a):

ถ้าเลน (a) >1:

กลาง = เลน (a)//2

A = a[:กลาง]

B = a[กลาง:]

ผสานการเรียงลำดับ (A)

ผสานการเรียงลำดับ (B)

ผม = j = k = 0

ในขณะที่ฉัน < len(A) และ j < len(B):

ถ้า A[i] < B[j]:

a[k] = เอ[i]

ผม+=1

อื่น:

a[k] = ข[j]

เจ+=1

k+=1

ในขณะที่ฉัน < len(A):

a[k] = เอ[i]

ผม+=1

k+=1

ในขณะที่ j < len(R):

a[k] = ข[j]

เจ+=1

k+=1

def printList(a):

สำหรับฉันอยู่ในช่วง (len (a)):

พิมพ์ (a[i],end=" “)

พิมพ์()

ถ้า __name__ == '__main__':

a = [12, 11, 13, 5, 6, 7]

ผสานการเรียงลำดับ (ก)

print(“เรียงลำดับอาร์เรย์คือ: “, end=”\n”)

printList(ก)

เรียนรู้เพิ่มเติม: การเรียกซ้ำในโครงสร้างข้อมูล: มันทำงานอย่างไร ประเภท & เมื่อใช้

2. การเรียงลำดับการเลือก

ในตอนแรกองค์ประกอบที่เล็กที่สุดจะถูกส่งไปยังตำแหน่งแรก

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

ดูภาพด้านล่างเพื่อทำความเข้าใจให้ดีขึ้น

แหล่งที่มา

โปรแกรม Python สำหรับการใช้งานการเรียงลำดับการเลือก

นำเข้าsys

X = [6, 25, 10, 28, 11]

สำหรับฉันอยู่ในช่วง (len(X)):

min_idx = ฉัน

สำหรับ j ในช่วง (i+1, len (X)):

ถ้า X[min_idx] > X[j]:

min_idx = j

X[i], X[min_idx] = X[min_idx], X[i]

พิมพ์ (“อาร์เรย์ที่เรียงลำดับคือ”)

สำหรับฉันอยู่ในช่วง (len(X)):

พิมพ์ (“%d” %X[i]),

การรับรองขั้นสูงของ Data Science, พันธมิตรจ้างงานมากกว่า 250 ราย, การเรียนรู้มากกว่า 300 ชั่วโมง, 0% EMI

3. เรียงลำดับฟอง

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

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

ตัวอย่าง :

อินพุต : 637124

ผ่านครั้งแรก

63 7124 -> 36 7124 : Bubble sort เปรียบเทียบ 6 กับ 3 และสลับกันเพราะ 3<6

3 67 124 -> 3 67 124 : ตั้งแต่ 6<7 ไม่มีการสับเปลี่ยน

36 71 24 -> 36 17 24 : สลับ 7 และ 1 เป็น 7>1

361 72 4 -> 361 27 4 : สลับ 2 และ 7 เป็น 2<7

3612 74 -> 3612 47 : สลับ 4 และ 7 เป็น 4<7

รอบสอง

36 1247 -> 36 1247

3 61 274 -> 3 16 274

31 62 74 -> 31 26 74

312 67 4 -> 312 67 4

3126 74 -> 3126 47

รอบที่สาม

31 2647 -> 13 2647

1 32 647 -> 1 23 647

12 36 47 -> 12 36 47

123 64 7 -> 123 46 7

1234 67 -> 1234 67

อย่างที่คุณเห็น เราได้ผลลัพธ์จากน้อยไปหามากหลังจากผ่านไปสามครั้ง

โปรแกรม Python สำหรับการจัดเรียงแบบฟองสบู่

def bubbleSort (a):

n = เลน (ก)

สำหรับฉันอยู่ในช่วง (n):

สำหรับ j ในช่วง (0, ni-1):

ถ้า a[j] > a[j+1] :

a[j], a[j+1] = a[j+1], a[j]

a = [64, 34, 25, 12, 22, 11, 90]

bubbleSort (ก)

พิมพ์ (“อาร์เรย์ที่เรียงลำดับคือ:”)

สำหรับฉันอยู่ในช่วง (len (a)):

พิมพ์ (“%d” %a[i]),

อ่านเพิ่มเติม: เฟรมข้อมูลใน Python: บทช่วยสอนเชิงลึกของ Python

บทสรุป

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

หากต้องการทราบข้อมูลเชิงลึกเพิ่มเติมเกี่ยวกับวิธีการจัดเรียง ติดต่อเราและเราจะช่วยคุณเริ่มต้นหลักสูตรที่เหมาะสมกับความต้องการของคุณมากที่สุด!

หากคุณอยากเรียนรู้เกี่ยวกับวิทยาศาสตร์ข้อมูล ลองดูโปรแกรม Executive PG ของ IIIT-B & upGrad ใน Data Science ซึ่งสร้างขึ้นสำหรับมืออาชีพที่ทำงานและมีกรณีศึกษาและโครงการมากกว่า 10 รายการ เวิร์กช็อปภาคปฏิบัติจริง การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม 1 -on-1 พร้อมที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ

ขอให้สนุกกับการเขียนโค้ด!