CoE KKU

ในบางกรณีที่เป็นกรณีพิเศษเราอาจทำการจัดเรียงข้อมูลได้ โดยใช้เวลาเป็น linear time ตัวอย่างอย่างง่ายได้แก่ bucket sort โดยจะต้องประกอบด้วยสารสนเทศเพิ่มเติมเพื่อให้มันทำงานได้

ถ้าอินพุต $A_1, A_2, ... , A_n$ เป็นเลขจำนวนเต็มบวกที่มีค่าน้อยกว่า M เราจะกระจายอินพุต เข้าไปในถัง ( bucket ) แล้ว เรียงข้อมูล ในแต่ละถัง โดยอาจใช้การเรียงแบบธรรมดา หรือ Recursive ใช้ Bucket sort ก็ได้ แล้วนำข้อมูลที่เรียงในแต่ละถังมาต่อกัน เป็นการเรียงข้อมูลทั้งหมด ถังอาจใช้ linklist หรือ arraylist ในการเก็บข้อมูล โดยแต่ละถังอยู่ในอาร์เรย์

กำหนดให้ มี k ถังในอาเรย์ เราสามารถนำข้อมูล $A_i$ เข้าไปเก็บในถังที่ $\left\lfloor k\bullet A_i/M\right\rfloor$ โดยการอ่านข้อมูลทั้งหมด จะมีการทำงานเป็น $O(n)$ จากนั้นเรียงข้อมูลในแต่ละถัง ในกรณี worst case ข้อมูลทุกตัว เข้าไปอยู่ในถังเดียวกัน จะทำให้ใช้เวลาเป็น $O(n^2)$ ถ้าข้อมูลกระจายอย่างเท่าๆ กัน จะทำให้ในแต่ละถัง มีข้อมูล $\left\lceil n/k\right\rceil$ ซึ่งใช้เวลารวม $k\bulletΟ(\lceil n/k \rceil ^2)$ จากนั้น นำข้อมูลมาต่อกัน โดยการรวม k ถัง ถ้าต้อง copy ข้อมูลออกมา จะทำงานเป็น $O(n)$ ซึ่งโดยรวม ทั้งกระบวนการ จะใช้เวลา $Ο(n)+k∙Ο(\lceil n/k \rceil ^2)+Ο(n)$

ถ้า $k = O(n)$ เช่น $n/2$ หรือ $n/100$ และข้อมูลมีการกระจายอย่างสม่ำเสมอในแต่ละถังจะมีข้อมูลเฉลี่ยเป็น ค่าคงที่ ทำให้เทอม $\ k\bulletΟ( \lceil n/k \rceil ^2)$ มีค่า $O(n) O(1)$ ดังนั้น โดยรวม bucket sort จะทำงานเป็น $O(n)$

ตัวอย่าง ให้อินพุต เป็น 78, 17 , 39, 26, 72, 94, 21, 12, 23, 68 และกำหนดให้ อินพุต มีค่าไม่เกิน 100 เลือก k =10 นำอินพุตใส่ใน bucket เป็น link list และเรียงข้อมูลใน bucket ได้ตามรูปที 7.19

แม้ว่าจะคล้ายกับ การนำข้อมูลเข้า Hash table แต่ การ mapping เป็น index ของอาร์เรย์ ไม่เหมือนกัน ในกรณีของ Bucket sort function ที่ใช้ จะเรียง bucket ด้วย ข้อมูลใน bucket [ 0 ] จะน้อยกว่าข้อมูล ใน bucket [ 1 ]

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

Counting Sort ใช้เรียงข้อมูลจำนวนเต็ม ที่มีค่าไม่เกิน M โดยการสร้างอาร์เรย์ ขนาด M (count[M]) เพื่อใช้นับข้อมูล โดยการนับข้อมูล $A_i$ ในตำแหน่งค่าของ $A_i$ ( count[$A_i$]++ ) เมื่อนับข้อมูลทั้งหมดแล้ว จะคำนวณตำแหน่งของข้อมูลที่ได้จากการนับ แล้วนำข้อมูลไปใส่ใน อาร์เรย์ใหม่ตามตำแหน่ง ถ้าข้อมูลเป็น จำนวนเต็มอย่างเดียวไม่ใช่ key ของ Object สามารถพิมพ์ข้อมูลได้ เมื่อนับข้อมูลเสร็จ

ตัวอย่าง ให้อินพุต เป็นข้อมูลจำนวนเต็ม มีค่าไม่เกิน 5 ตามรูปด้านล่าง

