Google        youtube          psv       สพม.11

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

สำหรับบทนี้เป็นการกล่าวถึงเทคนิคในการสร้างจัดเรียงรับดับข้อมูล(Sortinq) ซึ่งเป็นกระบวนการที่คล้ายกับเทคนิค ในการค้นหาค่าข้อมูล(Record)ที่จะกล่าวในบทต่อไปการจัดเรียงในรับดับค่าของข้อมูลจะพิจารณาถึงรับดับก่อนหน้าและหลังแต่ละเรคคคอร์ดหรือทะเบียน(Recorf) โดยมีคีย์ที่นำมาใช้พิจารณาถึงรับดับก่อนหน้าและหลังของแต่ละเรคคอร์ดเพื่อประสิทธิ์ภาพการทำงานและง่ายต่อการเรียกใช้งาน การเรียงลำดับข้อมูลจึงเป็นกระบวนการเพื่อจัดการเรคคอร์ดให้จัดเรียงลำดับตามคีย์ เป็นเทคนิคในการค้นหาข้อมูลมีประสิทธ์ภาพมากขึ้น โดยมีการออกเป็น 2 ประเภทๆ หลักคือ
การเรียงลำดับภายใน 
การเรียงลำดับภายใน(Internal Sorting) เป็นหลักการทีมาใช้เมื่อนำข้อมูลทั้งหมดที่รวบรวมไว้มีขนาดเล็กเพียงพอ ที่จะเก็บไว้ และ ทำการเรียงลำดับภายในหน่วยความจำหลัก(Memorly) เวลาที่มักใช้ในการอ่านและเขียนเรคคอร์ดจะนำใช้พิจารณาถึงประสิทธิ์ภาพการเรียงลำดับข้อมูล แต่จะใช้เวลาในการเปรียบเทียบค่าของคีย์มาพิจารณา นอกจากนี้การเรียงลำดับภายในยังแบ่งออกเป็น2 ลักษณะ คือ การเรียงลำดับข้อมูลที่ใช้เฉพาะพื้นที่หน่วยความจำของ ตนเอง(Inplace Sort) และการเรียงลำดับข้อมูลที่ต้องใช้พื้นที่หน่วย ความจำเพิ่มเติมเข้ามาช่วยจัดเรียง
การเรียงลำดับภายนอก
การเรียงลำดับภายนอก(External Sortinq) เป็นหลักการที่นำมาใช้กับข้อมูลที่รวบรวมไว้เป็นจำนวนมากๆ ไม่สามารถเก็บไว้ในหน่วยความจำหลักได้หมดในคราวเดียวกัน แต่ต้องเก็บไว้ในหน่วย
ความจำหลักได้หมด ในคราวเดียวกัน แต่ต้องเก็บไว้ในหน่วยสำรอง เช่น เทปแม่เหล็กหรือจานแม่เหล็ก การเรียงข้อมูลจะกระทำได้พียงบางส่วน ในแต่ละครั้ง ประสิทธิ์ภาพในการเรียงลำดับแบบนี้จึงพิจารณาจากเวลาที่ใช้อ่านและเขียน เพื่อถ่ายโอนข้อมูลระหว่างความจำหลักกับความจำสำรอง
บางครั้งการเรียงลำดับการใช้กับเรคคอร์ดที่ค่าของคีย์ซ้ำกันได้ ทำให้กอริทึมการเรียง
ดับเรียกว่า สเตเปิ้ล(Stable Sort) เมื่อลำดับเรคคอร์ดที่มีค่าของคีย์ซ้ำกันได้เกมือนเดิมหลังจากการมีเรียงลำ เช่น เรคคอร์ด ที่ 5 และ 8 มีค่าของคีย์เท่ากัน หลังจากที่เรียงลำดับแล้วเรคคร์ดที่ 5 ยังคงมาก่อนเรคคอร์ดที่ 8 เหมือนจึงเรียกว่า การเรียงลำดับแบบสเตเบิ้ล แต่ถ้าหากเรคคอร์ดที่ 5 ไปอยู่หลังเรคคอร์ดที่ 8จะไม่เป็นสเตเบิ้ล การเรียงลำดับแบบสเตเบิ้ลมาใช้  เมื่อลำดับเดิมยังมีความสำคัญหรือมีความหมายบางอย่างในการใช้งาน เช่น การเรียงลำดับเรคคอร์ด ตามค่าของคีย์แต่คำนึงถึงเวลาของแต่ละคอร์ดที่บันทึกไว้
การเรียงลำดับข้อมูลนำมาใช้การจัดเรียงลำดับเรคคอร์ดตามค่าของคีย์ในแฟ้มข้อมูล(Fill)
ซึ่งส่วนใหญ่อัลกอริทึม ที่ใช้เป้ฯการเรียงลำดับมีการเปรียบเทียบ(Comparieon Sort) และในที่นี้จะใช้เป็นคีย์อย่างเดียวสำหรับการเรียงลำดับข้อมูลและเก็บอยู่ของอาร์เรย์มีการเปรียบอยู่สองค่าของสมาชิกของอาร์เรย์การเรียงลำดับตามค่าของคีย์  อาจใช้เป็นแบบจากค่าน้อยไปหามาก (Ascendinq) หรือให้เรียงลำดับจากค่ามากไปหาค่าน้อย(Desendinq) สำหรับการเรียงลำดับภายในจะใช้การเรียงลำดับมีการเรียงลำดับมีการเปรียบเทียบมาพิจารณาถึงประสิทธิ์ภาพ ซึ่งใช้เวลาน้อยที่สุดคือ O(n loq n) ขณะที่การเรียงลำดับมีการ       เปรียบเทียบ จะใช้เวลาน้อยที่สุด คือ O(n) ส่วนการเรียงลำดับภายนอกถึงแม้ใช้การเรียงลำดับมีการเปรียบเทียบแต่ใช้เวลาการทำงานน้อยกว่าเมื่อเทียบเวลาการทำงานของ I/O เพื่ออ่านและเขียนข้อมูลระหว่างหน่วยความจำหลักกับหน่วยความจำสำรองจึงไม่นำมาพิจารณา ในการเรียงลำดับข้อมูลจึงมีเทคนิคหรือวิธีอื่นๆมากมายซึ่งแบ่งออกเป็นประเภทต่างๆ ตามประสิทธิ์ภพการทำงาน ดั้งต่อไปนี้

