Google         youtube            psv            สพม.11

การเรียงลำดับแบบเลือก 
                เช่น เดียวดับดารจัดเรียงลำดับแบบบับเบิ้ลซึ่งการทำงานจะมีจำนวน 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แต่ยังถือว่าการทำงานยังใช้เวลาทรายยกกำลังสอง

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s