สร้างอาร์เรย์ Count และนับจำนวนข้อมูลใน A ตามรูปด้านล่าง

ถ้าข้อมูลเป็นจำนวนเต็มอย่างเดียว จะพิมพ์ผลลัพธ์ได้ เป็น 0 0 2 2 3 3 3 5 โดยดูจากการนับ

ถ้าข้อมูลเป็น object โดยมีจำนวนเต็มเป็นค่า key เพื่อเรียงข้อมูลจะคำนวณหาค่า Offset โดย บวกจำนวนสะสมจากตัวหน้า จะได้ตามรูปด้านล่าง

ทั้งนี้ อาจคำนวณในอาร์เรย์ Count เป็นค่า Offset เลยก็ได้ เนื่องจากไม่ได้ใช้ค่า count อีกแล้ว อีกทั้งจะมีขนาดเท่ากัน ค่า Offset จะเป็นค่าตำแหน่งท้ายสุดที่ข้อมูลค่าตาม index ของอาร์เรย์ จะอยู่

สร้างอาร์เรย์ B ขนาดเท่ากับ อาร์เรย์ A เพื่อเก็บค่าที่เรียงกัน อ่านค่าอาร์เรย์ A จากตัวสุดท้าย ไปหาตัวแรก ดูค่า offset โดยการ mapping ค่ามายัง index ของ offset จะได้ตำแหน่ง ย้ายข้อมูลจาก อาร์เรย์ A มายัง อาร์เรย์ B ที่ตำแหน่งดังกล่าว และ ลดค่า offset ตัวอย่างตามรูปที่ 7.20

การที่อ่าน อาร์เรย์ A จากด้านหลังมาด้านหน้า เพื่อให้เป็น Stable sort คือข้อมูลที่เท่ากัน จะเรียงเหมือนเดิม

จะเห็นได้ว่า การทำงาน จะนับข้อมูลทั้งหมด 1 รอบ ปรับปรุงข้อมูลใน Count อาร์เรย์ และ ย้ายข้อมูลทั้งหมด อีก 1 รอบ ดังนั้น การทำงานจึง มี Runtime เป็น $O(n) + O(M) + O(n)$ โดย M เป็นขนาดของ Count อาร์เรย์ และ ต้องการเนื้อที่เก็บข้อมูลเพิ่ม เท่ากับ จำนวนอินพุต

M อาจจะมีขนาดใหญ่ตามค่าของอินพุตที่เป็นไปได้ โดยมากแล้ว ใช้การแบ่งค่า ตามหลักของค่าอินพุตออกเป็นส่วนๆ เพื่อให้ M มีขนาดเล็กลง จำนวนเต็มอาจจะมองในฐาน 10 เป็นหลักหน่วย หลักสิบ แต่ละหลักมี 10 ตัว หรือ อาจจะมองในฐาน 2 เป็น byte แรก, byte ที่ 2 แต่ละ byte มี 256 ตัว แล้วทำงานหลายรอบตาม Radix sort

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

ตัวอย่าง มีอินพุตเป็นจำนวนเต็ม 3 หลัก ทำการ เรียงด้วย Counting sort ในแต่ละหลัก 3 ครั้ง โดยแต่ละหลัก Count อาร์เรย์ มี่ขนาด 10 เพราะใช้เลขฐาน 10 ซึ่งเป็นเลขได้ 0-9 ตามรูปที่ 7.21

รูปที่ 7.21 Radix sort

ถ้าอินพุตมีจำนวนหลักมากกว่านี้ เช่นเป็นตัวเลข 13 หลัก (รหัสประจำตัวประชาชน) การใช้ Counting sort อาจทำทีละ 4 หลักก็ได้ ซึ่งจะลดการทำงาน จาก 13 รอบเหลือเพียง 4 รอบ แต่ Count อาร์เรย์ จะมีขนาด เป็น 10,000 ช่อง การเรียงข้อมูลแต่ละหลัก อาจใช้วิธีการอื่นที่ไม่ใช่ Counting sort ก็ได้ แต่ต้องเป็น Stable sort กล่าวคือ ข้อมูลที่มีค่าเท่ากัน ตัวที่มาก่อนในอินพุต จะมาก่อนใน ผลลัพธ์

จะเห็นได้ว่า Runtime เท่ากับ จำนวนรอบ คูณกับ Runtime ของการ Sort แต่ละรอบ