การเรียงลำดับแบบเลือก
เช่น เดียวดับดารจัดเรียงลำดับแบบบับเบิ้ลซึ่งการทำงานจะมีจำนวน n=1 รอบและทำการเปรียบเทียบค่าทั้งหมดตามลำดับอาร์เรย์ โดยแต่ละตั้งจะมีการย้ายค่ามากที่วุดของค่าที่เหลือที่ยังจัดเรียงตามลำดับ ไปยังที่ตำแหน่งที่ถูกต้อง ดั้งในรูปที่ 11.2ลักษณะการทำงานจะมีประสิทธิภาพมากกว่าการจัดเรียงลำดับแบบบับเกิ้ล ที่ในแต่ละรอบการทำงานจะมีการสลับตำแหน่งเพียงครั้งเดียว และได้อัลกอริทึมการเรียงลำดับแบบเลือกตั้งในตาราง ตารางที่ 11.4 อัลกอริทึมการเรียงลำดับแบบเลือก
| 1. ทำขั้นตอน 2ซ้ำแต่ i=n-1จนถึง i=1 2. ทำการสลับตำแหน่งระหว่าง a กันค่าที่มากที่สุดใน [ao…ai] |
และเขียนเป็นฟังก์ชันเรียงลพดับแบบเลือกได้เป็นตารางที่ 11.5
ตารางที่ 11.5 ฟังชันก์เรียงลำดับแบบเลือก
| Void Selectionsort (int key [], I nt size){ Int I, j, max; For(i=size-1; i>0; i–){ Max =0; For (j=1; j ,=I; j++) If(key[j]>key[max]) Max=j; Swap(&key[max]); } } |
เมื่อ นำลำดับแบบเลือกมาใช้กับอาร์เรย์ตัวเดียวกับตัวอย่างในการเรียงลำดับแบบบับ เบิ้ลซึ่งมีสมาชิกn=8มีขั้นตอนดั้งในรูปที่ 11.3 โดยรูปภายนอกทำงาน n-1=7 รอบ ในแต่ละรอบจะมีการสลับตำแหน่งเพียงครั้งเดียวหลังจากพบค่าที่มากที่สุดเพื่อ นำไปใช้ในตำแหน่งที่ถูกต้อง ในรอบแรกหลังจากการเปรียบเทียบค่าทั้งหมดพบว่าค่าที่มากที่สุดคือ 99 ในตำแหน่งอาร์เรย์ที่2 ก็ทำการสลับตำแหน่งกับค่า 77 ในตำแหน่งอาร์เรย์ที่ 7 หลังจากนั้นในรอบถัดไปก็ทำแบบเดิมกับค่าที่เหลือ จำนวนค่าที่เหลือก็ลดน้อยลงจนเหลือเพียงค่าเดียว ก็ไม่ต้องทำต่อจนจบการทำงาน
| 66 | 33 | 99 | 88 | 44 | 55 | 22 | 77 |
| 66 | 33 | 77 | 88 | 44 | 55 | 22 | 99 |
รอบที่ 1
| 66 | 33 | 77 | 88 | 44 | 55 | 22 | 99 |
| 66 | 33 | 77 | 22 | 44 | 55 | 88 | 99 |
รอบที่ 2
| 66 | 33 | 77 | 22 | 44 | 55 | 88 | 99 |
| 66 | 33 | 55 | 22 | 44 | 77 | 88 | 99 |
รอบที่ 3
| 66 | 33 | 55 | 22 | 44 | 77 | 88 | 99 |
| 44 | 33 | 55 | 22 | 66 | 77 | 88 | 99 |
รอบที่ 4
| 44 | 33 | 55 | 22 | 66 | 77 | 88 | 99 |
| 44 | 33 | 22 | 55 | 66 | 77 | 88 | 99 |
รอบที่ 5
| 44 | 33 | 22 | 55 | 66 | 77 | 88 | 99 |
| 22 | 33 | 44 | 55 | 66 | 77 | 88 | 99 |
รอบที่ 6
| 22 | 33 | 44 | 55 | 66 | 77 | 88 | 99 |
| 22 | 33 | 44 | 55 | 66 | 77 | 88 | 99 |
รอบที่7
รูปที่ 11.3ขั้นตอนการเรียงลำดับข้อมูลแบบเลือก
การจัดเรียงลำดับแบบเลือกมีการเปรียบเทียบเป็น o(n2)จำนวนการทำงานจะเพิ่มขึ้น เป็นยกกำลังสองเช่นกับการ จัดเรียงลำแบบบับเบิ้ล แต่จะทำงานได้เร็วกว่าเนื่องจากการย้ายค่าจะใช้เพียงo(n2)ในแต่ละรอบ จากตัวอย่างของทั้งสองแบบจะเห็นว่ามีการเปรียบค่าเท่ากัน คือ 28 (7+6+5+4+3+2+1)แต่การเรียงลำดับแบบบับเบิ้ลมีกาวรสลับบตำแหน่ง 16 ครั้ง ส่วนการจัดเรียงลำดับแบบเลือกสลับตำแหน่งเพียง 7 ครั้ง
การเรียงลำดับแบบแทรก
เช่น เดียวกับการจัดเรียงลำดับทั้งสองแบบที่ผ่านมาซึ่งการทำงานมีจำนวน n-1 รอบและเปรียบเทียบข้อทั้งหมดตามลำดับในอาร์เรย์ โดยแต่ระรอกบมีการแทรกค่าถัดไปเข้าในอาร์เรย์ย่อยด้านซ้าย และเป็นได้อาร์เรย์ย่อยด้านซ้าย และได้เป็นได้อาร์เรย์ย่อยที่จัดเรียงตามลำดับ ทีลักษณะแบบเดียวกับผู้เล่นไพ่ เมื่อได้รับไพ่จากการแจกก็จะนำมาแทรกไว้ในไพ่ที่ถืออยู่เพื่อให้ตัวเลขเรียง ตามลำดับและต้องมีการขยับไพ่ใบอื่นหรือตำแหน่งให้ถูกต้อง ดั้งในรูปที่ 11.4 และได้อัลกอริทึมการเรียงลำดับแบบแทรก
ตารางที่ 11.6 อัลกอริทึมการเรียงลำดับแบบแทรก
| 1.ทำขั้นตอน 2-5ซ้ำตั้งแต่ i=1จนถึง i=n-1 2. เก็บค่าของajไว้ที่ตัวแปลชั่วคราว 3.ค้นหาที่ดัชนี j_<I สำหรับค่า aj_>ai 4.ขยะค่าจากอาร์เรย์ย่อย {aj…ai-1} หนึ่งตำแหน่งไปยัง {aj+1…a} 5.นำค่าในตัวแปลชั่วคราวซึ่งเป็นของ ai ให้กับaj |
และเขียนเป็นฟังก์ชันแบบแทรก ได้เป็นตารางที่ 11.7
ตารางที่ 11.7 ฟังก์ชันเรียงลำดับแบบแทรก
| Void insertionsort (int key[], int size){ Int I, j, insert; For(i=1;i<size;i++){ Insert=key[i]; For(j=I;(j<0)&&(key[j-1]>insert);j–) Key[j]=key[j-1]; Key[j]=insert; } } |
ตัวอย่าง การเรียงลำดับแบบแทรกจะใช้อาร์เรย์ตัวเดียวกับที่ผ่านมาซึ่งมีสมาชิก n=8 และมีขั้นตอนดั้งในรูปที่ 11.5 โดยรูปภายนอกทำงาน 7รอบ ในแต่ระรอบจะมีการนำค่าตำแหน่งที่ยังมีค่าน้อยกว่า และค่าที่มากว่าจะขยับเข้ามาทางขวาหนึ่งตำแหน่ง หากมีค่ามากกว่าก็จะพบตำแหน่งที่ถูกต้องและเก็บค่าในตำแหน่งนั้น เช่น ในรอบที่ 4 ต้องการแทรกค่า 44 ในตำแหน่งอาร์เรย์ที่ 4 ไปทางซ้าย หลังจากเปรียบเทียบที่ละ ค่าจะพบตำแหน่งที่ถูกต้องอยู่ในตำแหน่งอาร์เรย์ที่ 1 ก็ทำการเก็บค่าซึ่งได้จากตัวแปล insret ในรอบถัดไปก็ทำค่าแบบเดิมกับค่าแบบเดิมกับค่าที่เหลือ จนกระทั่งทุกค่าถูกแทรกเข้าไปจนครบจึงจบการทำงาน
| 66 | 33 | 99 | 88 | 44 | 55 | 22 | 77 |
| 33 | 66 | 99 | 88 | 44 | 55 | 22 | 77 |
รอบที่ 1
| 33 | 66 | 99 | 88 | 44 | 55 | 22 | 77 |
| 33 | 66 | 99 | 88 | 44 | 55 | 22 | 77 |
รอบที่ 2
| 33 | 66 | 99 | 88 | 44 | 55 | 22 | 77 |
| 33 | 66 | 88 | 99 | 44 | 55 | 22 | 77 |
รอบที่ 3
| 33 | 66 | 88 | 99 | 44 | 55 | 22 | 77 |
| 33 | 44 | 66 | 88 | 99 | 55 | 22 | 77 |
รอบที่ 4
| 33 | 44 | 66 | 88 | 99 | 55 | 22 | 77 |
| 33 | 44 | 55 | 66 | 88 | 99 | 22 | 77 |
รอบที่ 5
| 33 | 44 | 66 | 55 | 88 | 99 | 22 | 77 |
| 22 | 33 | 44 | 55 | 66 | 88 | 99 | 77 |
รอบที่ 6
| 22 | 33 | 44 | 55 | 66 | 88 | 99 | 77 |
| 22 | 33 | 44 | 55 | 66 | 77 | 88 | 99 |
รอบที่7
รูปที่ 11.5 ขั้นตอนการเรียงลำดับข้อมูลแบบแทรก
ลักษณะ การทำงานของการเรียงลำดับแบบแทรกจะเป็นการหมุนไปทางขวา(Reqit Rotation) ของค่าบางส่วนหรือดลุ่มย่อยของคำ(Seqment) ในอาร์เรย์ดั้งในรูปที่ 11.6 เป็นรอบที่ 4 ในตำแหน่งอาร์เรย์ที่ 1ถึงตำแหน่งอาร์เรย์ที่ 4แต่ละค่าจะหมุนไปทางขวาหนึ่งตำแหน่งค่าที่อยู่ขวาสุดจะหมุนไปซ้ายสุด ก็จะเกิดเรียงตามลำดับ
เช่นเดียวกับการจัดเรียงลำดับแบบบับเบิ้ลและแบบเลือก การทำงานมีจำนวน n-1 รอบแต่ละรอบจะมีการหมุนเซ็กเม้นท์ในอาร์เรย์ การหมุนแต่ละครั้งอาจหมุนค่าตั้งแต่ละครั้งอาจหมุนค่าตั้งแต่ 1ถึง n ค่า และมีจำนวนการเปรียบเทียบค่าซึ่งเป็นค่าที่มีเซ็กเม้นโดยเฉลี่ยการหมุนจะ เป็นครึ่งของความยาวเซ็กเม้นทื่ค่าถูกเรียงลำดับก่อนหน้านี้ความยาวเฉลี่ย ของเซ็กเม้นท์จึงเท่ากับ n/2 และจำนวนในการเปรียบเทียบค่าเป็น n/4 ดั้งนั้นในกรณีเฉลี่ย (Averaqe Case) มีการเปรียบเทียบค่าเท่ากับ(n/4)(n-1) และในกรณีแย่ที่สุด(Worfst Case) มีการเปรียบเทียบค่าเท่ากับ (n/2)(n-1)
เนื่องจากการจัดเรียงลำดับแบบแทรกไม่มีการสลับตำแหน่งเช่นเดียวกับการจัดการ เรียงลำดับทั้งสองแบบที่พ่านมา จึงใช้การย้ายในการเปรียบเทียบกัน โดยการหมุน 4 ค่าเท่ากับ การย้ายค่า 4 ค่าจากตัวอย่างการจัดเรียงลำดับแบบบับเบิ้ลมีการย้ายค่า 32 ค่า ซึ่งไม่จำเป็นเสมอไปเนื่องจากการแบบแทรกมีการเปรียบเทียบค่าเท่ากับ (n/2)(n/1)ในทุกกรณี แต่ในกรณีเฉลี่ยของแบบแทรกจะเร็วกว่าเป็นสองเท่า คือ (n/4)(n/1)
อย่างไรก็ตาม ในกรณีเฉลี่ยแย่ที่สุดของการเรียงลำดับแบบแทรกมีการเปรียบเทียบส่วนกรณีดี ที่สุด (Best Case) มีการเปรียบเทียบเป็น o(n) โดยใช้เวลาเป็นเส้นตรงและเกิดขึ้นเมื่อแต่ละรอบมีการเปรียบเทียบค่าเพียง ครั้งเดียว ซึ่งหมายถึงทุกๆ ค่าในอาร์เรย์มีการจัดเรียงลำดับก่อนเรียบร้อยแล้ว
การทำงานอัลกอริทึมเป็นกานหาตำแหน่งที่ถูกค่าให้ค่าในลักษณะที่เป็นการหาร ตามลำดับต่อเนื่องจึงเรียกว่าการเรียงลำดับแนวตรง( Binary Insertion Sort) ซึ่งเป็นตังอย่างการใช้ไบนารี่ที่11.6 การเรียงลำดับแบบเชล์
การ เรียงลำดับแบบแทรกใช้เวลาเป็นเส้นตรงเมื่ออาร์เรย์ทีการจัดเรียงลำดับก่อน แล้วเท่านั้น สิ่งสำคัญคือการจัดเรียงลำดับที่ใช้เวลา เกือบเป็นเส้นตรงเมื่ออาร์เรย์เกือบจัดเรียงลำดับที่เสร็จเรียบร้อยแล้ว ซึ่งค้นพบโดย Donald Shell และแสดงได้เห็นว่าการจัดเรียงลำดับบนอาร์เรย์สามารถทำได้ดีกว่าเวลาที่ใช้ เป็นยกกำลังสอง
การจัดเรียงลำดับแบบเซล์หรือจำนวนลำดับแบบจำนวนเพิ่มๆค่อยลดลง (Diminishing Incremeny Sort จะใช้เรียงลำดับแบบแทรกกับกลุ่มย่อยของค่าตาม
ดับ กลุ่มย่อยเหล่านี้จะถูกเลือกใช้ในทิศทางพยายามให้ค่าถูกเรียงมากสุดก่อนที่ จะใช้ การเรียงลำดับแบบแทรก ก็จะได้เวลาการทำงานที่ใช้การเรียงลำดับแบบแทรกในแต่ละรอบเกือบเป็นเส้นตรง
กลุ่มย่อยจะถูกกำหนดด้วยตัวเลขในการกระโดดข้าม (Skip Number) และค่าที่อยู่ในกลุ่มย่อยเดียวกันก็จะห่างกันเท่าตัวเลข กระโดดข้ามคือ d=4 ก็จะได้ 4 กลุ่มย่อยที่ถูกจัดเรียงลำดับและความเป็นอิสระ ต่อกันไม่เกี่ยวข้อง ดั้งนี้
{S0, S4, S8,S12,…}
{S1, S5, S9,S13,…}
{S2, S6, S10,S14,…}
{S3, S7, S11,S15,…}
แต่ ละกลุ่มย่อยของทั้ง 4 กลุ่มสามารถถูกจัดเรียงลำดับที่เป็นอิสระต่อกัน โดยใช้โปรเซทเซอร์แยกกันและทำงานเป็นแบบขนาน (parallelizable) อัลกอริทึมการเรียงลำดับแบบเซลล์เป็นได้ดั้งนี้ในตารางที่ 11.8
ตาราง ที่ 11.8 อัลกอริทึมการเรียงลำดับแบบเซลล์
| 1.ให้ d=n/2 เป้นตัวเลขกระโดดข้าม 2. ทำขั้นตอน 3-4 ซ้ำ เมื่อ d ยังมากว่า 0 3. ใช้การเรียงลำดับแบบแทรกกับแต่ละกลุ่มย่อย d กลุ่ม {S0, Sd, S2d,S12,…} {S1, Sd+1, S2d+1,S3d+1,…} {S2, Sd+2, S2d+2,S3d+2,…} . . . {Sd-1, S2d-1, S3d-1,S4d-1,…} 4.กำหนดให้ d=d/2 |
และ เขียนลำดับฟังก์ชัน เรียงลำดับแบบเซลล์ได้เป็นตารางที่ 11.9 แบ่งออกเป็นฟังชันก์ชัน shebllSort เป็นหลักเพื่อกำหนดตัวเลขกระโดดข้าม และฟังก์ชัน skipSort ใช้เรียงลำดับแบบแทรกค่าห่างกันเท่ากับ d ตำแหน่ง
ตารางที่ 11.9 ฟังก์ชันเรียงลำดับแบบเซลล์
| Void skipSort (int key[],int size,int ,c, int d){ Int I, j, k; For(i=c+d;i<size; i=d){ K=key[i] J=1; While( (j> c)&&(key[j-d]>k)){ Key[j]=key[j-d]; j-=d; } Key[j]=k; } Void shellSort (int key[], int size){ Int d, j; For(d=asize/2;d>0;d/2) For (j=0; j<d; j++) skipSort(key,size, j ,d); } |
ตัวอย่าง การเรียงลำดับ แบบเซลล์จะใช้เช่นเดียวกับที่ผ่าน โดยมีขั้นตอนดั้งใน รูปที่ 11.8 ในรอบเราแบ่งการทำงานออกเป็น 4 กลุ่มย่อย คือ {ao, a4},{a1, a5},{a2, a6},{ao, a4},เพื่อเรียงลำดับของแต่ละกลุ่ม ในรอบสุดท้ายค่าทั้งหมด จะถูกจัดเรียงตามลำดับ จะเห็นว่าแต่ละกลุ่มย่อยจะมีการย้ายค่าเพียงสองครั้งเท่านั้น
| 66 | 33 | 99 | 88 | 44 | 55 | 22 | 77 |
| 44 | 33 | 99 | 88 | 66 | 55 | 22 | 77 |
| 44 | 33 | 99 | 88 | 66 | 55 | 22 | 77 |
| 44 | 33 | 99 | 88 | 66 | 55 | 22 | 77 |
| 44 | 33 | 99 | 88 | 66 | 55 | 22 | 77 |
| 44 | 33 | 22 | 88 | 66 | 55 | 99 | 77 |
| 44 | 33 | 22 | 88 | 66 | 55 | 99 | 77 |
| 44 | 33 | 22 | 77 | 66 | 55 | 99 | 88 |
รอบที่ 1
| 22 | 33 | 22 | 77 | 66 | 55 | 99 | 88 |
| 44 | 33 | 22 | 77 | 66 | 55 | 99 | 88 |
| 22 | 33 | 22 | 77 | 66 | 55 | 99 | 88 |
| 22 | 33 | 44 | 55 | 66 | 77 | 99 | 88 |
รอบที่ 2
| 22 | 33 | 44 | 55 | 66 | 77 | 99 | 88 |
| 22 | 33 | 44 | 55 | 66 | 77 | 99 | 88 |
รอบที่ 3
รูปที่ 11.8 –ขั้นตอนการเรียงลำดับข้อมูลแบบเซลล์
โดยทั่วไปการแบ่งกลุ่มย่อยที่มีขนาด m จะมีการเปรียบเทียบค่าไม่เกิน m/2เนื่องจากครึ่งหนึ่งของจำนวนค่าได้ถูกจัดเรียงเรียบร้อยแล้วในรอบก่อน หน้านี้ เช่น ต้องการเรียงลำดับ ค่า n=128 ในรอบแรกมการจัดเรียงลำดับ4 กลุ่มย่อยที่มีขนาดเท่ากับ 2 รอบที่ 32มีการเรียงลำดับกลุ่มย่อยที่มีขนาด เท่ากับ 4 และรอบที่ 3มีการจัดเรียงที่ ย่อยขนาดเท่ากับ 8 ซึ่งกลุ่มย่อยที่มีขนาด 8 จะมี 4 ค่าที่จัดเรียงเรียบร้อยแล้วแต่ในละกลุ่มจะมีกลุ่มย่อย 32 กลุ่ม การทำงานของการเรียงลำดับแบบเซลล์โดยเฉลี่ยจึงใช้เวลา o(m1แต่ยังถือว่าการทำงานยังใช้เวลาทรายยกกำลังสอง
