การแปลงต นไม ท วไปเป นแบบ ไบนาร ม ก ข นตอน

คอรด หนึ่งซํ้า เดมิ อยใู นตําแหนงที่ 5 แตหลงั จากเรคอรด เรียงลาํ ดับแลว เรคอรดหมายเลข 14 ที่ 1 จะไป

อยูห ลงั เรคอรดคีย หมายเลขที่ 5 ผลลพั ธคลาดเคล่อื นของตําแหนงเรคอรดทม่ี ีคียซา้ํ กันนี้เปน ผลมากจากการ

ใชจดั เรียงลําดับทีไ่ มคงท่ี อน่ึง ในบางกรณีลักษณะคงท่ี (Stable) ไมจ ําเปนเพราะความสําคัญอะไร แตใ น

บางกรณีลาํ ดับท่ีกอนหลงั ของเรคอรด ท่ีมคี ยี ซ าํ้ กันอาจเปนสําคญั และจาํ เปนจะตองเลือกใช วธิ กี ารจดั

เรียงลาํ ดับทคี่ งท่ี

ตวั อยางโปรแกรมการทํางานของ Selection Sort void selectionSort(int numbers[], int array_size) { int i, j; int min, temp;

for (i = 0; i < array_size-1; i++) { min = i; for (j = i+1; j < array_size; j++) {

if (numbers[j] < numbers[min]) min = j; } temp = numbers[i]; numbers[i] = numbers[min]; numbers[min] = temp; } }

7.2 การจดั เรียงลาํ ดบั แบบ Insertion sort เทคนคิ พื้นฐานในการจัดเรียงลําดับเรคอรด อีกวธิ หี น่ึง คือเทคนิคการแทรกเรคอรด ซึ่งใชว ธิ ีการอาน

คา ขอมลู มาแลวแทรกจดั หาลําดับเรคอรด ตามตาํ แหนงทีเ่ หมาะสม วิธกี ารน้ีเปนเทคนิคที่ไดพัฒนาตอจาก เทคนิคแบบ Selection Sort คือแตละทีจ่ ะตองรอจนอานครบทกุ เรคอรดกอนจงึ จะเริม่ จัดเรียงลาํ ดับ (แบบ Selection) เราใชวธิ กี ารจดั เรยี งลาํ ดับไปเรอื่ ย ๆ ตามท่แี ตละเรคอรดถกู อา นเขามา (แบบ Insertion) หากจะ

Data Structure & Algorithm

เปรยี บเทยี บกบั การเลนไพ เราหยับไพแตล ะใบเขามาแลว จดั เรียงไพไปเรื่อย ๆ เราใชเทคนคิ การแทรกไพ (เรยี งตามเลขมากนอยตามลําดบั ) แตถา เรารอจนแจกไพห มดแลวหยบิ เขามาในมือแลวจึงจดั เรยี ง เรากใ็ ช เทคนคิ การเลอื กเรียงไพ

ตัวอยา งเชน เรามตี วั เลขทัง้ หมดทย่ี งั ไมไดเ รยี งลําดับอยดู ังนี้

14 3 22 9 10 14 2 7 25 6

ในรอบแรกเราอา นคา เรคอรด ที่ 1 คือหมายเลข 14 ดงั น้ันผลลัพธในรายการทีจ่ ะจัดเรียงลาํ ดบั ก็คือ 14

3 22 9 10 14 2 7 25 6 14 Unsorted List Sorted List

ในรอบท่ี 2 อา นเลข 3 เขา มา แลว นาํ ไปจัดเรยี งลาํ ดบั ใน Sorted List จะไดผลคอื

22 9 10 14 2 7 25 6 3 14 Unsorted List Sorted List

หลังจากรอบท่ี 6 ผลลพั ธค ือ

2 7 25 6 3 9 10 14 22

Unsorted List Sorted List

การดําเนนิ การสอดแทรกรายการจาก Unsorted List เขาไปใน Sorted List จะดาํ เนินการ

ตอ ไปจนหมดเรคอรดใน Unsorted List

อลั กอริทึมที่ 1 จะแสดงเทคนิคการจดั เรียงลาํ ดับเรคอรด แบบ Insertion Sort โดยจะเรยี งเรคอรด

ท้งั หมดจํานวน n เรคอรด อนึง่ การจดั เรียงเรคอรด แบบน้ี จะไดผลลพั ธเ ปน แบบคงท่ี

Insertion Sort void insort(record a[], int n) { int i,j; record memo; for(i=1; i<n; i++)

Data Structure & Algorithm

{ /* now a[0],a[1],...,a[i-1] is sorted */ memo=a[i]; for(j=i-1; j>=0; j--)

{ /* now a[0],a[1],...,a[j],a[j+2],...a[i] is sorted

and a[j+1] may be overwritten */ if(cmp(&a[j], &memo)>0)

a[j+1]=a[j]; /* now a[0],a[1],...,a[j-1],a[j+1],...a[i] is sorted

and a[j] may be overwritten */ else break; } /* now a[0],a[1],...,a[j],a[j+2],...a[i] is sorted and a[j+1] may be overwritten */ a[j+1]=memo; /* now a[0],a[1],...,a[i] is sorted */ } }

7.3 การเรียงแบบ Bubble sort ตัวอยา งการเปรยี บเทยี บอยา งงายของชุดขอมลู 10 เรคอรด (เรคอรดละ 1 ตัวเลข) ท่ียงั ไมได

เรียงลาํ ดับ ดังน้ี 512889

รูปท่ี 7.1 การเรียงแบบ bubble sort

ชนั้ แรกใหน าํ เอา 5 เปรยี บเทยี บกับ 1 ปรากฏวา 5 และ 1 เรียงลําดบั ตามท่ีเราตองการอยแู ลว จากนนั้ ใหน ําเอา 1 เปรยี บเทียบกับตวั ถัดไปคือ 2 เนื่องจาก 2 มากกวา 1 และ 2 อยู ในตาํ แหนงท่ผี ดิ ลาํ ดับ จงึ ใหแ ลกที่กบั 1 หลงั จากท่ี 2 ไปอยใู นตําแหนงที่อยเู ดมิ ของ 1 (นัน่ คือ ตาํ แหนง ท่ี 2) แลว ก็ให 2 เปรียบเทยี บกับคาในตาํ แหนงที่ 1 คือ 5 ปรากฏอยูในลําดบั ทถี่ กู ตอ งกไ็ มต องแลกทกี่ นั ตอมานํา 1 ไป

Data Structure & Algorithm

เปรียบเทียบกบั 8 แลวทาํ ในลกั ษณะเดมิ คา 8 จะคอยๆ ลอย ข้นึ ไปอยูในตาํ แหนงทีถ่ ูกตอ ง ในทสี่ ุดก็นาํ 1 ไปเปรยี บเทียบกบั 9 เลข 9 จะคอย ๆ ลอยข้ึน ไปยงั ตําแหนง ท่ถี กู ตอ ง

วิธีการแบบ Bubble Sort และวธิ ีการ Sort แบบอนื่ ๆ ท่ีไดกลา วมาแลวทั้งหมดเปนวธิ กี ารที่งา ยตอ การเขยี นโปรแกรม แตการดําเนินการจะชกั ชาเสยี เวลามากเพราะตองไลเ ปรยี บเทยี บไปทีละคู โดยปกตแิ ลว มกั จะไมเ ปนท่นี ิยมใช เทคนิคการจัดเรยี งลําดบั แบบอนื่ ๆ ท่ีจะไดกลาวตอไปจะเปน เทคนิคทที่ าํ งานไดเร็วกวา และมปี ระสทิ ธิภาพกวามาก

ตัวอยางโปรแกรมในการเรียงขอ มลู แบบ Bubble Sort void BubbleSort()

