Bucket Sort

Bucket Sort

     สมมติว่าเรารู้ว่าขนาดของ array ที่เราต้องจัดเรียงข้อมูลมีขนาดเล็ก และแน่นอน เราอาจเลือกใช้การจัดเรียงแบบกระจาย (distribution sort) มาทาการจัดเรียงข้อมูลให้เรา และ Bucket sort ก็เป็นเทคนิควิธีอีกแบบหนึ่งที่ใช้การกระจายของข้อมูลมาเป็นตัวช่วยในการจัดเรียง ลองดูภาพตัวอย่างของข้อมูลที่มีอยู่ใน array ตัวอย่างนี้

     เรากาหนดให้ array ตัวอย่างมีข้อมูลอยู่ระหว่าง 0 – 9 ดังนั้นเราต้องใช้ตัวนับ 10 ตัวในการนับจานวนครั้งของข้อมูลที่มีอยู่ใน array จากตัวอย่างข้อมูลที่เรากาหนดขึ้น เรามีตัวเลขที่ซ้ากันอยู่ 3 ตัวคือ 2, 4, และ 8 เพราะฉะนั้น counter ที่อยู่ ณ ตาแหน่งของตัวเลขดังกล่าวก็จะมีค่าเป็นจานวนครั้งของตัวเลขทั้งสามตัวที่ถูกเก็บอยู่ใน array ซึ่งก็คือ 2 หลังจากที่เรารู้ถึงความถี่ของข้อมูลใน array แล้วเราก็นาเอา index ของข้อมูลเหล่านี้ใส่กลับเข้าไปใน array

Algorithm Bucket Sort

public void sort(int[] array) {

   //each index of count represents number in array

   //each number in count represents occurrences of

   //numbers in array

   for(int i = 0; i < size; i++) {

   count[array[i]]++;

}

   //move each index where occurrences of numbers appear

   //from count back to array

   for(int i = 0, j = 0; i < size; i++) {

     while(count[i] > 0) {

       array[j++] = i;

         count[i]--;

      }

   }

}