1. การเรียงลำดับมีการเปรียบเทียบ O(n2)
การเรียงลำดับแบบดับเบิ้ล  (Bubble Sort)
การเรียงลำดับแบเลือก  (Selection Sort)
การเรียงลำดับแบแทรก  (Insertion Sort)
การเรียงลำดับแบบเชล์   (Shell Sort)
2.การเรียงลำดับมีการเปรียบเทียบ O(n Loq n)
การเรียงลำดับแบบผสาน  (Merqe Sort)
การเรียงลำดับแบบรวดเร็ว  (Quick Sort)
การเรียงลำดับแบบฮีพ  (Heap Sort)
3.การเรียงลำดับไม่มีการเปรียบเทียบ
การเรียงลำดับแบบนับจำนวน(Countinq Sort)
4.การเรียงลำดับและผสานแฟ้มข้อมูล
การเรียงลำกับแบบบับเบิ้ล 
เป็นอัลกอริทึม การจัดเรียงลำดับข้อมูลที่เป็นมาตรฐานโดยการทำงานเป็นการเปรียบเทียบค่าสมาชิกของอาร์เรย์ที่อยู่ติดกันและมีการสลับตำแหน่งกันเมื่อค่าทั้งสองไม่เรียงลำดับในลักษณะที่เปรียบเทียบทีลพคู่ตามลำดับจากคู่ที่อยู่ด้านซ้ายไปยังด้านขวาค่าที่มากที่สุดจะย้ายไปยังส่วนท้ายของอาร์เรย์จากการเปรียบเทียบและขยับทีละตำแหน่ง เช่นเดียวกับฟองอากาศน้ำ ฟองที่ใหญ่กว่าจะลอยชนฟองที่เล็กกว่า แทรกไปยังผิวน้ำ
ในรอบแรกการทำงานจะย้ายค่ามากที่สุดไปยังส่วนท้ายของอาร์เรย์ หลังจากนั้นทำแบบเดิมกับส่วนย่อยของอาร์เรย์  คือ n-1 ที่ยังไม่เรียงลำดับ นำค่ามากที่สุดรองลงมาไปไว้ยังตำแหน่ง ที่ถูต้อง และเรียงตามลำดับแบบบับเบิ้ลดั้งใน
ตารางที่ 11.1 อัลกอริทึมการเรียงลำดับแบบบับเบิ้ล