{ int A[n], x, y; for(x = 0; x < n; x++) for(y = 0; y < n-1; y++) if(A[y] > A[y+1]){ swap(A[y], A[y+1]); } }

7.4 การจัดเรียงลาํ ดบั แบบ Quick Sort วิธีการที่ทํางานไดผลอยา งมีประสทิ ธภิ าพมากกวา Exchange Sort คือวิธีการแบบ Partition-

exchange Sort หรือท่ีเรียกวา Quick Sort วิธกี ารนีไ้ ดร บั การพัฒนาโดย C.A.R. Hoare ในป 1962 แนวความคิดพ้นื ฐานของการจัดเรยี งลําดบั แบบนี้ คอื ใชผ ลของการเปรียบเทยี บในรอบหนึ่งเปน

ตัวกาํ หนดเง่ือนไขในการเปรียบเทยี บครั้งตอไปตามลาํ ดบั ในกระบวนการเปรยี บเทยี บจะทําใหเกดิ ผลลพั ธ แบงแยกเปน 2 สว น (partition) โดยยา ยคาของชุดขอมลู ทาํ ใหดานหน่ึงจะมคี าของชุดขอมลู ท่ีมคี าสูงกวา คา ของคยี ที่กําหนดในขณะท่อี ีกดานหนึ่งมคี าตํ่ากวา

ลองพจิ ารณาตวั อยา งของชดุ ขอมลู ทีย่ ังไมไ ดจดั เรียงลาํ ดบั ดงั นี้

6 25 7 2 14 10 9 2 3 14 จุดมุง หมายของการเปรยี บเทียบจะแบงแยกคา ของขอมูลออกเปน 2 ดาน คา ท่สี ูงกวาใหด า นลาง และต่ํากวาไวดา นบนของรายการ เรมิ่ ตนดวยการเปรียบเทียบเลข 6 กับ 14 ผลลพั ธคือ ไมต องแลกคา เพราะ 6 (คาตา่ํ ) อยดู า นบน และ 14 (คาสูงอยูดา นลา งอยแู ลว การเปรียบเทียบถดั ไปจะเปน การ

Data Structure & Algorithm

เปรยี บเทียบ 6 กับ 3 ผลลพั ธคอื เอา 3 ยายไปดา นบน เลข 6 ยายไปดา นลา ง ถดั ไปเปรยี บเทียบ 25 กับ จะไดวาเลข 6 ถูกยายขึ้นบน 25 ถกู ยา ยลงลาง ตอ มา 6 จะถูกเปรยี บเทียบกับ 22 , 9, 10, 14 ตามลําดับ ผลลัพธค ือทกุ ตวั คงอยูต าํ แหนงเดิมจนถึง 6 กบั จะไดว า 2 ถกู ยา ยขน้ึ บน 6 ลงลาง การเปรียบเทยี บคร้ัง สดุ ทาย คือ กับ 6 จึงเกดิ ผลลัพธสลับคา ยา ยตาํ แหนง กัน ตรงจดุ นถี้ ือวาเปนการส้ินการยาย คา ในรอบแรกทั้งหมด สรปุ ไดผลลพั ธเ ปน คร่ึงบนเลขต้ังตนในรอบน้ี ( เลข 6 ) มีคาคือ 3, 2, 6 สว น ครึง่ ลางมี 7 คา คือ 7, 14, 10, 9, 22, 25, 14

333

25 3 25 25 7 2 77 7 14 10 22 2 9 22 14 14 14 3 14 10 10 10

99 9

22 22 22

14 14 14

รปู ที่ 7.2 การจัดเรยี งลาํ ดบั เรคอรด แบบ Quick Sort เมอ่ื จบรอบแลว จะเร่มิ ตนทาํ การเปรยี บเทียบสลบั คาไปมาโดยใชตรรกแบบเดิมของสวนคร่ึงบน และ สวนครง่ึ ลา งไปเรอ่ื ย ๆ ตามลําดบั เชน สว นคร่งึ ลางจะเรมิ่ ตนดว ยเลขต้ังตนท่ีเลข 7 แลวจะสลบั คายา ยไปมา ใหเลขท่ีต่ํากวา 7 ไวดานหนา สูงกวา 7 ไวอกี ดา นหน่ึง และจําทาํ การเปรยี บเทยี บเชนนี้ในสวนครึง่ บนและ ครงึ่ ลา งของเลข 7 อีกตอ ๆ ไป น้ันคอื เราจะแบงสวนของขอมลู ออกเปน สวนยอยๆ บนลางไปตามลําดบั จน ทุกคา ไดร บั การจดั เรยี งเรียบรอยแลว อน่ึง เมื่อสว นยอย ๆ มีขนาดเลก็ ลง ผเู ขียนโปรแกรมอาจจะเลอื กใช วธิ กี ารจดั เรียงลาํ ดบั วธิ อี ื่นๆ ที่งา ยกวา เขามาใชร ว มกบั วธิ ี Quick Sort ได นอกจากนยี้ งั มีเทคนิคการแบงสวนชุดขอ มลู เปน ดา นคาสูงและคาตํา่ อีกวิธีการหน่ึง ซง่ึ จะเลยี นแบบ วิธกี ารที่คนทั่วไปใชในการจดั เรยี งลําดบั ขอ มูล คอื การแบงชุดขอมลู ออกเปน “กอง (piles)” และจะแบงเปน กองยอยๆ ตอไปตามลําดับ ในการแบง กองของขอมูลดวยเทคนคิ ของ Quick Sort แบบนี้ จะเริ่มตนดว ย การคํานวณหาจดุ กงึ่ กลางของขอมลู (mid – point) แลวจะจดั เอาขอมลู ที่มีคาตาํ่ กวา จุดก่งึ กลางไวทด่ี า นหนึง่ ของชดุ ขอมลู และที่มีคา สูงกวาไวใ นอีกดา นหน่งึ และจะหาจดุ กึ่งกลางของขอมลู แตล ะดา นจดั แบงเปน กลุม ยอ ยๆ ทําวนเวียนไปจนทุกขอมูลอยใู นลําดับท่ตี อ งการ ลองพิจารณาตัวอยา งชุดขอ มูล 10 เรคอรด (ตวั เลข) ซ่งึ ยังไมไดเ รยี งลาํ ดับตอไปน้ี

Data Structure & Algorithm

86 3 10 23 12 67 59 47 31 24

ในรอบแรก จุดกึง่ กลางของคาขอ มูลคือ 55 (ไดจาก (86+24)/2) หลังจากนั้นขอมูลทีม่ ีคาตํ่ากวา 55 จะถูกยายไปดา นหนึ่ง ( 24-47 ) และที่มากกวา 55 จะอยใู นอีกดานหน่งึ (59-86) ในรอบท่ี 2 จดุ กึ่งกลาง ขอ มูลของคร่ึงแรกจะมีคาเทากับ 35 (ไดจ าก(24+47)/2) และจะแบงสลบั ขอ มลู ยอ ยได 2 ดาน ดานตาํ่ กวา 35 คอื 24-31 และดานสงู กวาคอื 47 ) และจะใชตรรกเดิมเชน นีว้ นเวียนรวม 10 รอบจนไดผ ลลัพธสดุ ทาย เปนทกุ เรคอรด ถูกจัดวางในตําแหนงทค่ี วรจะเปนจุดกง่ึ กลาง

ตาํ แหนงในอารเรยของขอมลู

รอบท่ี 1 2 3 4 5 6 7 8 9 10 1 55 86 3 10 23 12 67 59 47 31 24 2 35 24 3 10 23 12 31 47 59 67 86 3 27 24 3 10 23 12 31 47 59 67 86 4 18 24 3 10 23 12 31 47 59 67 86 5 11 12 3 10 23 24 31 47 59 67 86 6 6 10 3 12 23 24 31 47 59 67 86 7 23 3 10 12 23 24 31 47 59 67 86 8 72 3 10 12 23 24 31 47 59 67 86 9 63 3 10 12 23 24 31 47 59 67 86 10 3 10 12 23 24 31 47 59 67 86

