การเรียงข้อมูล (Sorting)

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

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

ประเภทของการจัดเรียงลำดับข้อมูล

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

1. การจัดเรียงลำดับภายใน (Internal Sorting) เป็นการจัดเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำ โดยข้อมูลเหล่านี้จะถูกเก็บอยู่ในโครงสร้างข้อมูลแบบอาร์เรย์ หรือลิงค์ลิสท์ ข้อมูลที่ทำการเรียงลำดับมีขนาดเล็กหรือจำนวนไม่มาก ซึ่งหน่วยความจำสามารถจะอ่านข้อมูลทั้งหมดขึ้นมาบนหน่วยความจำ และสามารถทำงานต่าง ๆ บนหน่วยความจำได้โดยไม่ต้องอาศัยสื่อบันทึกข้อมูล เช่น ดิสก์ หรือ เทป มาช่วยในการทำงาน

2. การจัดเรียงลำดับภายนอก (External Sorting) เป็นการจัดเรียงลำดับข้อมูลที่เก็บอยู่ในสื่อบันทึกข้อมูล โดยทั่วไปข้อมูลที่บันทึกนี้ มักมีจำนวนมากจนไม่สามารถจะเก็บเอาไว้ในหน่วยความจำได้ทั้งหมด ต้องแบ่งออกเป็นส่วนย่อย ๆ แล้วจึงนำมาจัดเรียงในหน่วยความจำ จากนั้นจึงทำการบันทึกกลับลงไปในสื่อสำหรับบันทึกข้อมูลเป็นส่วน ๆ ต่อจากนั้นนำส่วนต่าง ๆ ที่จัดเรียงลำดับเรียบร้อยแล้วมาทำการรวมเข้าด้วยกัน (Merge) สำหรับการเรียงแบบภายนอกนั้น จะต้องคิดถึงเวลาที่สูญเสียไปอันเนื่องจากการถ่ายเทข้อมูลระหว่างเทปหรือดิสก์ กับหน่วยความจำหลักด้วย เวลาที่สุญเสียไปในการถ่ายเทข้อมูลระหว่างหน่วยความจำหลักกับเทป หรือดิสก์จะเป็นตัวระบุความดีเลวของแบบการคำนวณแบบเรียงภายนอก

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

วิธีการต่าง ๆ สำหรับการจัดเรียงลำดับข้อมูล

วิธีการในการจัดเรียงลำดับข้อมูลภายใน ได้แก่

1. การจัดเรียงลำดับข้อมูลแบบ Bubble Sort

2. การจัดเรียงลำดับข้อมูลแบบ Selection Sort

3. การจัดเรียงลำดับข้อมูลแบบ Insertion Sort

4. การจัดเรียงลำดับข้อมูลแบบ Quick Sort

5. การจัดเรียงลำดับข้อมูลแบบ Shell Sort

6. การจัดเรียงลำดับข้อมูลแบบ Heap Sort

7. การจัดเรียงลำดับข้อมูลแบบ Radix Sort

วิธีการในการจัดเรียงลำดับข้อมูลภายนอก ได้แก่

1. การจัดเรียงลำดับข้อมูลแบบ Merge Sort

2. การ Run List

3. การเรียงข้อมูลบนดิสก์

4. การเรียงข้อมูลบนเทป

การจัดเรียงข้อมูลแบบ Bubble Sort

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

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

Unsorted	รอบที่ 1 เปรียบเทียบทั้งหมด 9 ครั้ง	รอบที่ 2 เปรียบเทียบทั้งหมด 8 ครั้ง
36	36 36 36 36 36 36 36 36 5	5 5 5 5 5 5 5 5
27	27 27 27 27 27 27 27 5 36	36 36 36 36 36 36 36 9
23	23 23 23 23 23 23 5 27 27	27 27 27 27 27 27 9 36
33	33 33 33 33 33 5 23 23 23	23 23 23 23 23 9 27 27
32	32 32 32 32 5 33 33 33 33	33 33 33 33 9 33 33 33
18	18 18 18 5 32 32 32 32 32	32 32 32 9 33 33 33 33
5	5 5 5 18 18 18 18 18 18	18 18 9 32 32 32 32 32
13	13 9 9 9 9 9 9 9 9	9 9 18 9 32 32 32 32
9	9 13 13 13 13 13 13 13 13	10 10 10 10 10 10 10 10
10	10 10 10 10 10 10 10 10 10	13 13 13 13 13 13 13 13