1.      ทำขั้นตอน 2 ซ้ำ ตั้งแต่ i=n-1 จนถึง i=1
2.   ทำขั้นตอน 3 ซ้ำ ตั้งแต่   j=0  จนถึง  j=i-1
3.   ถ้าค่า a,น้อยกว่า aj+1  ให้สลับตำแหน่งกัน

และเขียนเป็นฟังก์ชันเรียงลำดับแบบบับเบิ้ลได้เป็น  ตารางที่11.2
ตารางที่ 11.2 ฟังก์ชันเรียงลำดับแบบบับเบิ้ล

Void   bubblesort  (int key[], int size){
Int i, j;
For ( i=size-1;  i>0; i–)
If (Key[j]>key[j+1])
Swap(&key[j],&key[j+1]);

เมื่อนำการเรียงลำดับแบบบับเบิ้ลมาใช้กับอาร์เรย์ที่มีสมาชิก (66,33,99,88,44,55,2,77)  จะมีขั้นตอนดั้งในรูปที่  11.1 โดยรูปภายในจะทำการย้ายค่าที่มากที่สุดไปไว้ยังตำแหน่งที่ถูกต้องในแต่ละรอบโดยการสลับตำแหน่งที่ติดกัน ส่วนรูปภายนอกเป็นการกำหนดรอบให้มีการหนดรอบให้มีการย้ายทุกๆค่าในอาร์เรย์ ซึ่งมีสมาชิก n=8 จึงมีการทำงาน n-1=7รอบ เช่น ในระบบแรกจะ  นำค่าติดกัน ส่วนรูปภายนอกเป็นการกำหนดรอบให้มีการย้ายๆทุกๆ ค่าในอาร์เรย์ซึ่งมีสมาชิก n = 8 จึงมีการทำงาน n-1=7 รอบ เช่น ในรอบแรกจะนำค่าที่ติดกันมาเปรียบเทียบกันที่ละคู่ทั้งหมดในอาร์เรย์ ค่าที่มากว่าจะถูกขยับไปเรื่อยๆ จนถึงสุดท้ายของอาร์เรย์หลังจากนั้นในรอบถัดไปก็ทำเฉพาะในส่วนที่เหลือ  และจำนวนการทำซ้ำจะลดลงตามจำนวนค่าเหลือเพียงค่าเดียวก็ไม่ต้องทำต่อจบการทำงาน

ทำงาน
0

66 33 99 88 44 55 22 77
33 33 99 88 44 55 22 77
33 33 99 88 44 55 22 77
33 33 88 99 44 55 22 77
33 33 99 44 99 55 22 77
33 33 99 44 55 99 22 77
33 33 99 44 55 22 99 77
33 33 99 44 55 22 77 99

                          0
1
2
3
4
5
6
7

                                                 รอบที่ 1

33 66 88 44 55 22 77 99
33 66 88 44 55 22 77 99
33 66 88 44 55 22 77 99
33 66 44 88 55 22 77 99
33 66 44 55 88 22 77 99
33 66 44 55 22 88 77 99
33 66 44 55 22 77 88 99

0
1
2
3
4
5
6
รอบที่ 2

33 66 44 55 22 77 88 99
33 66 44 55 22 77 88 99
33 44 66 55 22 77 88 99
33 44 55 66 22 77 88 99
33 44 55 22 66 77 88 99
33 44 55 22 66 77 88 99

0
1
2
3
4
5

                                                 รอบที่ 3

33 44 55 22 66 77 88 99
33 44 55 22 66 77 88 99
33 44 55 22 66 77 88 99
33 44 22 55 66 77 88 99
33 44 22 55 66 77 88 99

0
1
2
3
4

รอบที่ 4

33 44 22 55 66 77 88 99
33 44 22 44 66 77 88 99
33 22 44 55 66 77 88 99
33 22 44 55 66 77 88 99

0
1
2
3

รอบที่ 5

33 22 44 55 66 77 88 99
22 33 44 55 66 77 88 99
22 33 44 55 66 77 88 99

0
1
2

รอบที่ 6

22 33 44 55 66 77 88 99
22 33 44 55 66 77 88 99

0
1

รอบที่ 7

รูปที่ 11.1 ขั้นตอนการเรียนลำกับข้อมูลแบบบับเบิ้ล

ในแต่ละรอบในการทำงานหลังจากเปรียบเทียบค่าแจมีการสลับตำแหน่งของค่าอาจมีการสลับตำแหน่งของค่าที่ไม่โรงเรียนตามลำดับ ซึ่งจะใช้ฟังก์ชัน swap  ให้การสลับตำแหน่งดั้งในตารางที่ 11.3
ตาราง 11.3 ฟังก์ชันการสลับตำแหน่ง

Void swap (int *l, int &r){
Int tmp=*l;
*L=*R;
*R=tmp;

ประสิทธิภาพการจัดเรียงแบบบับเบิ้ลพิจารณาได้จากตารางที่11.2 ลูปภายนอกมีการทำงาน n-1 ครั้งโดยตัวแปร I ทำงานจากค่า 0 จนถึง i=1 และการวนซ้ำแต่ละครั้งมีการเปรียบเทียบค่าทั้งหมดจึงเท่ากับ
(n-1)+(n-2)+(n-3)+…..+3+2+1
ผลรวมทั้งหมดเท่ากับ(n(n-1)/2ถ้าหากค่า n มีขนาดใหญ่มากการทำงานจะเข้าใกล้ n2/2 จะอยู่ในรูปแบบของ n2 ซึ่งทำให้การจัดเรียงรับดับแบบบับเบิ้ลมีการเปรียบเทียบเป็น 0(n2)จำนวนการทำงานจะเพิ่มขึ้นเป็นยกกำลังสอง (Quabratic) หมายความว่า ขนาดของอาร์เรย์เพิ่มขึ้นเป็น2เท่า และจำนวนครั้งในการทำงาน จะเพิ่มขึ้นเป็นสี่เท่า
                          
การเรียงลำดับแบบผสาน 
                            การจัดเรียงลำดับแบบต่างๆ ที่ได้ผ่านมา จะเห็นว่าเวลาที่ต้องใช้ในการจัดเรียงลำดับไม่เร็วกว่าหรืออยู่ในช่วงของ o(n2) สำหรับการจัดเรียงแบบที่จะกล่าวถึงใช้ o(n LOQ)  และเป็นเวลาที่จัดเรียงลำดับมีการเปรียบเทียบค่าที่ไม่สามารถทำงานได้ เร็วกว่านี้ ซึ่งการจัดเรียงลำดับมีอยู่หลายแบบ และ เป็นมาตรฐานโดยใช้เวลาที่ดีที่สุด ตารางที่ 11.0 อัลกอริทึมการเรียงลำดับแบบผสาน

1.  ถ้าค่าในกลุ่ม(Sequence) มีจำนวนมากกว่าหรือเท่ากับ 2 ให้ทำขั้นตอนที่ 2-5
2. ให้ am เป็นค่าที่อยู่ตรงกลางของค่าทั้งหมดในกลุ่ม
3. ทำการเรียงลำดับค่าที่อยู่ในกลุ่มย่อย (Sequence)   ที่มาก่อนหรือด้านซ้ายของค่า am
4. ทำการเรียงลำดับค่าที่อยู่ในซึ่งเป็นค่าที่เหลือจากกลุ่มย่อยแรกคือ ด้านขวาของค่า am
5. ทำการผสานค่าจากทั้งห้องสมุดที่จัดเรียงลำดับเรียบร้อยแล้ว

อัลกอริทึมทำได้ทีการมีการทำงานแบบรีเคอร์ชีฟ(Recuisiv) โดยในตอนที่ 3 และ 4 มีการเรียกตัวเองขึ้นมาทำงาน และมีอัลกอริทึมย่อยทำงานอย่างผสมผสาน ค่าจากสองกลุ่มย่อยโดยการเปรียบเทียบค่าที่ละคู่จากสองกลุ่มย่อย ดั้งในรูปที่ 11.9 และนำค่าที่น้อยกว่าไปเก็บไว้ยังกลุ่มที่ รับค่าเก็บไว้ต่อจากค่าก่อนหน้านี้ เมื่อทำหมดทั้งสองค่าทั้งสองกลุ่ม ก็จะได้ค่าทั้งหมดมีการจัดเรียงลำดับ

รูปที่ 11.9 วิธีการผสานได้เป็นตารางที่ 11.11 มีฟังก์ชันหลัก คือ merqeSort ที่ทำงานแบบ  บีเคอร์ชิฟ และฟังก์ชัน  merqe ใช้ผสานค่าให้เรียงตามลำดับ
ตารางที่ 11.11 ฟังก์ชันเรียงลำดับแบบผสาน

Void merge int key[], int lower,int middle int upper){
Int i=lower;
Int j=middle;
Int k=0;
Int *aTemp=malloc(sizeof(int)*(upper-lower) );
If(key[middle-1]>key[middle]){
While( (i<middle)&&(j<upper) ) {
aTemp[k++]=key[i++];
else
aTemp[k++]= key[j++];
}
While(i<middle)
aTemp[k++]=key[i++];
While(j<middle)
aTemp[k++]= key[j++];
i=0;
while(i<k)
key[lower++]=aTemp[i++];
}
Void mergeSort (int key[], int lower,int upper){
If (upper-lower>=2){
Int middle=(lower+upper){
mergeSort(key,lower+midde);
mereSort(key,middle,upper);
merge(key,lower,middle,upper);
}

ฟังก์ชัน mereSort ทำการแบ่งอาร์เรย์เป็นอาร์เรย์ย่อย (Subarray) จนกว่าจะมีขนาดเล็กลงเหลือ 0 หรือ 1 จากนั้นนำแต่ละส่วนมาผสานกันรวมกันจนได้ขนาดเดียวกันกลับมาเท่าเดิม  ส่วนฟังก์ชันจะถูกเรียกให้ผสานค่าจากสองกลุ่ม ให้เรียงตามลำดับและต้องใช้อาร์เรย์ชั่วคราว (Temporaoy Array) เพื่อจะรวบรวมค่าที่จะการผสานกันและทำการคัดลอกกลับไปยังตำแหน่งเดิมของอาร์เรย์ย่อยตัวเดิม
ตัวอย่างการเรียงลำดับแบบผสานในดั้งรูป 11.10 โดยใช้อาร์เรย์ตัวเดิม ซึ่งจะถูกแบ่งครึ่งไปเรื่อยๆ จาก 1 อาร์เรย์ เป็น 2 อาร์เรย์ย่อย เป็น 4 อาร์เรย์ย่อย และเป็น 8 อาร์เรย์ย่อย เรียงลกดับค่า โดยเริ่มทำในส่วนด้านซ้ายจากนั้นจึงมาทำด้านขวาตามลำดับมาเลื่อยๆ จนมาถึงการผสานครั้งสุดท้ายก็จะได้เป็นอาร์เรย์ที่มีค่าทั้งหมดจัดเรียงตามลำดับ

66 33 99 55 88 22 44 77

88 22 44 77
66 33 99 55

99 55
44 77
66 33
88 22

66
33
99
55
88
22
44
77

22 88
44 77
33 66
55 99

33 55 66 99
22 44 77 88
22 33 44 55 66 77 88 99

จากคัวอย่างเป็นกระบวนการแยกและรวมกัน โดยค่าที่จัดเรียงมีทั้งหมด 8 ค่า มีการแยกค่าออก 3 ระดับ การทำงานทั้งหมดมี 6 ระดับ และเป็นสองเท่า ของจำนวนเวลา n ที่ถูกการหารครึ่งจากการหารด้วย 2 เท่า ได้เป็นไนบรารี่ลอกการิทึม (Binary Loqarithm) ของ n Loq n การทำงานทั้งหมดมีจึงมี (2 Loq n) ระดับในการเรียงระดับค่า โดยแต่ระดับมีการเปรียบเทียบทุกค่า จึงเท่ากับ n ก็จะได้เปรียบเทียบค่าทั้งหมด
การเรียงลำดับแบบรวดเร็ว 
การเรียงลำดับแบบรวดเร็วเป็นอัลกอริทึมอีกแบบที่ทำด้วยวิธีการแบ่งและยึดรวมกัน
(Divde-and-Conquer) และใช้รีเคอร์ชิฟ ซึ่งดรณีเฉลี่ยจะใช้เวลา O(n Loq n) คิดค้นโดย C.A.R. Hoare เช่นเดียวกับการเรียงลำดับแบบผสานที่การทำงานแบ่งเป็นส่วน จะแบ่งค่าในกลุ่มออกเป็นสองกลุ่มย่อยที่แยก ในการแบ่งส่วน ขั้นตอนที่สองเป็นการเรียงลำดับแต่ละกลุ่มย่อยที่ถูกแบ่งแบบเคอร์ชิฟ และอัลกอริทึมในการจัดเรียงลำดับแบบรวดเร็วได้เป็นดั้งในตารางที่ 11.12
ตารางที่ 11.12  อัลกอริทึมการเรียงลำดับแบบรวดเร็ว

1.ถ้าค่าในกลุ่มมีจำนวนมากกว่าหรือเท่ากับ 2 ให้ทำขั้นตอนที่ 2-4
2.ให้ค่าแรก  ap  เป็นแกนหลัก แบ่งส่วนในกลุ่มออกเป็น {ap,…aq…1} และได้เป็น 3 กลุ่มย่อย
3.ทำการเรียงลำดับค่าที่อยู่ในกลุ่มย่อย x
4.ทำการเรียงลำดับค่าที่อยู่ในกลุ่มย่อย y

เมื่อเขียนเป็นฟังก์ชัน เรียงลำดับแบบรวดเร็วได้เป็นตารางที่ 11.13 มีฟังก์ชันหลัก คือ quickSort ที่ทำงานแบบรีเคอร์รีเคอร์ซิฟ  และมีฟังก์ชัน partition ใช้สำหรับแบ่งกลุ่มออกเป็นกลุ่มด้านขวาที่มีค่า
ตารางที่ 11.13 ฟังก์ชันเรียงลำดับแบบรวดเร็ว

Int partion(int key[] int lower int upper){
Int pivot=key[lower];
Int down=lower;
Int up=upper;
While(down<up){
While (key[down]<=pivot)&&(down<up){
Down++;
While (key [up]>pivot)
Up–;
If(down<up)
Sawp(&key[down],&key[up]);
}
Key[lower]=key[up];
Key[up]=pivot;
Return up;
}
Void quickSort(int key[], int lower,int upper){
If(upper-lower>=1){
Int pivot=partition(key,lower,upper);
quickSort(key,lower,pivot-1);
quickSort(

ตัวอย่างการเรียงลำดับแบบรวดเร็วดั้งในรูปที่ 11.11 โดยใช้อาร์เรย์ตัวเดิม ซึ่งครั้งแรกจะทำการแบ่งครึ่งโดยกำหนดให้ค่าแรกซ้ายมือเป็นแกนหลัก ต่อจากนั้นอ่านค่าทางขวามือสุดถอยกลับลงมาเลื่อยๆจนสินสุดเมื่อพบค่าที่น้อยกว่าค่าที่น้อยกว่าค่าของแกนหลัก แล้วนำค่าทั้งสองสลับตำแหน่งกัน ทำเช่นนี้จนกระทั้งการอ่านขึ้นกับการอ่านลงมาพบกันก็ใช้ค่าของตำแหน่งนั้นสลับตำแหน่งกับค่าแกนหลัก และเป็นตำแหน่งที่ถูกต้อง ในการเรียงลำดับ เช่น ในครั้งแรกให้ค่า 66 เป็นแกนหลัก อ่าขึ้นไปจนหยุดค่าที่ 99 และอ่าลงมาอยู่ที่ 22 จึงสลับตำแหน่งกัน ทำต่อพบที่ค่า 88 กับ 55 จึงสลับตำแหน่งกัน สุดท้ายเมื่ออ่านขึ้นและอ่านลงมาพบกันจึง สลับตำแหน่งของค่า 55 กับ 66 ซึ่งเป็นแกนหลักและอยู่ในตำแหน่งที่ถูกต้อง จากนั้นทำส่วนที่ เหลือทั้งด้านซ้ายและด้านขวาแบบเดิมโดยการรีเคอร์ซีฟจนเหลือเพียงค่าเดียวในกลุ่มย่อยจึงจบการทำงาน

66 33 99 44 88 55 22 77
66 33 22 44 88 55 99 77
66 33 22 44 55 88 99 77
55 33 22 44 66 88 99 77
88 99 77
88 77 99
77 88 99
55 33 22 44
44 33 22 55
44 33 22
22 33 44
22 33
22 33
22 33 44 55 66 77 88 99

รูปที่ 11.11 ขั้นตอนการเรียงลำดับข้อมูลแบบรวดเร็ว

                   การเรียงลำดับแบบรวดเร็วคล้ายกับการเรียงลำดับแบบผสาน ทั้งสองแบบ ใช้วิธีการแบ่งและยึดรวมกันเป็นแบบรีเคอร์ชิฟ ดั้งนั้น เวลาที่ใช้ทำงานในกรณีเฉลี่ยจึงเท่ากับ o(n Loq n) อย่างไรก็ตามการเรียงลำดับแบบรวดเร็วมีความซับซ้อนมากว่า ในกรณีแย่สุด คือ การเรียง  ลำดับแบบรวดเร็วจะใช้เวลา (n2) เกิดขี้นทุกค่าในอาร์เรย์  มีการจัดเรียงลำดับก่อนแล้ว ทำให้การแบ่งส่วนแต่ละครั้ง ไม่มีการย้ายแกนของหลักจะอยู่ด้านซ้ายเสมอและได้กลุ่มย่อย ด้านขวาด้านที่  ลดขนาดเพียงค่าเดียว การทำงานจึงเป็น n-1 และมีการเปรียบเทียบค่าเท่ากับ o(n) จึงใช้เวลาเปรียบเทียบค่า o(n Loq n)

รูปที่ 11.12 ลักษณะการเรียงลำดับข้อมูลแบบรวดเร็วในกรณีดีที่สุด
จะเห็นว่าค่าของแกนหลักมีความสำคัญต่อประสิทธิภาพการทำงาน จึงต้องมีวิธีการเข้ามาช่วยในการเลือกค่าที่จะมาเป็นแกนหลัก เพื่อให้ค่าเก็บอยู่ไกล้ตำแหน่งตรงวกลางมากที่สุดรวดเร็วในกรณี เฉลี่ยเท่ากับ o(n  Loq n) ส่วนกรณีแย่ที่สุด จะใช้เวลา o(n2) แต่ก็ถือว่าเป็นแบบที่ใช้งาน ไม่ต้องใช้หน่วยความจำเพิ่มเติม การเรียงลำดับแบบฮีพ ที่ผ่านมาการจัดเรียงลำดับแบบผสานและแบบรวดเร็วใช้เวลาในการทำงานเท่ากับ o(n Loq n) ซึ่งดีกว่าการจัดเรียงลำดับที่ต้องใช้เวลา O(n2) ด้วยปรปะสิทธิ์ในการเปรียบเทียบ n ค่าที่ใช้เวลาเพียง o(n Loq n) แทนที่ต้องใช้เวลา o(n) อัลกอริทึม ทำงานโดยวิธีการแบ่งและยึดรวมกัน (Divide-and-Conquer)

รูปที่ 11.13 วิธีการจัดเรียงลำดับข้อมูลแบบฮีพ
แนวคิดของการเรียงลำดับแบบฮีพเหมือนกับการนเรียงลำดับแบบเลือก คือ เลือกค่าที่ มากที่สุดจากกลุ่มของค่าที่ยังเหลืออยู่ และยังไม่จัดเรียงลำดับ จากนั้นสลับตำแหน่งให้ถูกต้อง ซึ่งใช้เวลาการทำงานเท่ากับ n-1 เป็นเส้นตรงกับการเรียงลำดับแบบเลือก ที่ใช้เวลาเป็นอัลกอริทึม
ตารางที่ 11.14 อัลกอริทึมการเรียงลำดับแบบฮีพ

1.สร้างฮีพเพื่อเก็บค่าในกลุ่ม (Sepuence)
2.ทำขั้นตอน 3-4ซ้ำตั้งแต่ i=n-1จนถึง i=1
3.สลัลตำแหน่งกับระหว่าง a กับ a
4.ทำการฮิฟปิฟาย

การเรียงลำดับแบบฮีพแบ่งการทำงานออกเป็น  2 ช่วง คือ ช่วยการสร้างฮีพ กับช่วง ปรับปรุงฮีพให้จัดเรียงใหม่  เมื่อเขียนเป็นฟังก์ชัน หลัก

ตารงที่ 11.15 ฟังก์ชันเรียงลำดับแบบฮีพ

Void heapify(int key[],int father, int size){
Int tmp=key[father*2+1<size; father=child){
Int child;
For (;father*2+1<size; father=child){
Child=father*2+1;
If(child<size-1&& key[child+1]>[child] )
Child++;
If(key[child]>tmp
Key[father]=key[child];
Else
Break;
}
key[father]=tmp;
}
void herapsort( int key[],int size){         int I;
for(i=size/2; i>=0;i–)
heapify(key-1;I,size);
or(i=size=1;i>0;i–){
swap(&key[0],&key[i];
heapiffy(key,o,.i);
heapify(key,o,i);
}
}

ตัวอย่างการเรียงลำดับแบบฮีพจะใช้อาร์เรย์ที่ผ่านมา โดยเริ่มต้นเป็นการสร้างฮีพและจัดลำดับให้ถูกต้อง ดั้งในรูปที่ 11.14 ซึ่งแสดงในลักษณะที่เป็นเนบรารี่ทรีละอาร์เรย์ และการทำงานให้ฟังก์ชัน โดยเริ่มที่ โหนดตำแหน่งตรงกลาง คือ 4 เพื่อเปรียบเทียบค่าขิงโหนดพ่อ กับลูกมีค่ามากกว่า จะสลับตำแหน่งกัน และทำงานแบบเดิมทุก
โหนดถัดลงมาจนถึงโหนด 0 เช่น ในรอบที่ 4 หรืออาร์เรย์  4 หรืออาร์เรย์ 4 ไม่มีโหนดลูกจึงไม่มีการเปรียบเทียบ ในรอบที่ 5 เริ่มที่โหนด 0 หรืออาร์เรย์  0 เมื่อเปรียบเทียบกับโหนด 1 และ 2 พบว่าโหนด 2 มีค่ามากกว่าจึงสลับตำแหน่งกัน ต่อจากนั้นที่โหนด 2 เปรียบเทียบกับ โหนด 5 และ 6 พบว่าไม่มากกว่า จึงหยุดทำงาน และเป็นไปตามคุณสมบัติของฮีพที่โหนดพ่อมี ค่ามากกว่าโหนดลูก โดยโหนด 0 หรืออาร์เรย์  หรืออาร์เรย์ คือ 99

66
99
44
33

88
22

55

77
66 33 99 55 88 22 44 77

ฮีพ 1

66
99
44
33

88
22

77

55
66 33 99 77 88 22 44 55

ฮีพ 2

66
99
44
33

88
22

77

55
66 33 99 55 88 22 44 55

ฮีพ 3

66
99
44
88

33
22

77

55
66 88 99 77 33 22 44 55

ฮีพ 4

99
66
44
88

33
22

77

55
99 88 66 77 33 22 44 55

ฮีพ 5

รูปที่ 11.14 การสร้างฮีพและจัดลำดับข้อมูลตามคุณสมบัติของฮีพ
หลังจากสร้างฮีพจะเป็นการนำค่าที่มากที่สุดสี่โหนด 0 สลับตำแหน่งกับโหนดสุดท้ายก็ได้ค่ามากที่สุดอยู่ในตำแหน่งที่ถูกต้อง จากนั้นทำแบบเดิมกับค่าที่เหลือตั้งแต่ n-1 โหนดจนเหลือโหนดเดียวพร้อมกับปรับปรุงฮีพให้เป็นไปตามคุณสมบัติและการปรับปรุงเริ่มที่โหนด 0 ทุกครั้ง ดั้งในรูปที่ 11.14 เช่นหลังจากสลับตำแหน่งครั้งแรกระหว่างโหนด 7 และมาเกี่ยวข้องอีก จากนั้นปรับปรุงฮีพครั้งแรกจะมีการย้ายค่า ระหว่างโหนด 0.1และ 3 ค่าที่มีมากกว่าจะถูกย้ายไปอยู่ด้านบน คือ 88ส่วนค่าน้อยกว่าจะถูกย้ายลงมาล่างคือ 55 เมื่อสลับตำแหน่งครั้งที่ 2 ส่วนค่าน้อยกว่าจะถูกว่าไว้ด้านล่าง คือ 44 ทำแบบเดิมใจนถึงการสลับตำแหน่งครั้งที่ 7 และปรับปรุงฮีพ ครั้งที่ 7ที่เหลือเพียงโหนดค่าเดียวจึงจบการทำงาน

 

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