รปู ท่ี 7.3 การจัดเรียงลาํ ดบั เรคอรดแบบ Quick Sort (midpoint)

7.5 การจัดเรียงลาํ ดับแบบ Heap Sort

วิธกี ารแบบ Quick Sort จะทาํ งานไดดีกวาเทคนิคการจดั เรยี งแบบเชงิ เสนตรง สวนเทคนิค Heap sort ตอ ไปนี้เปนวิธกี ารแบบไมเ สน ตรง และเทคนิคนจ้ี ะทํางานไดพอ ๆ กับ Quick Sort และอาจจะดีกวา ในหลายกรณีที่ขอมูลมคี วามซับซอนมาก ๆ แตอยา งไรกต็ าม การเขียนโปรแกรม Heap Sort กย็ งุ ยากกวา วิธี อ่นื ๆ ทีไ่ ดกลาวมาแลว เทคนิคของ Heap Sort นถ้ี กู พัฒนาในป 1964 โดย J.W.Williams

Data Structure & Algorithm

ในการดําเนนิ การของ Heap Sort เราจะกําหนดใชโครงสรางขอมูลแบบพิเศษของ Binary Trees ท่ี เรียกวาเปนโครงสรางแบบ Heap ซงึ่ จะมโี ครงสรา งเปนแบบตน ไม แตกเปน ก่ิงกานและใบไปตามลาํ ดบั ชน้ั ใน Heap ขนาด n ของ Binary Trees จะมีกิง่ กานและใบเปนจาํ นวน n โหนดการแตกก่งิ กานของโหนดจะอยู ภายใตเ ง่ือนไขตอไปน้ี

1. ทีท่ ุกระดบั ของ Heap จะแตกสาขาออกไปได 2 ทาง คือทางซายและทางขวา และจะตองมีโหนด ในระดบั บนครบ 2 ดานกอน จงึ จะแตกโหนดตอในระดบั ลางได อนงึ่ การแตกโหนดออกไปจะตองเร่มิ ทางดาน ซา ยกอ น จึงจะแตกไปดา นขวาตามลาํ ดบั