List 2	รอบที่ 3 เปรียบเทียบ 7 ครั้ง			รอบที่ 4 เปรียบเทียบ 6 ครั้ง			รอบที่ 5 = 5 ครั้ง
5	5 5 5 5 5 5 5			5 5 5 5 5 5			5 5 5 5 5
9	9 9 9 9 9 9 9			9 9 9 9 9 9			9 9 9 9 9
36	36 36 36 36 36 36 10			10 10 10 10 10 10			10 10 10 10 10
27	27 27 27 27 27 10 36			36 36 36 36 36 13			13 13 13 13 13
23	23 23 23 23 10 27 27			27 27 27 27 13 36			36 36 36 36 18
33	33 33 33 10 23 23 23			23 23 23 13 27 27			27 27 27 18 36
32	32 32 10 33 33 33 33			33 33 13 23 23 23			23 23 18 2 7 27
18	18 10 32 32 32 32 32			32 13 33 33 33 33			33 18 23 23 23
10	10 18 18 18 18 18 18			13 32 32 32 32 32			18 33 33 33 33
13	13 13 13 13 13 13 13			18 18 18 18 18 18			32 32 32 32 32
List 5		รอบที่ 6 = 4 ครั้ง	รอบที่ 7 = 3		8 = 2	9 = 1
5		5 5 5 5	5 5 5		5 5	5
9		9 9 9 9	9 9 9		9 9	9
10		10 10 10 10	10 10 10		10 10	10
13		13 13 13 13	13 13 13		13 13	13
18		18 18 18 18	18 18 18		18 18	18
36		36 36 36 23	23 23 23		23 23	23
27		27 27 23 36	36 27 27		27 27	27
23		23 23 27 27	27 36 36		36 32	32
33		32 32 32 32	32 32 32		32 36	33
32		33 33 33 33	33 33 33		33 33	36

จะเห็นได้ว่าข้อมูลมีการสลับที่กันไปเรื่อย ๆ จนได้ข้อมูลที่มีการเรียงลำดับเป็นที่เรียบร้อยแล้ว ซึ่งมีการจัดเรียง n - 1 รอบ โดยในแต่ละรอบจะมีการเปรียบเทียบคีย์เป็น n - 1, n - 2, n - 3,….,3 ,2,1 ดังนั้น จำนวนการเปรียบเทียบทั้งหมดจะเป็น

1+2+3+…+(n - 2) + (n - 1) = n(n - 1)/2

= (n ² - n)/2

จากตัวอย่างเมื่อแทนในสูตรจะได้ = (10 ² - 10)/2

= (100 - 10)/2

= 90/2

= 45

Algorithm BUBBLE

เพื่อใช้ในการจัดเรียงข้อมูลในอาร์เรย์ A จากน้อยไปหามาก โดยที่

N แทน จำนวนข้อมูลทั้งหมด

I แทน ตัวแปรนับรอบ

J แทน ตัวแปรนับรอบ

TEMP แทน ตัวแปรสำรองเพื่อเก็บค่าข้อมูล

1. [ทำสิ่งต่อไปนี้ซ้ำ ๆ จนถึงข้อ 3. โดยที่ตัวแปร I เริ่มจาก 2 จนถึง N โดยเพิ่มค่าขึ้นครั้งละ 1]

REPEAT THRU STEP 3. FOR I = 2 TO N STEP 1

2. [ทำสิ่งต่อไปนี้ซ้ำ ๆ จนถึงข้อ 3. โดยที่ตัวแปร J เริ่มจาก N จนถึง I โดยลดค่าลงครั้งละ 1]

REPEAT THRU STEP 3. FOR J = N TO I STEP -1

3. [เปรียบเทียบข้อมูล]

IF A[J] < A[J-1] THEN

TEMP = A[J]

A[J] = A[J-1]

A[J-1] = TEMP

ENDIF

4. [จบการทำงาน]

EXIT

การจัดเรียงข้อมูลแบบ Selection Sort

การจัดเรียงข้อมูลวิธีการนี้เป็นวิธีการที่ง่ายที่สุด โดยเริ่มจาก

1. เลือกค่าของข้อมูลที่มีค่าน้อยที่สุด

