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

การเรียงข้อมูลมความจำเป็นหลายประการ นอกจากจะทำให้บัญชีชื่อหรือสิ่งของสะดวกต่อการค้นหาและตีความแล้ว ยังมีผลต่อกระบวนการดึงข้อมูลมาใช้ นอกจากนี้อัลกอริทึมหรือแบบการคำนวณสำหรับการแก้ปัญหาสลับซับซ้อนต่างๆ เช่น job scheduling, knapsack problem ก็ต้องอาศัยการเรียฝข้อมูลทั้งสิน การเรียงข้อมูลแบ่งได้เป็น 2 ลักษณะคือ

    1. การเรียงข้อมูลแบบภายใน (Internal Sorting) การเรียงข้อมูลภายในหมายถึงว่าจำนวนข้อมูลที่มีขนาดไม่ใหญ่กว่าของพื้นที่ความจำที่กำหนดให้กับผู้ใช้แต่ละรายดังนั้นข้อมูลทั้งหลายจะเก็บอยู่ใรหน่วยความจำหลัก (main memory) และแบบการคำนวณสำหรับการเรียงข้อมูลสามารถอ่านข้อมูลแต่ละชิ้นจากหน่วยความจำหลักหรือเขียนข้อมูลสู่หน่วยความจำหลักได้เลย โดยไมจำเป็นต้องใช้หน่วยความจำรอง เช่น ดิสก์ (disk) หรือเทป (tape) สำหรับเก็บผลลัพธ์ชั่วคราว
    2. การเรียงข้อมูลแบบภายนอก (External Sorting) ถ้ามีข้อมูลจำนวนมากเกินกว่าที่จะบรรจุลงในพื้นที่ความจำหลักได้ทั้งหมดในคราวเดียว จึงจำเป็นต้องแบ่งข้อมูลออกเป็นส่วนย่อยๆ ซึ่งแต่ละส่วนมีขนาดใหญ่พอที่จะอยู่ในหน่วยความจำหลักได้ และจะได้รับการเรียงโดยใช้แบบการคำนวณการสำหรับการเรียงแบบภายในตามที่ผู้ออกแบบเห็นเหมาะสม หลักจากนั้นก็ต้องมีการนำข้อมูลย่อยของส่วนที่เรียงแล้วไปเก็บไว้ในดิสค์หรือเทป เป็นการชั่วคราว เพื่อรอที่จะรวมกับข้อมูลส่วนอื่นๆ ที่เรียงแล้ว การเรียงข้อมูลแบบภายในจำเป็นต้องคิดถึงเวลาที่เสียไปในการเปรียบเทียบและ การเลื่อนที่ข้อมูลในหน่วยความจำหลักเท่านั้น สำหรับการเรียงแบบภายนอกจะต้องคิดถึงเวลาที่สูญเสียไป อันเนื่องจากการถ่ายเทข้อมูลระหว่างเทปหรือดิสก์กับหน่วยความจำหลักด้วย เวลาที่ต้องสูญเสียไปกับการถ่ายเทข้อมูลระหว่างหน่วยความจำหลักกับเทปหรือดิสก์จะเป็นตัวระบุความตีเลวของการคำนวณแบบเรียงภายนอก
  1. Bubble sort
Bubble sort เป็นแบหนึ่งของ exchange sort หลักการมีอยู่ว่าเราจะเปรียบค่าของ 2 ค่าที่ติดกัน ถ้ามันไม่ได้อยู่ในระดับที่เรากำหนด เช่น จากน้อยไปมาก ก็ให้แลกเปลี่ยนตำแหน่งของค่าทั้ง 2 ค่านั้นและวเอาค่าน้อย (หรือค่าที่มาก ถ้าเป็นการเรียงจากค่ามากไปหาค่าน้อย) เปรียบเทียบกับค่าถัดไปอีกเป็นเช่นนี้ตลอดไปจนกว่าจะอยู่ในระดับที่ถูกต้อง สมมติเรามีลิสต์ ( 5, 1 , 2, 8, 9) เราจะเรียงโดยเทคนิคดังรูปที่ 1.1 (โดยการเรียงลำดับจากมากไปน้อยตามแนวบนลงล่าง)

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

 
ขั้นแรกให้เอา 5 เปรียบเทียบกับ 1 ปรากฏว่า 5 และ 1 เรียงลำดับตามที่เราต้องการอยุ่แล้วจ่กนั้นให้เอา 1 เปรียบเทียบกับตัวถัดไปคือ 2 เนื่องจาก 2 มากกกว่า 1 และ 2 อยู่ในตำแหน่งที่ผิดลำดับ จึงให้แลกที่กับ 1 หลักจากที่ 2 ไปอยู่ที่ตำเหน่งที่อยู่เดิมของ 1 (นั่นคือตำเหน่งที่ 2 ) แล้วก็ให้เปรียบเทียบกับค่าในตำเหน่งที่ 1 คือ 5 ปรากฏอยู่ในลำดับที่ถูกต้องก็ไม่ต้องแลกกัน ต่อมานำ 1 ไปเปรียบเทียบกัย 8 แล้วทำในลักษณธเดิม ค่า 8 จะค่อยๆ ลอยขึ้นไปอยู่ในตำเหน่งที่ถูกต้อง ในที่สุดก็นำ 1 ไปเปรียบเทียบกับ 9 เลข 9 จะค่อยๆ ลอยขึ้นไปยังตำเหน่งที่ถูกต้องของมัน

 
สิ่งที่ต้องทำในการเรียงค่าคือ เปรียบเทียบและแลกตำเหน่ง เราจะพิจารณากรณีปลายสุด2 กระณีคือ
  1. ถ้าลิสต์ที่เรียงเรียบร้อยแล้วจากมากไปน้อย และเราบังเอิญต้องการเรียงจากมากไปน้อยโดย bubble sort เราจะสามารถทำได้โดยไม่ต้องมีการแลกตำแหน่งเลยและต้องทำการเปรียบเทียบ เพียง n-1 ครั้งเท่านั้น (ถ้ามีข้อมูล n ตัว)
  2. ถ้าลิสต์ที่เรียงเรียบร้อยแล้วจากน้อยไปมากและเราต้องเรียงมันจากมากไปน้อย เรา

