Binary Insertion Sort
ยังมี algorithm อีกตัวหนึ่งที่นาเอาเทคนิควิธีของ binary search และ insertion sort มาประยุกต์ใช้ร่วมกันจึงมีชื่อเรียกว่า Binary Insertion Sort ซึ่งมีหลักการทางานคร่าว ๆ ดังนี้
เริ่มด้วยการทางานกับข้อมูล 2 ตัว ทากระบวนการที่คล้ายกันกับการทางานของ binary search เพื่อหาตาแหน่งที่เหมาะสมของข้อมูล (แบ่งข้อมูลออกเป็นสองส่วน – สลับตาแหน่งถ้าเข้าข่ายของเงื่อนไข) หลังจากนั้นเพิ่มข้อมูลอีกหนึ่งตัวเข้าสู่กระบวนการ (รวมเป็นสามตัว) ทากระบวนการของ binary search กับข้อมูลทั้งสามอีก ซึ่งจะทาให้ข้อมูลทั้งสามตัวถูกจัดวางในตาแหน่งที่เหมาะสม ทากับข้อมูลที่เหลืออยู่โดยเพิ่มทีละหนึ่งตัว จนกว่าข้อมูลจะหมด เราก็จะได้ข้อมูลที่มีการจัดเรียง เช่น ตัวอย่างที่แสดงนี้
Algorithms Binary Sort
public static <T extends Comparable<? super T>>
void binaryInsertionSort(T[] arr) {
int lower, upper;
int mid;
for(int i = 1; i < arr.length; i++) {
lower = 0;
upper = i;
while(lower < upper) {
mid = (lower + upper) / 2;
if(arr[i].compareTo(arr[mid]) > 0)
lower = mid+1;
else
upper = mid;
}
for(int j = i; j > lower; j--)
swap(arr, j-1, j);
}
}
ไม่มีความคิดเห็น:
แสดงความคิดเห็น