Sorting

บทที่ 9

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

ความหมาย

l การจัดเรียงลำดับ (Sorting) หมายถึงการจัดเรียงข้อมูล ให้เรียงลำดับตามเงื่อนไขที่กำหนดไว้ (มากไปน้อย หรือ น้อยไปมาก)

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

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

l การจัดเรียงภายใน (Internal Sorting)

l การจัดเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำของเครื่องคอมพิวเตอร์ การจัดเรียงแบบนี้จะต้องอาศัยเทคนิคและวิธีการของโครงสร้างข้อมูลมาช่วย เช่น การใช้ Array หรือ Linked-List เข้ามาช่วย

l การจัดเรียงภายนอก (External Sorting)

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

วิธีการจัดเรียงข้อมูล

·       จัดเรียงแบบแลกเปลี่ยน (Exchange Sort)

·       การจัดเรียงแบบแทรก (Insertion Sort)

·       การจัดเรียงแบบเลือก (Selection Sort)

การจัดเรียงแบบแลกเปลี่ยน (Bubble Sort)

·       เป็นการจัดเรียงโดยการเปรียบเทียบค่า 2 ค่าที่ติดกัน

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

o   ข้อมูลที่มีค่าน้อย ต้องอยู่ในตำแหน่งหน้า

o   ข้อมูลที่มีค่ามาก จะอยู่ตำแหน่งหลัง

o   ข้อมูล 2 ตัวที่อยู่ติดกัน ถ้า

§  ถ้าข้อมูลตัวแรกมากกว่าตัวหลัง ก็จะต้องสลับตำแหน่งกัน

§  แต่ถ้าข้อมูลตัวแรกน้อยกว่าข้อมูลตัวหลัง ก็ไม่ต้องสลับตำแหน่ง

§  ทำเช่นนี้ซ้ำกันไปเรื่อย ๆ จนกว่าการเปรียบเทียบของข้อมูลตลอดทั้งชุดจะไม่ต้องมีการสลับตำแหน่งเลย

Bubble Sort

·       เป็นวิธีที่ง่ายเช่นกัน

·       แนวคิด คือค่าที่มากๆ จะต้องถูกนำไป (ลอยไป) ไว้ด้านท้าย

·       เหมือนลูกโป่งที่ขนาดใหญ่จะลอยได้เร็วและสูง

·       แนวคิด

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

o   แต่ละครั้งจะได้ค่ามากที่สุดไปไว้ท้ายสุด

o   จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-1

o   จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-2

o   …

o   จากนั้นเริ่มการเปรียบเทียบใหม่ตั้งแต่ตัวแรกถึงตัวที่ N-x

o   ทำจน x = N-1

ตัวอย่าง Function การจัดเรียงแบบ Bubble

ตัวอย่าง: Bubble Sort

รอบที่                                                     ข้อมูล

1              06           44           55           12           42           94           18           67

2              06           12           44           55           18           42           94           67

3              06           12           18           44           55           42           67           94

4              06           12           18           42           44           55           67           94

5              06           12           18           42           44           55           67           94

6              06           12           18           42           44           55           67           94

7              06           12           18           42           44           55           67           94

Program bublesort1;

const n = 8;

      a:array[1..n] of integer = (44,55,12,42,94,18,06,67);

VAR  i,j,l,temp : integer;

begin

   for i := 2 to n do

     begin

        for j := n downto i do

          if a[j-1] > a[j] then

            begin

               temp := a[j-1];

               a[j-1] := a[j];

               a[j] := temp;

           end;

          for l := 1 to n do

             write(a[l]:10);

     end;

     writeln;readln;

end.

 การจัดเรียงแบบแทรก (Insertion Sort)

·       เป็นการจัดเรียงโดยการนำข้อมูลที่จะทำการเรียงนั้น ๆ ไปจัดเรียงทีละตัว

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

·       วิธีการลักษณะนี้จะคล้ายกับการหยิบไพ่ขึ้นมาเรียงทีละใบ ซึ่ง

o   ไพ่ใบแรกจะไม่ต้องสนใจอะไร

