Quick Sort

Quick Sort
เป็นอีกวิธีที่เหมาะกับลิสต์ขนาดใหญ่ และเป็นวิธีเรียงข้อมูลที่ให้ค่าเฉลี่ยของเวลาที่ใช้น้อยที่สุดเท่าท ี่ค้นพบวิธีหนึ่ง อย่างไรก็ดีเราต้องใช้สแตกขนาด log2n สำหรับเป็นตำแหน่งของลิสต์ย่อยที่ยังไม่ได้เรียงและเวลาที่ใช้ในกรณีเลวร้ายที่สุด จะไม่ดีกว่าแบบ O(n2)

สมมติ A(K1,K2,…,Kn) เป็นลิสต์ของค่าหรือเรคอร์ดที่ยังไม่ได้เรียง เราจะเลือก K1 จากนั้นจะแบ่งลิสต์ A นี้ออกเป็น 2 ลิสต์ย่อย S1 และ S2 โดยที่

S1 ประกอบด้วยเรคอร์ดที่มีค่าคีย์น้อยกว่า K1
S2 ประกอบด้วยเรคอร์ดที่มีค่าคีย์น้อยกว่า K1

นั่นคือเราสามารถเขียนลิสต์ A ได้ดังนี้ {
S1 } < X < {S2}
โดยที่ลิสต์ {S1 } และ {S2} เป็นค่าต่าง ๆ ที่ยังไม่ได้เรียง จากนั้นก็ทำวิธีดังกล่าวซ้ำกับ {S1 } และ {S2} ตามลำดับ (อย่างรีเคอร์ซีฟ) ในที่สุดก็จะได้ลิสต์ที่เรียงตามที่ต้องการ

การเรียงข้อมูลจะเริ่มโดยใช้พอยน์เตอร์ 2 ตัวคือ F และ R ให้ F มีค่า 1 ซึ่งก็คือชี้ไปยังค่าคีย์ตัวแรก ส่วน R มีค่าเท่ากับ n นั่นคือชี้ไปยังค่าคีย์ตัวสุดท้ายในลิสต์ การเปรียบเทียบจะการะทำระหว่างค่าที่ถูกชี้โดย FและR (อย่าลืมว่าจุดประสงค์ของเราคือการแบ่งลิสต์นี้ออกเป็น 2 ลิสต์ย่อย โดยใช้ค่า K1 เป็นตัวเปรียบเทียบ ฉะนั้นพอยน์เตอร์ที่ชี้ไปยัง K1 ไม่ว่าจะเป็น F หรือ R จะไม่เป็นตัวเลื่อนไปยังตำแหน่งอื่น) ทุกครั้งที่มีการเปรียบเทียบจะมีการเลื่อนพอยน์เตอร์ F ไปข้างหน้า นั่นคือจากซ้ายไปขวา หรือ R จะเลื่อนถอยหลัง นั่นคือจากขวาไปซ้าย การจะเลื่อนพอยน์เตอร์ตัวใดให้ใช้กฏต่อไปนี้ "ให้เลื่อนพอยน์เตอร์ตัวที่ไม่ใช่ชี้ไปยังค่า K1 หรือ ที่ทำหน้าที่ K1 ในการเรียงเที่ยวนั้น เมื่อ F พบ R ที่ค่าK1 ก็เป็นอันว่าเสร็จสิ้นการเรียงเที่ยวนั้น " สมมติให้ชุดคีย์ที่จะเรียงมีดังนี้ (27,15,22,37,11,59,18,50,42)

การเรียงแถวที่ 1

[Only admins are allowed to see this image]

ณ จุดนี้ คีย์ 27 ได้แบ่งลิสต์ที่กำหนดให้เป็นลิสต์ย่อย 2 ลิสต์
ดังนี้ (18,15,22,11) 27 (59,37,50,42)

เนื่องจากมีลิสต์ย่อย (sublist) 2 ลิสต์ย่อย จึงต้องชะลอการเรียงของลิสต์ย่อยชุดหลังไว้การจะจำว่าต้องเรียงลิสต์ (59,37,50,42) ภายหลังนั้น ทำได้โดยผลัก (push) ค่า (6,9) ซึ่งผลักค่า (6,9) ซึ่งหมายถึงค่าที่ 6 ถึงค่าที่ 9 ในอาร์เรย์ A ไว้ในสแตก ทุก ๆ ครั้งที่มีการแตกเป็นลิสต์ย่อย ให้ผลกักแอดเดรสของค่าที่ยังไม่ได้เรียงไว้ในสแตก ในภายหลังเมื่อ POP สแตกจะได้ลิสต์ย่อยซึ่งต้องทำการเรียงอีก (โดยวิธีเดียวกัน)

