Quick Sort
วิธีการของการ sort ก็คือ แบ่งข้อมูลออกเป็นสองส่วน แล้วเรียกตัวเองขึ้นมา sort ข้อมูลสองส่วนนี้ Quick sort จะเลือกข้อมูลหนึ่งตัว (pivot) สาหรับใช้ในการแบ่งข้อมูล ถ้าข้อมูลตัวอื่นซึ่งเมื่อนามาเปรียบเทียบกับข้อมูลที่เลือกไว้นี้มีค่าน้อยกว่า เราก็เก็บข้อมูลนี้ไว้ใน sub-array ตัวหนึ่ง (left) แต่ถ้ามากกว่าเราก็เก็บไว้ใน sub-array อีกตัวหนึ่ง (right) แล้วก็ sort ข้อมูลเหล่านี้จนกว่าข้อมูลใน sub-array ทุกตัวอยู่ในตาแหน่งที่เหมาะสม ภาพที่ 5.13 แสดงขั้นตอนการจัดเรียงข้อมูลของ Quick sort ด้วย Algorithm นี้
ขั้นตอนการทางานของ quickSort
1. ถ้าจานวนของข้อมูลใน list เท่ากับ 0 หรือ 1 ยุติการทางาน (return)2. เลือก pivot จาก list
3. แบ่งข้อมูลออกเป็นสองส่วน โดยที่ส่วนแรกมีข้อมูลที่น้อยกว่า pivot และส่วนหลังมากกว่า pivot
4. ส่งผลลัพธ์ของ quickSort(list ส่วนแรก) ตามด้วย pivot ตามด้วย quickSort(list ส่วนหลัง) พร้อมกับเริ่มกระบวนการ (1 ถึง 4) ใหม่
การเลือก pivot ให้เหมาะสมกับการจัดเรียงด้วย Quick sort นั้นทาได้ไม่ง่ายนัก เพราะว่าข้อมูลที่จะมาเป็น pivot นั้นควรเป็นข้อมูลที่สามารถใช้ในการแยกแยะข้อมูลทั้งหมดได้ดี มีวิธีการหลากหลายวิธีที่สามารถนามาใช้ในการคัดเลือก pivot ที่เหมาะสม เช่น ให้ข้อมูลตาแหน่งแรกสุดเป็น pivot หรือตาแหน่งท้ายสุดเป็น pivot แต่ทั้งสองวิธีไม่ใช่วิธีที่เหมาะสม
วิธีทั้งสองใช้ได้ถ้าข้อมูลนั้นอยู่กระจัดกระจาย (random) แต่ถ้าข้อมูลมีการจัดเรียงบางส่วน (presorted) หรืออยู่ในรูปแบบของการจัดเรียงจากมากไปหาน้อย (reverse order) วิธีนี้ไม่เหมาะสมเพราะ pivot ที่ใช้อยู่ห่างจากข้อมูลที่เหมาะสมมากเกินไป (extreme)
ก่อนที่เราจะดูถึงวิธีที่เหมาะสมในการหา pivot เรามาดู code ของ quick sort ที่ใช้ข้อมูลในตาแหน่งแรกเป็น pivot
Algorithms Quick Sort
public static <T extends Comparable<? super T>>void quickNM(T[] arr) {
quickNM(arr, 0, arr.length-1);
}
//recursive quick sort
private static <T extends Comparable<? super T>>
void quickNM(T[] arr, int start, int end) {
//cannot sort if end is less or equal to start
if(end <= start)
return;
T pivot = arr[start]; //pivot
int i = start; //starting index
int j = end + 1; //ending index
while(true) {
//searching for data that is less than pivot
while(i < end && arr[++i].compareTo(pivot) < 0) {}
//searching for data that is greater than pivot
while(j > start && arr[--j].compareTo(pivot) > 0) {}
//exchange data at i and j only if i < j
if(i < j)
swap(arr, i, j);
else
break;
}
//restore pivot
arr[start] = arr[j];
arr[j] = pivot;
quickNM(arr, start, j - 1);//sort left side
quickNM(arr, j + 1, end); //sort right side
}
ไม่มีความคิดเห็น:
แสดงความคิดเห็น