o   แต่เมื่อหยิบไพ่ใบที่ 2 ก็จะต้องพิจารณาว่าจะไว้ก่อนหรือไว้หลังใบแรก

o   และเช่นเดียวกัน เมื่อหยิบไพ่ใบถัด ๆ มา ก็จะต้องพิจารณาว่าจะวางใบตำแหน่งใดเพื่อให้เกิดการเรียงลำดับ จนกระทั่งหมด

ตัวอย่าง Function การเรียงแบบ Insertion

ตัวอย่าง: Insertion Sort

รอบที่                                                     ข้อมูล

2              44           55           12           42           94           18           06           67

3              12           44           55           42           94           18           06           67

4              12           42           44           55           94           18           06           67

5              12           42           44           55           94           18           06           67

6              12           18           42           44           55           94           06           67

7              06           12           18           42           44           55           94           67

8              06           12           18           42           44           55           67           94

Program insertionsort;

const n = 8;

      a:array[1..n] of integer = (44,55,12,42,94,18,06,67);

VAR  i,j,l,x : integer;

begin

   for i := 2 to n do

     begin

        x := a[i]; j := i-1;

        while (x < a[j]) and (j > 0) do

            begin

               a[j+1] := a[j];

               j := j - 1;

            end;

        a[j+1] := x;

        for l := 1 to n do

          write(a[l]:10);

     end;

     writeln;readln;

end.

การจัดเรียงแบบเลือก (Selection Sort)

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

·       แล้วเอามาเก็บไว้ข้างนอก

·       แล้วกลับไปหาข้อมูลตัวที่น้อยที่สุดในกองต่อไปจนกว่าจะหมดกอง

ตัวอย่าง Function การเรียงแบบ Selection

ตัวอย่าง: Selection Sort

รอบที่                                                     ข้อมูล

1              06           55           12           42           94           18           44           67

2              06           12           55           42           94           18           44           67

3              06           12           18           42           94           55           44           67

4              06           12           18           42           94           55           44           67

5              06           12           18           42           44           55           94           67

6              06           12           18           42           44           55           94           67

7              06           12           18           42           44           55           67           94

Program selectionsort;

const n = 8;

      a:array[1..n] of integer = (44,55,12,42,94,18,06,67);

VAR  i,j,k,l,temp : integer;

begin

   for i := 1 to n-1 do

     begin

        k := i;

        for j := i+1 to n do

          if a[k] >a[j] then k := j;

        temp := a[i];

        a[i] := a[k];

        a[k] := temp;

        for l := 1 to n do

          write(a[l]:10);

     end;

     writeln;readln;

end.

Shellsort

·       Shellsort ตั้งตามชื่อของผู้คิดค้นการจัดเรียงแบบนี้ คือ Donald Shell และเป็นอัลกอริทึมแรกที่ทำลายขอบเขตเวลาที่เป็น quadratic

·       ในขณะทำงานแต่ละ phase นั้น shell sort ใช้การเปรียบเทียบค่าที่อยู่ในตำแหน่งที่ห่างกัน ระยะห่างดังกล่าวนี้จะลดลงลงเรื่อย ๆ จนกระทั่งถึงขั้นตอนสุดท้ายที่เป็นการเปรียบเทียบค่าที่อยู่ติดกัน

o   ด้วยเหตุที่ระยะห่างของค่าที่นำมาเปรียบเทียบกันลดลงในระหว่างการทำงานของอัลกอริทึมนี้เอง จึงเรียกShellsort อีกอย่างว่า diminishing increment sort

·       Shellsort ใช้การลำดับของ h₁, h₂, . . . , h_t ซึ่งเรียกว่า increment sequence และลำดับที่ใช้จะมีค่าลักษณะใดก็ได้เพียงแต่มีเงื่อนไขว่า h₁ = 1 เท่านั้น แต่แน่นอนว่าบางลำดับจะทำงานได้ดีกว่าบางลำดับ (จะกล่าวถึงอีกครั้ง)