เนื่องจากลิสต์ย่อย (22) มีค่าเดียวจึงไม่จำเป็นต้องเก็บแอดเดรสของมันในสแตก นั่นคือเท่ากับว่าค่า 22 อยู่ที่ตำแหน่งที่ถูกต้องของมันแล้ว

merge sort เป็นวิธีการเรียงข้อมูลที่มีความสำคัญมาก เพราะเป็นวิธีสำคัญในการเรียงข้อมูลขนาดใหญ่ (การเรียงแบบภายนอก) วิธีการเรียงจะเริ่มกระทำครั้งละ 2 ค่า ซึ่งจะได้ลิสต์ย่อยจำนวน n/2 ลิสต์ แต่ละลิสต์มี 2 ค่า จากนั้นจะทำการ merge sort ต่ออีกครั้งละ 2 ลิสต์แล้วจะได้ลิสต์ที่เรียงแล้ว จำนวน n/4 ลิสต์ แต่ละลิสต์มี 4 ค่า ทำเช่นนี้ไปเรื่อย ๆ จนในที่สุดจะทำการ merge sort 2 ลิสต์ สุดท้ายเข้าด้วยกัน จะได้ลิสต์ที่เรียงแล้ว



*เครดิต [Only admins are allowed to see this link]


ขั้นตอนวิธี Quick sort
Quick sort ใช้หลักการ divide-and-conquer เหมือนกับ merge sort แต่แทนที่จะใช้ การรวมกันของข้อมูลที่เรียงแล้ว Quick sort ใช้วิธีการสลับที่ของสมาชิกใน array โดยที่สมาชิกในส่วนหน้าต้องน้อยกว่า หรือเท่ากับสมาชิกในส่วนหลัง A[p...q] <= A[q+1...r]
ข้อมูลเข้า A[1..n], p, r
ข้อมูลออก การจัดเรียงของข้อมูลใน A โดยที่ A[p] A[p+1] A[p+2] . . . A[r] (sorted in place)
QUICK-SORT(A, p, r)
1. if p < r
2. then q = PARTITION(A, p, r)
3. QUICK-SORT(A, p, q)
4. QUICK-SORT(A, q+1, r)
5. endif
PARTITION(A, p, r)
1. (x, i, j) = (A[p], p-1, r+1)
2. while TRUE
3. do repeat j = j-1
4. until A[j] <= x
5. do repeat i = i+1
6. until A[i] >= x
7. if i < j
8. (A[i], A[j]) = (A[j], A[i])
9. else
10. return j
11. endif
12. endwhile

*เครดิต [Only admins are allowed to see this link]

#include <stdio.h>
#define cutoff 3
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
int median(int a[],int left,int right)
{
int center=(left+right)/2;
if(a[left]>a[center])
swap(&a[left],&a[center]);
if(a[left]>a[right])
swap(&a[left],&a[right]);
if(a[right]<a[center])
swap(&a[right],&a[center]);
swap(&a[center],&a[right-1]);
return a[right-1];
}
void insertionsort(int A[],int n)
{
int j,p,temp;
for(p=1;p<n;p++)
{
temp=A[p];
for(j=p;j>0&&A[j-1]>temp;j--)
A[j]=A[j-1];
A[j]=temp;
}
}
void qsort(int a[],int left,int right)
{
int i,j,pivot;
if(left+cutoff<=right)
{
pivot=median(a,left,right);
i=left;
j=right-1;
while(1)
{
while(a[++i]<pivot){}
while(a[--j]>pivot){}
if(i<j)
swap(&a[i],&a[j]);
else
break;
}
swap(&a[i],&a[right-1]);
qsort(a,left,i-1);
qsort(a,i+1,right);
}
else
insertionsort(a+left,right-left+1);
}
void quicksort(int a[],int n)
{
qsort(a,0,n-1);
}
int main()
{
int i,n,*a;
printf("\nThe scope of the data.\n -> Enter the number of rows : ");
scanf("%d",&n);
a=(int*)(n*2);
printf("\n Enter the number \n ");
for(i=1;i<=n;i++)
{
scanf("%d",a+i);printf(" ");
}
insersort(&a[0],n);
printf("\n\n Row in sorted order is:\n ");
for(i=1;i<=n;i++)
{
printf("%d",*(a+i));printf(" \n ");
}
getch();
quicksort(a,10);
int i;
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
getchar();
}