2. คาคยี ข องโหนดจะตองถูกจัดในลักษณะทว่ี าโหนดตวั บน (father-ตัวพอ จะตองมีคาคียส ูงกวา ของ โหนดลา ง (son-ตวั ลูก)

90 70

45 35 60 50

39 22 33 30 35 75 30 40

(ก) โครงสรา ง Heap (ข) ไมใชโ ครงสราง Heap

รปู ท่ี 7.4 การเปรยี บเทียบระหวางโครงสราง Heap กับโครงสรางอนื่

ในกระบวนการดําเนนิ การของ Heap Sort จะแบง ออกไดเ ปน 2 ลาํ ดบั ขน้ั ตอน คือ 1. การสรา ง Heap 2. การประมวลผลของขอ มลู ใน Heap ขน้ั ตอนการสราง Heap : ในขั้นตอนแรกของ Heap Sort เราจะตอ งจดั ชุดขอมูลที่มีอยูใหมี

ลักษณะโครงสรา งเปนแบบ Heap ขนาดของ Heap จะใหญข ้นึ เร่ือย ๆ เม่ือเราอา นขอ มูลแตละตัว (key) เขามาตามลําดบั การจัดเรียงลําดบั ของคียของโหนดตางๆ จะตอ งเปน ไปตามเงื่อนไข 2 ประการท่ีไดกลา ว มาแลว ตรรกทีใ่ ชในการจัดการคอื เมื่ออา นคา คยี เ ขา มาแตล ะตัว คาของคูคยี จะถูกเปรยี บเทียบกัน ถา คยี ม ีคาสูง กวา จะถูกสลับคาไปเปนตวั พอ และอีกตัวหนึ่งที่คาตา่ํ กวาจะถกู ยายมาเปนตัวลกู คา ของแตล ะคียใน

Data Structure & Algorithm

กงิ่ กานสาขาตางๆ ของ Heap ที่ขนาด I (I เปน ขนาดของ Heap มีคาตง้ั แต Heap ขนาด 1 ถึงขนาด n โหนด )

ข้ันที่ 1 : ใหเ ปรียบเทียบโหนดท่เี ขา ใหมก บั โหนดทเ่ี ปนพอ IF Knew > KFATHER THEN แลกท่ีกนั เล่ือน I ไปชย้ี งั ตําแหนง FATHER (น่ันคือ I ตดิ ตาม

Knew ขนึ้ ไป ) ขัน้ ท่ี 2 : ทําขน้ั ท่ี 1 เรื่อย ๆ จนทาํ ไมได

ผลลพั ธท ไี่ ดใ นข้ันตอนแรกของการสราง Heap ยงั ไมไดถ ูกจัดเรยี งลําดบั ตามความตองการเปนแตจดั โครงสรางของตน ไมขึ้นมาเทานัน้ ในขนั้ ตอนท่ี 2 นีจ้ ะเปนการปรับโครงสรางท่ีไดใหม โี ครงสรา งที่เปนการจัด เรียงลาํ ดบั ขอ มลู โดยท่ีจะทํายอนกลับการสรา ง Heap โดยทําจาก Heap ขนาด 10 ยอนกลบั ไปยัง Heap ขนาด 1

โดยอาศยั แนวความคิดทีว่ า ขอมูลใน Heap ยังคงจัดใหมีลักษณะโครงสรางแบบอารเรยไ ดดังนน้ั เรา จะยา ยโครงสรา งกลบั คือเปลี่ยนแลกตาํ แหนง จากโหนดบนคยี  [1] ใหก ลายเปนโหนดลา งสุด คอื คีย [n] แลวปรับโครงสรางของ Heap ท่ีเรยี งตามลําดบั จนกลายเปน วาคีย [1] คอื คาตํา่ สุด และคยี  [n] คือ คาสูงสดุ

void perc_down(input_type a[], int i, int n) { int child; input_type tmp; for (tmp=a[i]; i*2 <= n; i=child) { child = i*2; if ((child != n) && (a[child+1] > a[child])) child++; if (tmp < a[child])

a[i] = a[child]; else break; } a[i] = tmp; }

void heapsort(input_type a[], int n) { int i, j;

Data Structure & Algorithm

100

j = n; for (i=n/2; i>0; i--) /* BuildHeap */ perc_down(a,i,j); i = 1; for (j=n; j>=2; j--) { swap(&a[i],&a[j]); /* DeleteMax */ perc_down(a,i,j-1); } }

7.6 การจดั เรยี งขอ มลู แบบ Tournament Sort การจัดเรยี งลาํ ดับขอมลู โดยใชหลักการของตน ไมอีกเทคนคิ หนง่ึ คอื Tournament Sort หรือบางที

เรียกวา Tree – selection Sort เทคนิคนี้ไดร ับการพัฒนาโดย E.H.iend (1956) วธิ ีการของเทคนิคนเี้ ปน ลักษณะคลายการจดั สายการแขง ขันกฬี าแบบแพค ัดออกไปตามลําดบั โดยจะทําการเปรยี บเทียบคแู ขง ขันทีละ คจู นกระทงั่ ไดผูชนะในขนั้ สดุ ทา ย

วิธีการจดั เรียงลําดับแบบ Tournament ดูจะเปนวิธกี ารทม่ี ผี ูนิยมใชมากกวาเทคนคิ การจัด เรยี งลาํ ดบั แบบ Internal อน่ื ๆ ท้ังหมด โปรแกรมสําเรจ็ รูปท่สี รางขนึ้ ใชใ นการจดั เรยี งลําดบั ขอมลู ก็มักจะ ประยุกตใ ชเ ทคนคิ น้ีกันเปนหลกั

ลองพิจารณาตัวอยา งของชุดขอ มูลทยี่ ังไมไดจดั เรยี งลาํ ดับ 15 คียต อ ไปนี้ 6 25 7 2 14 10 9 22 3 14 8 12 1 30 13

เพ่ือแสดงเปนตวั อยาง สมมติวา สามารถอา นคา เขาเก็บไวใ นหนว ยความจาํ เพียงครั้งละ 4 คา ดงั นัน้ การจดั การเปรียบเทยี บจะเร่ิมตนดว ยการสรางเปน คเู ปรยี บแบบ 2 คู คอื 6 กับ 25 และ 7 กบั 2 ในคูแรกผู ชนะคอื เลข 6 (เพราะมีคาตาํ่ กวา ) และในคูห ลักคือเลข 2 ดงั นั้นเมอื่ ผชู นะ 2 ทมี จาก 4 ทมี มาพบกัน จะได ผลลัพธรอบแรกวาเลข 2 คือผูชนะเลศิ ในรอบท่ี 1 น้ี แตการแขง ขนั ยังไมจบและไมไ ดม ผี ูเขามาแขงขนั เพยี งแค 4 ทีม ยังมีผเู ขา แขงขนั อ่ืนๆ อกี อยูอีกตามลาํ ดบั และจะใชนโยบายแบบคดั ออกไป แลวทดแทนเขา มา (Tree replacement-selection sort) ดงั นัน้ ในรอบถดั ไปเราจะอานเลขถัดไปคือเลข 14 เขามาแทนท่ีเลข 2 ทช่ี นะ ออกไปและเร่มิ ทาํ การเปรยี บเทยี บคแู ขง 4 ทมี ใหม วนเวยี นเชน น้ีไปตามลําดับ

เมอ่ื ถึงรอบท่ี 6 จะเกดิ มปี ญ หาข้นึ เพราะเลขท่ีอานเขามาแทนทเี่ ลขที่คดั ออกคือเลข 3 หากเอาเลข 3 เขารวมแขงขัน เลข 3 ก็จะเปนผูชนะเพราะมีคา ต่ํากวาเลขอ่ืนแตก จ็ ะทําใหลําดบั ที่ของผูเขา รอบชนะทผ่ี า น ๆ มาเสียไปหมด ดงั น้ัน ในการจัดการแขงขันเปรยี บเทยี บคาจึงมีขอกาํ หนดเอาไววา “ถาคยี เขา มาใหม < คียท ี่ เพิ่งออกไปใหกาํ หนดคยี ทเี่ ขามาใหมเ ปนคียท่ีขาดคณุ สมบตั ิที่จะลงแขง ขันชั่วคราว” (ในที่นีจ้ ะใส * เอาไว)

Data Structure & Algorithm

101

เลข 3 ไมไดล งแขง ขันดวย เลขอนื่ ๆ ก็จะเลน แขงขันเปรยี บเทียบกนั ตอไปตามปกติ รอบที่ 6 ถึง 9 จะอา นคา ใหมเขามาไลค าเกา ออกไปได และตดิ เงื่อนไขดงั กลาวไวทลี ะรอบตามลําดับ

ถึงรอบท่ี 10 ทุกคา (ทัง้ 4 คียทจี่ ะเปรยี บเทยี บ) ที่อา นเขามาจะตดิ เง่ือนไขหมดแลว จงึ ยกเลกิ เงื่อนไขดงั กลาวแลว เรมิ่ เปรียบเทียบใหมส รางเปน ชุดขอมลู เรยี งลาํ ดบั ชดุ ท่ี 2 ดงั นน้ั ในรอบที่ 10 จะเริ่มคู เปรยี บเทยี บคา ทเ่ี หลอื ใหมไปตามลาํ ดับ จนถึงรอบเริม่ จะหมดชุดขอมลู (ในทนี่ ้ใี สเปน เครือ่ งหมาย * ) และใน รอบที่ 14-15 เปน การเปรยี บเทียบตัวเลขทเ่ี หลือจนหมดชุดขอ มูลทงั้ หมดในรายการ ผลลพั ธสุดทาย คอื ตวั เลข ทถ่ี กู เรียงลาํ ดับแลว 2 ชุด

6 66 66 2=>2 25 25 25

7 7 2 72 2 2 2 (1) 2,6 66 6 => 2,6 66 25 25 6 = > 77 77 * 14 (2)

รูปท่ี 7.5 การจดั เรยี งลําดับขอมูลแบบ Tournament Sort เพอ่ื ใหไ ดผลลัพธเ ปนรายการชดุ ขอมลู ที่จัดเรียงลําดบั 1 ชุดขอมูล จะใชเทคนิคการเชื่อมชุดขอมูล 2 ชุด เขาดว ยกนั ดว ยวิธี Two-way Merge กลาวคือผา นคา ขอมลู แตละตัวจากแตล ะรายการมาเปรียบเทียบ กัน ตัวใดมคี า นอยกวา เขียนเก็บไวใ นชดุ ผลลัพธสุดทา ย (Merged list) แลว อา นคา ใหมจ ากรายการเดิมมา เปรยี บเทียบตอ ๆ ไปตามลาํ ดับ ในกรณีตัวอยางขางตน เปน ขัน้ ตอนการทํา Tournament Sort อยา งงายๆ มขี อมูลไมมากนัก และ เปรียบเทียบทีละ 2 คเู ปรียบเทียบ แตเ ราสามารถเขยี นโปรแกรมซับซอนข้ึน เปรยี บเทียบทีละหลายคูการ เปรยี บเทยี บก็ได

Data Structure & Algorithm

102

7.7 การเรียงขอมูลแบบ Merge Sort Merge sort เปนวิธกี ารเรยี งขอ มูลที่มีความสําคัญมาก เพราะเปน วธิ สี าํ คัญในการเรยี งขอมลู ขนาด

ใหญ (การเรียงแบบภายนอก) วธิ ีการเรียงจะเรม่ิ กระทําครงั้ ละ 2 คา ซ่งึ จะไดล สิ ตยอยจาํ นวน n/2 ลสิ ต แตล ะ ลิสตมี 2 คา จากน้นั จะทาํ การ merge sort ตออีกครงั้ ละ 2 ลิสต แลวจะไดล ิสตท่เี รียงแลว จํานวน n/4 ลิสต แตละลิสตมี 4 คา ทาํ เชน นี้ไปเรอื่ ยๆ จนในที่สุดจะทาํ การ merge sort 2 ลสิ ต สุดทายเขา ดว ยกัน จะไดล สิ ต ท่ีเรียงแลว ดังรปู

54 28 89 6

(4,5) (2,8) (8,9)

(2, 4, 5, 8) (6, 8, 9)

(2, 4, 5, 6, 8, 8, 9)

รปู ท่ี 7.6 การ Merge Sort

จะเหน็ ไดว า การทาํ Merge Sort ตองกระทาํ เปนจํานวน O (log2 n) เที่ยว และแตล ะเท่ียวทีท่ าํ การ Merge สามารถกระทําไดใน O (n) ดังน้นั เวลาในการเรียงขอมูลจะเปน O (n log2 n)

ตัวอยา งโปรแกรมของการเรยี งแบบ Merge Sort void mergeSort(int numbers[], int temp[], int array_size) { m_sort(numbers, temp, 0, array_size - 1); } void m_sort(int numbers[], int temp[], int left, int right) { int mid; if (right > left)

Data Structure & Algorithm

103

{ mid = (right + left) / 2; m_sort(numbers, temp, left, mid); m_sort(numbers, temp, mid+1, right); merge(numbers, temp, left, mid+1, right); } }

7.8 การเรียงขอ มูลแบบ Shell Sort โดยปกตกิ ารเรยี งขอ มลู แบบน้ีท่ีใชก ารเปรียบเทยี บประมาณ n log2 n จะตองมีกระบวนการและ

ข้นั ตอนท่ีพสิ ดารกวาการเรยี งขอมลู แบบท่ีใชก ารเปรียบเทยี บประมาณ n2 คร้งั แตถ า จาํ นวนขอมลู ทต่ี องเรียง มจี าํ นวนนอ ย หรือเกือบจะเรียงกนั อยูแลว การทาํ งานของแบบการคํานวณแบบ n2 นนั้ จะทํางานไดดีกวา การ เรยี งแบบ n log2 n การเรียงท่จี ะกลาวตอไปนี้ จะใชแ นวความคดิ จากเร่ืองนี้ น่ันคือแทนที่จะเรียงขอมลู ทง้ั ชดุ โดยตรง เราจะแบง ขอมลู ท้ังชุดหรอื คียท ่ีแทนขอมูลเหลา นี้ออกเปน สว นยอ ยๆ แลว เรยี งสว นยอย ๆ เหลา นั้น โดยใชอัลกอรทิ ึม n2 เชน Bubble Sort หรือ Insertion Sort

จากชุดคียที่กาํ หนดใหเ ราจะไมแ บงคยี ช ดุ นน้ั ออกเปน ลิสตย อยจริงๆ แตจะทาํ การแบงโดยกาํ หนดคาที่ จะอยใู นลิสตย อยหนึ่ง ๆ ดวยการกาํ หนดคา h เปน ระยะทางระหวางคา สองคาใด ๆ ในคียชุดนน้ั ทจี่ ะอยูใน ลิสตยอ ย อนง่ึ แตละลสิ ตย อยจะมคี ีย อยูประมาณ n/h คา จํานวนคยี ใ นลิสตยอ ยในแตละเทย่ี วที่ทําการเรยี ง จะไมเ ทากนั แตจ ะถกู กาํ หนดโดยคา h ตอ ไปนี้ ht, ht-1,…….., h1 โดยท่ีคา h1 = 1 เสมอ การเรยี งจะ ส้นิ สุดเม่อื ทําการเรยี งเปนจํานวน t เทยี่ ว การเลอื กคา hi วธิ ีการเลอื กคา hi มอี ยหู ลายแบบ สวนแบบทจี่ ะกลา วถึงในทีน่ ้ีมี 2 รปู แบบ คอื (1) ใหเลือก hi = 2i – 1 โดยทคี่ า I อยูร ะหวา งคา 1 และ (log2 n)

ถา เลอื ก hi โดยวิธีน้ี จาํ นวนครงั้ ที่ตองมีการเปรียบเทียบคีย จะเปน O (n3/2) ซงึ่ เปน กรณเี ลวรา ย ทส่ี ุด (2) ชดุ คา hi ทใี ชไดด ีอีกแบบหน่ึงกาํ หนดโดยสมการ สาํ หรับคา I อยูระหวา ง 1 และ t โดยท่ี t เปนคาจาํ นวนเต็มนอ ยทส่ี ุดท่ีสอดคลอ งกบั อสมการ ht+2  n

สมมติใหชดุ คยี ท่จี ะเรยี งมีดงั นี้

(37, 32, 14, 45, 92, 18, 19, 34, 31, 35,) เราจะเลอื กคา hi จากแบบ (1) ท่กี ลา วมาแลว เน่ืองจาก n = 10 เราจะไดว า (log2 10) = 3 ดงั น้ันคา I ทีใ่ ชค ือ 3, 2 และ 1 และจะได h3 = 7, h2 = 3, h1 = 1 ตามลาํ ดบั จากสมการ hi = 2i – 1

Data Structure & Algorithm

104

การเรียงเทย่ี วท่ี 1 h3 = 7

37 32 14 45 92 18 19 34 31 35

การเรยี งเทย่ี วที่ 1 จะมี 3 ลสิ ตยอย ดงั ที่แสดงโดยเสน ทโี ยงไว 3 ลสิ ตยอยนี้คอื (37, 34) (32, 31) (14, 35) หลังจากการเรยี งแตละลสิ ตยอยแลวจะไดชุดตัวเลขดังนี้

การเรียงเทีย่ วท่ี 2 h2 = 3 37 32 35 34 31 14 45 92 18 19

การเรยี งเทย่ี วนจ้ี ะประกอบดวย 3 ลิสต คอื (34, 45, 19, 35) (31, 92, 37) และ (14, 18,

หลงั จากการเรียงแตล ะลสิ ตย อ ยแลว จะได

19 31 14 34 37 18 35 92 32 45

การเรียงเที่ยวท่ี 3 h1 = 1

การเรยี งเท่ียวนี้จะประกอบดวยลสิ ตเพยี งลิสตเดยี ว นั่นคอื ทกุ คา ในลสิ ตน ้ี การเรียงเทากับการใช

insertion sort หรอื การเรียงแบบอื่น ๆ

19 31 14 34 37 18 35 92 32 45

เมอ่ื เรยี งแลวจะได

Data Structure & Algorithm

105 14 18 19 31 32 34 35 37 45 92 สังเกตดูขอมูลจากการเรยี งโดยวิธี Shell น้ี การเลือกคา hi อกี แบบทีม่ ีประโยชน (และงา ย) กค็ ือ ให hi = 1 แลว ให hi + 1 = 3hi + 1 และใหห ยดุ ที่ ht เมอ่ื ht + 2 มีคา มากกวา n

Data Structure & Algorithm

106

แบบฝก หัด

1. จงแสดงขัน้ ตอนในการเรยี งขอมลู สําหรับแตล ะวิธี โดยใชข อมูลที่กําหนดใหต อไปนี้ (1) Bubble Sort (มากไปหานอย) 634859827 (2) Insertion Sort (นอยไปหามาก) 634859827 (3) Heap Sort (นอยไปหามาก) 22 12 24 76 82 35 21 74 32 18 (4) Radix Sort (นอ ยไปหามาก) 3475 3476 3567 7476 7235 1346 7645 3674 7636 1345 5675 2456

2. จงบอกขอ ดี ขอเสียของการเรยี งลําดบั ขอมูลแตละประเภทตอไปน้ี (1) Bubble Sort (2) Selection Sort (3) Insertion Sort (4) Quick Sort (5) Shell Sort (6) Heap Sort (7) Radix Sort (8) Merge Sort

Data Structure & Algorithm

116

บทท่ี 8

การคนหาขอมลู (Searchintg)

8.1 บทบาทหนา ทีข่ องการคนหาขอ มูล การคนหาขอ มลู (Searching) เปนกระบวนการท่สี าํ คัญย่ิง ขอ มูลท่ีเก็บอยูในคอมพวิ เตอร

หลังจากผา นการประมวลผลหรือรวมเปน หมวดหมหู รอื แปลงเปนรูปแบบท่ตี องการแลว ยอมตองการนํา ขอ มลู เหลาน้ันออกมาใช นน่ั คือ การคน หาขอมลู (Searching) นงั่ เอง ขอมูลในแฟมขอมูลจะมีการจัดกลุม แบบเรคคอรด (Record) แตล ะเรคคอรดจะมีสว นทีเ่ รยี กวา คีย (key) ท่ีใชใ นการระบุ (ldentify) เรคค อรด คยี ห นง่ึ ๆ อาจจะประกอบไปดว ยฟลด (field) หนึง่ หรือมากหน่ึงฟลดข้ึนไป ซง่ึ การคน หา (Searching) ก็คือขบวนการทท่ี ําการคนหาแตละเรคคอรด โดยใชค าคยี  เพอื่ ใชใ นการคนหา ขอมลู ที่ ตองการ

อัลกอริทึมของการคนหา คือ อัลกอริทมึ ซง่ึ รับอารก วิ เมนต (argument) Q และพยายามหา ระเบยี นซง่ึ มีคีย (key) คอื a อลั กอริทมึ นี้ใหคา ของทั้งระเบียน หรอื ใหคา พอยนเ ตอรท ชี่ ้ีไปยงั ระเบยี น กรณีท่หี าคียไมพบ ก็จะใหผ ลลพั ธเ ปน ระเบียนนิล (nil record) หรอื นิล พอยนเตอร (nil pointer) การ คนหาทปี่ ระสพผลสาํ เรจ็ เรียกวา การคนคนื (retrieval) ในการคนหาขอมูล คยี ของระเบียน เปน สิ่งบอก ความแตกตา งของระเบยี น คียภ ายใน (Internal key) เปนคยี ท อ่ี ยภู ายใน ระเบียนทีต่ าํ แหนงซึง่ กําหนดไว จากจุดเรม่ิ ตนของระเบียน คียภ ายนอก (Exteral key) เปนคียท ่เี กบ็ ไวในตารางของคียซึ่ง รวมถึงพอยน เตอรซึง่ ชไ้ี ปยังระเบียน คียปฐมภูม(ิ Primary key) เปนคยี ซึ่งมเี อกลักษณ (unique) ซง่ึ แตละระเบยี นจะมี คยี ไ มซํ้ากนั ดรรชนขี องแถวลําดบั เปน คยี ภ ายนอกท่ีมีลกั ษณะเฉพาะ (unique external key) สาํ หรับ คยี ทตุ ิยภูมิ (Secondary key) เปน คียของระเบยี นท่ีไมเปนเอกลกั ษณ ไดแก 2 ระเบยี นมคี ียต วั เดยี วกนั เชน คยี ช ่อื จงั หวัด ในระเบียนของท่ีอยู

การคนหาถือวาเปน สง่ิ สาํ คัญในการประมวลผลขอมูลดว ยคอมพวิ เตอร การคนหาจะมคี วาม รวดเร็วหรือไมน ั้นขึน้ อยูกบั อัลกอริทึมของการคนหา และอัลกอรทิ ึมทใี่ ชก ็ข้ึนอยูกบั ลกั ษณะการเก็บขอมลู อกี ตอหนึ่ง โครงสรา งขอมลู ท่ีจะใชเ ปน ตัวบงบอกถงึ อลั กอริทมึ ทใ่ี ชคน หาขอมูลโดยตรงในกรณีที่ตารางนนั้ เกบ็ อยใู นหนว ยความจําหลกั (Main Memory) ทั้งหมด การคน หาขอมลู จะชาหรือเร็วข้นึ อยูกับจาํ นวน ครงั้ ท่ีตองทาํ การเปรียบเทียบ สวนในกรณที ่ีตารางท่ีใชใหญมากจนไมสามารถบรรจุอยูใ นหนว ยความจาํ หลกั ไดหมด ตารางสว นหน่ึงตองเก็บไวในหนวยความจําสาํ รอง (Secondary Storage) ในภาวะเชนนต้ี อ ง ใชเ ทคนิคการคน หาขอ มลู อกี แบบหนงึ่ ซ่งึ ตอ งคํานึงถึงเวลาทส่ี ูญเสียไปในระหวา งหนวยความจําหลกั และ หนว ยความจาํ รอง

Data Structure & Algorithm

117

8.2 Sequential Search

การคน หาขอมูลตามลาํ ดับ เปน การคน หาทลี่ ะคา ตามลําดับของขอมูลในแฟม ขอมูลจนกวาจะ พบ หรอื ถา ไมพ บกค็ นหาคาถัดไปเรอ่ื ย ๆ จนกวาจะหมดขอ มูล การคน หาขอมลู วธิ นี ี้ เปน การคน หาใน ลักษณะเชิงเสน เปนวิธีทง่ี ายท่สี ดุ และก็เปนวธิ ีทด่ี อ ยประสิทธิภาพกวา วธิ อี ืน่ แตกเ็ หมาะสมสําหรบั การ ประมวลผลขอมลู กบั บางประเภท เชน งานกลมุ (Bach Processing) งานสํารองขอมูล (Backup) งาน ปรับปรงุ แกไขขอมลู ใหทันสมัย (Update) หรอื งานประจาํ (Routine)

ข้นั ตอนในการคน หาขอมลู มดี ังน้ี

1. กาํ หนดเขตขอมลู ใหเ ปน คยี ห ลกั หรอื ดชั นีในการคนหาขอ มลู

2. การคนหาเริม่ ตนจากขอมูลตําแหนง แรกสุด ไดแก ในอารเรยต ําแหนงที่ 0 หรือ 1 (ขึ้นอยกู บั ขอกําหนด ที่ผใู ชต อ งการวา จะใหคา เริ่มตนท่ีอารเ รยตําแหนงท่ี 0 หรอื 1 )

3. ทาํ การเปรยี บเทียบคา ของขอมลู ท่ีตอ งการคนหากับคาของขอมูลในตาํ แหนง นนั้ ๆ

3.1 ถาคาท้ังสองตรงกัน แสดงวา คน พบและจบการทํางานในสวนของการคน หา

3.2 ถา คา ทั้งสองไมต รงกัน แสดงวาคน ยังไมพบ ใหเ ลื่อนตําแหนงของขอมูลไปอีก 1 ตําแหนง

3.3 ทําการเปรยี บเทยี บในขอที่ 3 ไปจนกวา จะพบขอมลู ที่ตองการ

3.4 ถาเปรียบเทยี บไปจนถึงขอมลู ตัวสดุ ทา ยแลวยังไมพ บ ใหจบการทาํ งานในสว นของการคน หา และแสดงใหผ ใู ชทราบวา ไมมีขอ มลู นัน้ ๆ อยใู นกลุม ของขอมูลที่ถกู จัดเก็บไวใ นโครงสรา งขอมูลน้ี

ในการคนหาหากโชคดีจะพบครงั้ แรก แตถ าโชคไมด ีจะพบท่ีคาสุดทาย หรือโชครายอาจไมพ บเลย สาํ หรับ กรณีท่ีไมพบ หรอื พบที่คาสุดทาย จาํ นวนครัง้ ในการคน หาจะเทา กับจาํ นวนของขอมลู

สมมตุ ิให N : จาํ นวนขอมูล / จํานวนครง้ั ในการคนหาแลวพบครงั้ แรก = 1 ครงั้

จํานวนคร้งั ทีค่ น หาแลวพบที่คาสดุ ทาย หรือไมพบเลย = N ครั้ง

ดงั นัน้ จํานวนครั้งในการคนหาโดยเฉล่ยี = (จาํ นวนคร้ังท่คี นหาแลว พบที่คา แรก + จํานวนครง้ั ทค่ี น หา แลวพบที่คาสุดทา ย) /2

Data Structure & Algorithm

118

จํานวนครั้งในการคนหาโดยเฉลยี่ = (1 + N) /2 = N/2 +1/2

จะเห็นวาจาํ นวนครั้งในการคนหาขอมลู โดยเฉลยี่ ขนึ้ อยกู บั ฟงกช ัน Big O(N)

Sequential_search (item, count, key) Char *item ; Int count ; Char key ; {

for (t = 0; t<count; ++t) if (key = = it em[t])

return t; return -1; }

เร่ิมตน เราจะคน หาขอมูลท่ีตองการ แตถ าไมพบก็จะสง คา -1 กลบั ไป จะเหน็ วา วิธีน้ีเปนวิธที ง่ี า ย ท่ีสดุ แตเ วลาที่ใชใ นกรณที ่เี ลวท่ีสดุ จะมีคา เปน O(n) เมือ่ n คอื จํานวนขอมูล จากตวั อยา ง ถา ตองการคนหาขอ มูลตวั เลข หมายเลข 11

30 5 8 11 3

Algorithm

กาํ หนดใหระเบยี นขอมูลทไี่ มไดจัดเรียงลาํ ดับของแฟมขอมูลประกอบดวย r1, r2,…,rn

เมื่อ n >= 1 ซ่งึ มคี าคียข องระเบยี นเปน k1, k2,…,kn ตามลําดับ จากน้ันจะทําการคนหาระเบียนขอมูล

ซ่งึ มคี า คยี ข องระเบียนคือ X

1. กาํ หนดตัวนบั ลําดับทีข่ องระเบยี นขอ มลู คอื I แลวทําซ้ําข้นั ตอนที่ 2 ถึงขัน้ ที่ 4

2. ทาํ การคน หา โดยถา x = k1 แลว ใหแจง ขอ ความการคน พบระเบียนขอมลู ทตี่ องการแลวไปทํา

ขนั้ ตอนท่ี 5

3. เลอื่ นลาํ ดับท่ีของระเบยี นขอ มูลทลี ะหนึ่ง

4. ตรวจสอบจดุ สิ้นสุดแฟมขอมูล โดยถา I <= n แลว ใหย อนไปทํางานในข้นั ตอนที่ 2 หรอื ไมใหแ จง

การคน หาไมพบระเบยี นทตี่ อ งการและทําขั้นตอไป

5. จบการคน หา

Data Structure & Algorithm

119

ขอดี 1. งายตอการสรางแฟม ขอมูลขนึ้ มาใหม และการจัดเก็บขอมลู 2. ใชก บั สือ่ ขอ มูลไดทกุ ประเภท จงึ สามารถเลือกเกบ็ ในสอ่ื ขอ มูลราคาถูก 3. สามารถใชกับงานทเี่ ปลยี่ นแปลงขอมูลจํานวนมาก

ขอ เสีย 1. ไมสามารถเขา ถึงขอมลู ไดโดยตรงได 2. การประมวลผลขา เพราะเสียเวลาในการอา น Record ทีไ่ มต องการประมวลผล

8.3 Binary Search

เปน การคน หารขอมูลอกี วิธีที่มีประสทิ ธิภาพ และเปน ที่นยิ มใชกันอยางแพรหลาย โดยเฉพาะการ สราง Index Table แตว ธิ ีนี้ ขอ มูลจะตองเรยี งกนั กอน จงึ สามารถใชง านได ดงั น้ันถา ขอ มูลมจี าํ นวนมาก ๆ การเรยี งลาํ ดับขอมลู กอ็ าจเปนปญ หาและใชเ วลา

การคน หาขอมูลแบบไบนารีเสิรชใชวธิ ีการคน หาโดยอาศยั หลักการของไบนารเี สริ ช ทรี ซึ่งมี รายละเอยี ดในสวนของขัน้ ตอนในการคนหาขอมลู มดี งั นี้

1. กําหนด หรือรบั ขอมลู ที่ตองการคน หา 2. แบง ครึง่ แฟมขอ มูล หรอื แถวลําดบั ขอมลู 3. นําขอมูลทีต่ องการคนหา จากขอ 1. มาเปรยี บเทยี บกับขอ มูล ท่ีตําแหนงตรงกลาง ซ่ึงไดจ ากการ

แบง ขอมูลในขอ 2. ถา มีคา เทากนั แสดงวาการคนหาประสบความสาํ เรจ็ แตถาไมเ ทา กันให ตรวจดูวาขอมลู ท่ตี องการคน หา มีคา นอยกวาหรือมากกวาคา ตรงกลาง ถา นอยกวาใหนาํ คา ใน สวนแรกมาแบง ครงึ่ เพ่ือนาํ มาเปรียบเทียบใหม แตถาไมใชใหน าํ คา ในสวนหลังมาแบงครึ่ง และ นาํ มาเปรียบเทียบใหม เชน เดียวกนั 4. ทําการเปรยี บเทยี บขอมูลในแฟมขอมูลหรือแถวลําดบั ขอมูล โดยแบงครึง่ ลงไปเรื่อยๆ จนกวา จะ พบหรอื ไมสามารถแบง ไดอกี ตอไป น้นั หมายความวาไมพ บขอมลู แนนอน

การคาํ นวณหาคา Mid = Low + Hight / 2

Data Structure & Algorithm

120

Data Structure & Algorithm

121

การวัดประสิทธิภาพการทาํ งานของอัลกอริทมึ การคนหาขอมูลแบบไบนารเี สริ ช คา ท่ไี ดจากการวัดประสิทธภิ าพการทํางานของอัลกอรทิ ึมการคน หาขอมูลแบบไบนารีเสิรช พจิ ารณาจาก กรณตี า งๆ ดังนี้

กรณที ี่ดีทีส่ ดุ ( Best Case ) ในการคนหาขอมลู คือพบขอมลู ทตี่ องการคนหาในคร้งั ท่ี 1 กรณีที่แยท ี่สุด ( Worse Case ) ในการคน หาขอมูล คือพบขอมลู ท่ตี องการคน หาในครั้งที่ N +1 เมอ่ื N คือ จํานวนระดับ ( Level ) ของขอมูลในไบนารีนน้ั ๆ โดยคา ของ N เริ่มตน ที่ 0 ดงั น้นั การคน หาแบบไบนารีเราจะใชเ วลาอยา งมากที่สดุ เปน 0( Log2N ) เมอื่ n คอื จาํ นวน ขอมลู

Binary Trees and Binary Search Trees

Binary (item, count, key) Char *item ; Int count ; Char key ; {

int low, high, mid ;

low = 0 ; high = count-1 ; while (low<=high) {

mid = (low+high)/2 ; if (key <item[mid])

Data Structure & Algorithm

122

high = mid-1 ; /* found */ else

if (key > item[mid]) low = mid+1 ;

else return mid ;

} return -1 ; }

ขอแตกตาง ของการคน หาแบบแบบไบนารีและแบบลาํ ดับ คือ การคน หาแบบไบนารไี มไดไล เปรียบเทยี บขอมลู ในลิสทอยา งลาํ ดบั แตเ ปรยี บเทยี บกับคากลางของชดุ ขอมลู ทีท่ ําเชนนี้ไดชุดขอ มลู ตอง เปนขอมลู ท่ีเรียงขอมลู ทเี่ รยี งลําดับ และตอ งอยูในโครงสรางขอมลู ทีส่ ามารถไปยังตําแหนงที่ตอ งการได

ทันที

8.4 แฮชชิ่ง (Hashing)

วิธนี เี้ ปนวธิ ีทีด่ ีที่สุดสาํ หรบั ใชในการคน หาแบบไบนารี ซึง่ จะใชเ วลาในการคนหา เปน O(log2n) วธิ แี ฮชชิ่งนี้เปนเทคนิคในการสรางตารางโดยมคี ยี แ บบหนึ่งใชในการคน หาคา คียใ น ตารางนัน้ ได ซึ่งทําได งา ยและรวดเร็ว แฮชช่ิงจะใชการแปลงคา คยี เ ปน คาแอดเดรสของคียนัน้ โดย จะอาศัยฟงกช นั พเิ ศษซึ่งเรา เรยี กวาแฮชชิ่งฟงกชัน (hashing function หรือ key – to – addresstransformation) เราจะใช สญั ลักษณ H(k) ซึ่ง k น้ัน กค็ ือคยี ท ่ีจะใชใ นการคน หาขอ มูล ตารางท่ีจะสรา งขึ้นน้ีจะข้ึนอยูกับฟง กชนั ดว ย ฉะน้ันเราจะเลือกใชฟง กท ม่ี ีการกระจายของขอ มูลหรอื คยี ไปสูแอดเดรสตา งๆ ใหม ากท่ีสุด แตใ นบางครั้ง ถาหากมีการแปลงคา คยี  k1 และ k2 แลว ให คาแอดเดรสออกมาตรงกนั เราจะเรยี กวิธกี ารดงั กลา ววา การ ชนกนั (collisions) ซงึ่ เราจะตอ งมวี ธิ ใี นการแกปญหานี้ใหไ ด แตกอนอืน่ เราจะมาเรยี นรูถึงวิธกี ารสรา ง ฟง กช ันในการคํานวณหาคาแอดเดรสกันกอน วธิ ีการสรางฟง กช นั แฮชชงิ่ มดี วยกนั หลายวิธดี งั น้ี

8.4.1 วธิ กี ารหาร เปน วธิ ีท่ใี ชก นั มากวิธหี นึ่ง โดยจะกําหนดรูปแบบของวิธีน้คี ือ H(x) = x MOD m+1 โดย ที่ m คือ ตวั หารทีเ่ ปน จํานวนเตม็ บวก

จากสูตร จะเหน็ วา เราจะนําเศษท่ีเหลือจากการหารมาใชแลว จงึ บวกดว ย 1 เชน ถา x = 35, m = 11

Data Structure & Algorithm

123

H(35) = 35 MOD 11+1 = 2 +1 = 3วธิ ีการนเี้ ราสามารถกระจายคาไดต้ังแต 1, 2, ….,m หลกั การเลือกคา m คือ จะตองเลอื กคา ใหกระจายในตารางใหม ากที่สุด และคาควรจะเปน จาํ นวนเฉพาะ เพ่ือปองกันไมใหเ กิดการชนกันหรือ เกดิ การชนกันนอ ยท่สี ดุ

จากตวั อยา ง จงสรา ง Hash Function จากฟงกช่ันตอ ไปน้ี

H(x) = x MOD 7 +1

จากขอมูล 12, 15, 9, 4, 34, 21, 38 01 21 H(12) = 6 02 15 H(15) = 2 03 9 H(9) = 3 04 38 H(4) = 5 05 4 H(34) = 7 06 12 H(21) = 1 07 34 H(38) = 4

Hash Table

8.4.2 วธิ ี Mid square หลกั การคือการนาํ คียขอมลู มายกกาํ ลังสอง จากนน้ั เลือกตําแหนงตรงกลางมาใช เปนตาํ แหนงที่อยูใ น Hash Table ตวั อยางเชน

คยี ข อ มลู ยกกาํ ลังสอง ผลลัพธของเลขยกกําลัง ตําแหนงที่อยู (เลอื ก 3,4,5) 312 3122 124 1242 097344 734

542 5422 015376 537

056 0562 293764 376

003136 313

แตเ นอื่ งจากเทคนคิ น้มี ีขอจาํ กัดอยตู รงท่ี คยี ขอมลู จะตองมีคา ไมมากจนเกนิ ไป เพราะถาคีย

ขอ มลู มีคา มาก เมื่อนํามายกกําลงั สองแลว คา ผลลพั ธที่ไดจะยงิ่ มคี ามากขึน้ ไปอีก ซง่ึ จะสงผลกระทบตอ

การเกบ็ ขอมลู ในหนวยความจํา

Data Structure & Algorithm

124

8.4.3 วธิ ีการพับ วิธีการนีเ้ ราจะแบงคียออกเปน สว นๆ ถา เปน ไปไดก็ควรจะแบงเปน สว นละเทาๆกนั แลว

นําแตล ะสวนมาบวกเขา ดว ยกัน โดยถามตี ัวทดเกิดขน้ึ ในหลกั ท่มี ากที่สดุ ก็ใหละเอาไว แบง ออกปน 2

แบบ

1. เทคนิคแบบ Fold Shift

โดยทําการแบง การชดุ ของขอมูลออกเปน 3 สว นเทา ๆกนั แลว ทําการเล่ือนคยี ของขอ มลู แตล ะ

ชุดคยี ใหขอมลู ตรงหลักกัน แลวทําการบวกคา ขอมูลของคีย ผลลพั ธท่ไี ด จะเปนคา คีย Hash ของชดุ

ขอมลู

จากตัวอยา ง จงหาคาคียของชุดขอ มลู 345684533 โดยวิธีการแบบ Fold Shift

จากขอมูล 345684533

แบงขอมลู 345 684 533

บวกขอมลู 345

684 +

533

1562

ตําแหนง ท่ีอยูใน Hash Table คอื ตําแหนง 562

2. เทคนิค Fold Boundary

ทาํ การแบงชดุ ของขอมูลออกเปน 3 สว นเทา ๆกนั ทาํ การพบั ตวั เลขคยี ขอมูล โดยยดึ ตําแหนง

ท่ี 4-6 เปนตําแหนงตรงกลาง แลวตําแหนง ท่ี 3-1 และ 9-7 จะทําการบวกคา คยี ของขอ มูล

จากตัวอยาง จงหาคา Hash Function ของคา คียต อไปนี้ 356942781 โดยวธิ กี ารแบบ Fold

Boundary

จากขอมูล 356942781

แบง ขอมลู 356 942 781

บวกขอมลู 942

653 +

187

1782

คา คียของ Hash Function ทไ่ี ดคือ 782

Data Structure & Algorithm

125

8.5 การแกป ญ หาคอลลิชนั

จากหัวขอท่ีเราไดกลา วถงึ การเกบ็ ขอมูลโดยใชฟง กช น่ั แฮชชิ่ง เพอื่ จะไดคน หาขอมลู ไดร วดเร็วข้ึน และในการเก็บขอมลู แตละคร้ังเราควรจะเกบ็ แอดเดรสเพียงคาเดยี วตอขอมูลหน่ึงคา แตในบางคร้งั ฟงกชน่ั แฮชชิง่ อาจจะทําใหคาแอดเดรสใหมตรงกับแอดเดรสทม่ี ีอยแู ลว จะทาํ ใหเ กิดการชนกันหรือเกดิ คอลลชิ ัน (collision) ข้นึ ซึง่ วธิ แี กป ญ หามหี ลายวธิ แี ตจ ะขอยกตัวอยา ง 2 วธิ คี อื

1. วธิ ี Separate Chaining 2. วิธี Open Addressing จดุ ประสงคข องการแกปญ หาคอลลชิ ันน้ี นอกจากแกปญหาการชนกนั แลว ยงั จะตองพยายามจดั คียใ หอยูใ นแอดเดรสทถ่ี ูกจองไวใ หอยางมปี ระสิทธภิ าพ โดยจะมองแอดเดรสตาง ๆ ใหอยูในรูปของตาราง (อาจมีหลาย ๆ ตารางก็ได) เพื่อจะไดส ะดวกในการเขยี นโปรแกรมและคนหา

8.5.1. วธิ ี Separate Chainning เปน วธิ กี ารเกบ็ ขอมลู โดยใชต ารางของ Hash Table ชว ยในการเกบ็ วธิ กี ารเก็บขอมูลน้ัน หา

ไดจากการใช Hash Function โดยคา ขอมูลท่ีเกิดการชนกันของขอมูลน้นั จะทาํ การเกบ็ ขอมลู ลงใน ตารางของ Hash โดยทาํ การเรียงขอมูลตอกันไปเร่ือยๆ เหมอื นเปนแบบโครงสรางอารเรยห รอื ลิงคลสิ ต

ตัวอยา ง จงสรางโครงสรางขอมลู แบบ Hash Table ประกอบดวยขอมูล 25, 4, 46, 23, 95, 26,

45 โดยกาํ หนดให Hash Table มขี นาดของตาราง 5 ชอ ง

Hash Function : H(x) = x MOD 5 +1

H(25) = 1 H(4) = 5

H(46) = 2 H(23) = 4

H(95) = 1 H(26) = 2

H(45) = 1

01 45 95 25 02 26 46 03 04 23 05 4

Hash Table

Data Structure & Algorithm

126

8.5.2. วธิ ี การแบบ Open Addressing มี 2 วิธี คอื