·       ในการทำงานแต่ phase ที่ใช้ลำดับการเพิ่ม h_k ผลที่ได้ คือ สำหรับแต่ละค่า i เราจะได้ว่า a[i] £ a[i + h_k] กล่าวคือสมาชืกทุกตัวที่มีระยะห่างกัน h_k จะอยู่ในลำดับที่มีกี่จัดเรียงอย่างถูกต้อง ซึ่งเรียกว่า h_k-sorted file

คุณสมบัติที่สำคัญของ Shellsort คือ การทำ h_k-sorted แล้วตามด้วย h_k-1-sorted นั้นยังคงสภาพของ h_k-sorted

Original       81  94  11  96  12  35  17  95  28  58  41  75  15

--------------------------------------------------------------------------------------

After 5-sort  35  17  11  28  12  41  75  15  96  58  81  94  95

After 3-sort  28  12  11  35  15  41  58  17  94  75  81  96  95

After 1-sort  11  12  15  17  28  35  41  58  75  81  94  95  96

Figure  Shellsort หลังการทำงานแต่ละ pass

Heapsort

·       ในการจัดเรียงด้วยเวลา O(N log N)  อัลกอริทึมที่ใช้พื้นฐานแนวคิดนี้ เรียกว่า heapsort และมี Big-Oh running time ดีกว่าอัลกอริทึมอื่น ๆ ที่กล่าวมาแล้ว

·       วิธีการ คือ สร้าง binary heap (มีสมาชิก N ตัว) ซึ่งใช้เวลา O(N) จากนั้นทำ deleteMin N ครั้ง สมาชิกที่ถูกย้ายออกไปจาก heap ตัวแรก คือตัวที่มีค่าน้อยที่สุด และเรียงลำดับตามค่าไป แล้วนำไปเก็บใน Arrray อีกตัวหนึ่งจากนั้นก็คัดลอกกลับไปยัง Array เดิมซึ่งก็จะเป็นคำตอบในการจัดเรียง เนื่องจากการทำ deleteMin แต่ละตัวใช้ O(log N) ดังนั้น running time รวมทั้งหมด คือ O(N log N)

·       หลังการทำงานจนเสร็จ Array ที่ได้ก็จะเป็น Arrayของสมาชิกที่จัดเรียงจากมากไปน้อย

o   ถ้าต้องการจัดเรียงจากน้อยไปมาก เราก็จะใช้ heap ที่ parent มีค่ามากกว่า child ของมัน นั่นคือ (max)heap

·       เราจะใช้ (max)heap ในการ implement ของเราและยังคงใช้ Array เช่นเดิม

o   ขั้นแรกสร้าง heap ด้วย linear time จากนั้นทำ deleteMaxes จำนวน N - 1 ครั้ง ด้วยการสลับสมาชิกตัวสุดท้ายใน heap กับสมาชิกตัวแรก แล้วลดขนาดของ heap ลงแล้วทำการ percolating down

o   หลังจบอัลกอริทึมจะได้ Arrayที่มีสมาชิกเรียงตามลำดับค่า

Figure 7.6 (Max) heap หลังการ build_heap

Figure 7.7 Heap หลัง deleteMax ครั้งแรก

Quick Sort

หลักการดำเนินงาน

         * หาตำแหน่งในการแยกลิสต์

         * แบ่งแยกข้อมูลออกเป็นสองส่วน และหาตำแหน่ง 

    ในการแยกลิสต์

         * ทำจนกว่าข้อมูลจะเรียงลำดับเรียบร้อย

Merge Sort

Merge Sort Algorithm Analysis

จำนวนครั้งของการเปรียบเทียบทั้งหมด

= ผลบวกทุกระดับของ ( จำนวนลิสต์ในแต่ละระดับ * จำนวนครั้งของการเปรียบเทียบแต่ละลิสต์ )

= (N-1) *1 + (N/2 -1)*2 + (N/4 – 1)*4 +..+(2-1)*N/2

= ( N-1) + (N-2)+(N-4)+..+(N-N/2) 

=  Nlog₂N    จะได้ bigO(Nlog₂N)