ต้องทำการแลกเปลี่ยนและเปรียบเทียบเป็นจำนวน 1+2+3+…+(n-1) ครั้งหรือเท่า กับ n(n-1)/2 ครั้งนั่นเอง
จะเห็นได้ว่า bubble sort จะดีหรือแลวก็ขึ้นอยู่กับว่าลิสต์นั้นเกลือบเรียง ในลำดับที่เราต้องการจะเรียงมันหรือไม่ ถ้าค่าลิสต์นั้นอยู่ในแบบ random ก็จะต้องมีการแลกเปลี่ยนประมาณ n(n-1)/4 ครั้ง การเรียงข้อมูลแบบนี้จัดเป็นพวก ซิงเกิลตัน อาร์.ซี (snigleton R.C. – Alogrithm 347-CACM) พบว่าวิธีการเรียงแบบ bubble จะดีที่สุดถ้าลิสต์นั้นมีค่าเท่ากับหรือน้อยกว่า 11 ตัวสรุปได้ว่าการเรียงข้อมุลแบบนี้ไม่เหมาะกับลิสต์ยาวๆ อย่างไรก็ดีวิธีการเรียงแบบนี้สามารถจำได้ง่ายและโปรแกรมได้ง่ายเช่นกัน

 

 
แผนผังของ bubble sort แสดงดังรูปที่ 1.2

 

2 Insertion sort

วีธีนี้ต้องใช้พื้นที่ความจำเพิ่มขึ้นอีก N ตำแหน่งสำหรับเก็บส่วนที่เรียงแล้ว นั้นถ้าเรามีลิสต์ A(1:N) ที่ยังไม่ได้เรียงเราต้องใช้ลสต์ B(1:N) มาช่วยโดยที่เราจะดึงแต่ละค่าในลิสต์ A ไปใส่ในตำเหน่งที่ถูกต้องในลิสต์ B จะเป้นลิสต์ที่เรียงกันตามลำดับ
รูปที่ 7.2 แผนผังการทำงานของ bubble sort เพื่อเรียงข้อมูลในอาร์เรย์ A(1:N)จากค่าน้อยไปค่ามาก อย่างไรก็ดีเราก็มีวิธีที่จะ sort – in place นั้นคือใช้พื้นที่ความจำเพียง N ตำแหน่งเท่านั้นโดยไม่ต้องใช้พื้นที่ความจำเพิ่ม วิธีนี้เราจะแนะนำตัวที่ 1 จากส่วนที่ยังไม่ได้เรียงใส่เข้าไปในส่วนที่เรียงแล้ว ซึ่ง J ตัวดังรูป

 

รูปที่ 2.3 ลักษณะการเรียงแบบไม่ต้องใช้ความจำเพิ่ม

 

3 Heap sort

การเรียงข้อมูลโดยอาศัยโครงสร้าง heap เป็นการเรียงข้อมูลแบบที่ดีที่สุด เพราะเป็นอัลกอริทึมที่รับประกันได้ว่าเวลาที่ใช้ไม่ว่าในกรณีใดจะเป็น O(long2n) เสมอ

 

รูปที่ 3.4 การเปรียบเทียบโครงสร้าง heap กับโครงสร้างอื่นๆ

โครงสร้าง Heap heap เป็นต้นไม้ไบนารีที่มีคุณสมบัติว่าโหนดใดๆ ในต้นไม้นั้นจะมีค่าคีย์ใหญ่กว่าที่อยู่ใน left son และ right son ของมัน (ถ้าโหนดนั้นมีลูก) ตัวอย่างดังรูปที่ 3.4 (ก) เป้น heap ส่วนรูปที่ 3.4 (ข) ไม่ใช่ hemp

 

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

ขั้นที่ 1 สร้างโครงสร้าง heap

ขั้นที่ 2 เอาต์พุตที่รูตโหนด

ขั้นที่ 3 ปรับแต่งต้นไม้ที่เหลือให้เป็น heap

 

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

รูปที่ 3.5

 

ความสัมพันธ์ระหว่างโครงสร้างอาร์เรย์และโครงสร้าง heap จะมีรูปเป็นต้นไม้ไบนารีดังรูปที่ 3.6

รูปที่ 3.6 ต้นไม้ไบนารีของอาร์เรย์รูปที่ 3.5

หน้าต่อไป

 

 

 

 1