การเรียงลำดับเป็นกระบวนการของการจัดเรียงองค์ประกอบทั้งจากน้อยไปมาก (หรือ) จากมากไปหาน้อย
ประเภทของการจัดเรียง
ภาษา C มีเทคนิคการเรียงลำดับห้าแบบ ซึ่งมีดังนี้ -
- การเรียงลำดับฟอง (หรือ) การเรียงลำดับการแลกเปลี่ยน
- การเรียงลำดับการเลือก
- การเรียงลำดับการแทรก(หรือ) การเรียงลำดับเชิงเส้น
- การเรียงลำดับด่วน (หรือ) การเรียงลำดับการแลกเปลี่ยนพาร์ติชั่น
- ผสานการเรียงลำดับ (หรือ) การเรียงลำดับภายนอก
เรียงลำดับอย่างรวดเร็ว
เป็นอัลกอริทึมการแบ่งและพิชิต
- ขั้นตอนที่ 1 − เลือกองค์ประกอบจากอาร์เรย์ เรียกว่าเป็นองค์ประกอบ pivot
- ขั้นตอนที่ 2 − แบ่งองค์ประกอบอาร์เรย์ที่ไม่เรียงลำดับออกเป็นสองอาร์เรย์
- ขั้นตอนที่ 3 − หากค่าที่น้อยกว่าองค์ประกอบ pivot อยู่ภายใต้อาร์เรย์ย่อยที่หนึ่ง องค์ประกอบที่เหลือที่มีค่ามากกว่า pivot จะอยู่ในอาร์เรย์ย่อยที่สอง
ลองพิจารณาตัวอย่างด้านล่างซึ่ง
- P คือองค์ประกอบเดือย
- L คือตัวชี้ด้านซ้าย
- R คือตัวชี้ที่ถูกต้อง
องค์ประกอบคือ 6, 3, 7, 2, 4, 5.
ตอนนี้
- เดือยอยู่ในตำแหน่งคงที่
- องค์ประกอบด้านซ้ายทั้งหมดมีค่าน้อยกว่า
- องค์ประกอบที่เหมาะสมมีค่ามากกว่าจุดหมุน
- ตอนนี้ แบ่งอาร์เรย์ออกเป็น 2 อาร์เรย์ย่อยด้านซ้ายและด้านขวา
- นำพาร์ติชั่นด้านซ้ายไปใช้การเรียงลำดับอย่างรวดเร็ว
ตอนนี้
- เดือยอยู่ในตำแหน่งคงที่
- องค์ประกอบด้านซ้ายทั้งหมดมีน้อยและเรียงลำดับ
- องค์ประกอบที่เหมาะสมนั้นยิ่งใหญ่กว่าและเรียงตามลำดับ
- รายการที่จัดเรียงขั้นสุดท้ายจะรวมอาร์เรย์ย่อยสองอาร์เรย์เข้าด้วยกันคือ 2, 3, 4, 5, 6, 7
ตัวอย่าง
ต่อไปนี้เป็นโปรแกรม C เพื่อจัดเรียงองค์ประกอบโดยใช้เทคนิคการเรียงลำดับอย่างรวดเร็ว -
#include<stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
} ผลลัพธ์
เมื่อโปรแกรมข้างต้นทำงาน มันจะสร้างผลลัพธ์ต่อไปนี้ -
How many elements are u going to enter?: 10 Enter 10 elements: 2 3 5 7 1 9 3 8 0 4 Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9