2. นำมาแลกเปลี่ยนกับค่าในตำแหน่งแรกสุดของกลุ่ม A(1)

หลังจากนั้นก็กระทำตามหลักการทั้ง 2 กับข้อมูลที่เหลือ คือในครั้งที่ 2 ค่า A(2) จะถูกแลกเปลี่ยนกับค่าที่เลือกแล้ว

ว่าน้อยที่สุดในลิสท์ A(2)…A(N) และในครั้งที่ 3 ค่า A(3) จะถูกแลกเปลี่ยนกับค่าที่เลือกแล้วว่าน้อยที่สุดในลิสท์ A(3)…A(N) และเรื่อยไปจนกระทั่งเหลือข้อมูลที่จะเปรียบเทียบแค่ 2 ค่าคือ A(N-1) และ A(N) ดังนั้น จำนวนรอบในการกระทำเป็น n-1 รอบ

ข้อมูลเดิม

I = 1

I = 2

I = 3

I = 4

I = 5

I = 6

I = 7

I = 8

I = 9

I = 10

I = 11

I = 12

Algorithm SELECTION

เพื่อใช้ในการจัดเรียงข้อมูลในอาร์เรย์ A จากน้อยไปหามาก โดยที่

N แทน จำนวนข้อมูลทั้งหมด

I แทน ตัวแปรนับรอบ

J แทน ตัวแปรนับรอบ

MIN แทน ตัวแปรที่เก็บตำแหน่งของข้อมูลที่มีค่าที่น้อยที่สุด

TEMP แทน ตัวแปรสำรองเพื่อเก็บค่าข้อมูล

1. [ทำสิ่งต่อไปนี้ซ้ำ ๆ จนถึงข้อ 5. โดยที่ตัวแปร I เริ่มจาก จนถึง N-1 โดยเพิ่มค่าขึ้นครั้งละ 1]

REPEAT THRU STEP 5. FOR I = 1 TO N-1 STEP 1

2. [กำหนดค่าเริ่มต้นให้ตัวแปร MIN โดยให้]

MIN = I

3. [ทำสิ่งต่อไปนี้ซ้า ๆ จนถึงข้อ 4. โดยที่ตัวแปร J เริ่มจาก I + 1 จนถึง N โดยเพิ่มค่าขึ้นค่าลงครั้งละ]

REPEAT THRU STEP 4. FOR J = I + 1 TO N STEP 1

4. [เปรียบเทียบข้อมูล]

IF A[J] < A[MIN] THEN

MIN = J

ENDIF

5. [ทำการสลับตำแหน่งของข้อมูลตัวที่มีค่าน้อยที่สุด กับตัวปัจจุบัน]

TEMP = A[I]

A[I] = A[MIN]

A[MIN] = TEMP

6. [จบการทำงาน]

EXIT

การเรียงลำดับข้อมูลแบบ Selection Sort มีการจัดเรียงทั้งหมด n - 1 รอบ โดยในแต่ละรอบจะมีการเปรียบเทียบคีย์ ดังนี้

รอบที่ 1 จำนวนการเปรียบเทียบทั้งหมดจะเป็น n - 1 ครั้ง

รอบที่ 2 จำนวนการเปรียบเทียบทั้งหมดจะเป็น n - 2 ครั้ง

รอบที่ 3 จำนวนการเปรียบเทียบทั้งหมดจะเป็น n - 3 ครั้ง

รอบที่ n - 2 จำนวนการเปรียบเทียบทั้งหมดจะเป็น 2 ครั้ง

รอบที่ n - 1 จำนวนการเปรียบเทียบทั้งหมดจะเป็น 1 ครั้ง

ดังนั้น จำนวนการเปรียบเทียบทั้งหมดจะเป็น

1+2+3+…+(n-2)+(n-1 = n(n-1)/2

= (n ² - n)/2

บอร์ด นี้ มีสาระ

Thursday, March 7, 2013

การเรียงลำดับข้อมูล(Sorting)

ประเภทของการจัดเรียงลำดับข้อมูล

วิธีการต่าง ๆ สำหรับการจัดเรียงลำดับข้อมูล

วิธีการในการจัดเรียงลำดับข้อมูลภายใน ได้แก่

วิธีการในการจัดเรียงลำดับข้อมูลภายนอก ได้แก่

Algorithm BUBBLE

No comments:

Post a Comment