Asymptotic

Asymptotic แต่ละชนิด จะได้ดังนี้ คือ

1. Big-Oh ()
    
   ผลลัพธ์ที่ได้คือ เซ็ตของฟังก์ชันที่มีค่าอัตราการเติบโตต่ำกว่าหรือเท่ากับ g(n)
   
   เช่น ถ้ากำหนดให้ 
   
   ดังนั้น เซ็ตของคำตอบก็คือ 
2. Little-Oh ()
    
   ผลลัพธ์ที่ได้จะเหมือนกับ Big-Oh แต่จะต่างกันนิดเดียวคือ ฟังก์ชัน f(n) ต้องมีอัตราการเติบโตต่ำกว่าฟังก์ชัน g(n)
   เช่น กำหนดให้ 
   ดังนั้น  จะไม่อยู่ในเซ็ตของคำตอบ เพราะมีอัตราการเติบโตเท่ากัน
3. Big-Omega ()
   
   
   ผลลัพธ์ที่ได้คือ เซ็ตของฟังก์ชันที่มีค่าอัตราการเติบโตสูงกว่าหรือเท่ากับ g(n)
4. Little-Omega()
   
   
   
   ผลลัพธ์ที่ได้คือ เซ็ตของฟังก์ชันที่มีค่าอัตราการเติบโตสูงกว่า g(n)
5. Theta()
   

Sorting 10 sort

1.Bubble Sort

การเรียงข้อมูลแบบ Bubble Sort จะทำโดยการเปรียบเทียบค่าข้อมูลที่อยู่ติดกันทีละคู่ไปเรื่อยๆ ในกรณีเรียง ลำดับข้อมูลจากน้อยไปมาก ถ้าค่าแรกมีค่ามากกว่าค่าสองก็จะทำการสลับที่กัน โดยวิธีการนี้ จะทำให้ ข้อมูลที่มีค่าน้อยกว่าลอยสูงขึ้นเรื่อยเหมือนฟองสบู่(bubble) ที่ลอยขึ้นที่สูง และข้อมูลที่น้อยที่สุดก็จะ อยู่ในต่ำแหน่งบนสุดของชุดข้อมูลจึงเรียกการเรียงลำดับวิธีนี้ว่า BUBBLE  SORT

สมมติว่าต้องการเรียงข้อมูลจากน้อยไปมาก จะทำการเปรียบเทียบข้อมูลทีละ 2 ตัว ถ้าข้อมูลตัวแรกมากกว่าจะทำการสลับค่ากับข้อมูลตัวที่ 2 และเปรียบเทียบข้อมูลอีก 2 ตัวถัดไปจนสุดอาร์เรย์ จากนั้นทำซ้ำแบบเดิมอีกตามจำนวนข้อมูลในอาร์เรย์-1 เช่น ถ้าข้อมูลในอาร์เรย์มีจำนวน 5 ช่อง ก็ต้องทำซ้ำเป็นจำนวน 4 ครั้ง เป็นต้น

กำหนดให้มีจำนวนเต็ม 5 จำนวน คือ 5 4 3 2 1

Bubble Sort ครั้งที่ 1

5 4 3 2 1 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า)

4 5 3 2 1 (เปรียบเทียบข้อมูลตัวที่ 2 กับตัวที่ 3 : ตัวที่ 2 มากกว่า ตัวที่ 3 --> สลับค่า)

4 3 5 2 1 (เปรียบเทียบข้อมูลตัวที่ 3 กับตัวที่ 4 : ตัวที่ 3 มากกว่า ตัวที่ 4 --> สลับค่า)

4 3 2 5 1 (เปรียบเทียบข้อมูลตัวที่ 4 กับตัวที่ 5 : ตัวที่ 4 มากกว่า ตัวที่ 5 --> สลับค่า)

4 3 2 1 5

Bubble Sort ครั้งที่ 2

4 3 2 1 5 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า)

3 4 2 1 5 (เปรียบเทียบข้อมูลตัวที่ 2 กับตัวที่ 3 : ตัวที่ 2 มากกว่า ตัวที่ 3 --> สลับค่า)

3 2 4 1 5 (เปรียบเทียบข้อมูลตัวที่ 3 กับตัวที่ 4 : ตัวที่ 3 มากกว่า ตัวที่ 4 --> สลับค่า)

3 2 1 4 5 (เปรียบเทียบข้อมูลตัวที่ 4 กับตัวที่ 5 : ตัวที่ 4 น้อยกว่า ตัวที่ 5 --> ไม่ต้องสลับค่า)

3 2 1 4 5

Bubble Sort ครั้งที่ 3

3 2 1 4 5 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า)

2 3 1 4 5 (เปรียบเทียบข้อมูลตัวที่ 2 กับตัวที่ 3 : ตัวที่ 2 มากกว่า ตัวที่ 3 --> สลับค่า)

2 1 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 3 กับตัวที่ 4 : ตัวที่ 3 น้อยกว่า ตัวที่ 4 --> ไม่ต้องสลับค่า)

2 1 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 4 กับตัวที่ 5 : ตัวที่ 4 น้อยกว่า ตัวที่ 5 --> ไม่ต้องสลับค่า)

2 1 3 4 5

Bubble Sort ครั้งที่ 4

2 1 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 1 กับตัวที่ 2 : ตัวที่ 1 มากกว่า ตัวที่ 2 --> สลับค่า)

1 2 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 2 กับตัวที่ 3 : ตัวที่ 2 มากกว่า ตัวที่ 3 --> ไม่ต้องสลับค่า)

1 2 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 3 กับตัวที่ 4 : ตัวที่ 3 น้อยกว่า ตัวที่ 4 --> ไม่ต้องสลับค่า)

1 2 3 4 5 (เปรียบเทียบข้อมูลตัวที่ 4 กับตัวที่ 5 : ตัวที่ 4 น้อยกว่า ตัวที่ 5 --> ไม่ต้องสลับค่า)

1 2 3 4 5

เมื่อทำครบ 4 ครั้ง เราก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมาก

ดู youtube การสลับตำแหน่งของข้อมูล แบบ Bubble Sort

งาน Bubble Sort M.5/7 - 2556 กลุ่มที่1 กลุ่มที่2

งาน Bubble Sort M.5/2 - 2557 กลุ่มที่1 กลุ่มที่2 กลุ่มที่3 กลุ่มที่4

งาน Bubble Sort M.5/4 - 2557 กลุ่มที่1 กลุ่มที่2 กลุ่มที่3 กลุ่มที่4 กลุ่มที่5 กลุ่มที่6

งาน Bubble Sort M.5/5 - 2557 กลุ่มที่1  กลุ่มที่2 กลุ่มที่3 กลุ่มที่4 กลุ่มที่5  กลุ่มที่6

งาน Bubble Sort M.5/6 - 2557 กลุ่มที่1 กลุ่มที่2 กลุ่มที่3 กลุ่มที่4 กลุ่มที่5

งาน Bubble Sort M.5/7 - 2557 กลุ่มที่1  กลุ่มที่2 กลุ่มที่3 กลุ่มที่4 กลุ่มที่5  กลุ่มที่6 กลุ่มที่7

ขอขอบคุณเพลงประกอบการทำงานกลุ่ม ทุกค่ายเพลง มา ณ โอกาศนี้.

การสลับค่าข้อมูลในอาร์เรย์

กำหนดให้มีอาร์เรย์เก็บจำนวนเต็มจำนวน 5 ช่อง

num = 5 4 3 2 1;

ถ้าหากต้องการสลับค่าข้อมูลตัวที่ 1 กับตัวที่ 2 โดยทั่วไปแล้วเรามักจะเขียนโค้ดว่า

num[0]=num[1];

num[1]=num[0];

แต่ถ้าหากเรามาพิจารณาดูแล้ว จะพบว่ามันผิด ดังนี้

5 4 3 2 1

num[0]=num[1];

4 4 3 2 1

num[1]=num[0];

4 4 3 2 1

เราจะพบว่า จำเป็นที่จะต้องมีตัวแปรหนึ่งตัว(ให้ชื่อว่า temp) ที่เก็บค่าข้อมูลตัวที่ 1 ไว้ชั่วคราว จากนั้นจึงค่อยสลับค่าดังนี้

5 4 3 2 1

temp=num[0];

temp=5

num[0]=num[1];

4 4 3 2 1

num[1]=temp;

4 5 3 2 1

เมื่อเราทราบวิธีการสลับค่าข้อมูล และวิธีการเรียงแบบ Bubble Sort แล้วเราก็สามารถนำมาประยุกต์ใช้สำหรับการจัดเรียงข้อมูลในอาร์เรย์ได้

int num[5]={5,4,3,2,1};

int i,j,temp;

for(i=0;i<4;i++){

for(j=0;j<4;j++){

if(num[j]>num[j+1]){

temp=num[j];

num[j]=num[j+1];

num[j+1]=temp;

}

}

}

2.Selection Sort

การเรียงลำดับแบบเลือก

การเรียงลำดับแบบเลือก (อังกฤษ: selection sort) เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่ายโดยใช้วิธีการเปรียบเทียบ ทำงานโดยการหาค่าเหมาะสมที่สุด (ค่ามากสุดหรือน้อยสุด) ที่อยู่ในรายการส่วนที่ยังไม่เรียงและนำค่าเหมาะที่สุดนั้นมาต่อท้ายของส่วนที่เรียงแล้ว ก็จะทำให้ส่วนที่เรียงแล้วมีขนาดใหญ่ขึ้นทีละหนึ่งในแต่ละรอบการทำงาน ทำเช่นนี้จนไม่มีส่วนที่ยังไม่เรียงก็เสร็จ แต่ด้วยประสิทธิภาพเมื่อเกิดกรณีทั่วไปที่ O(n²) ทำให้ไม่เหมาะที่จะใช้ในกรณีที่มีข้อมูลในรายการเป็นจำนวนมาก แต่ถ้าหากปรับปรุงการหาค่าเหมาะสมที่สุดในรายการด้วยแถวคอยลำดับความสำคัญที่ทำให้เกิดผลด้วยโครงสร้างข้อมูลแบบฮีปทวิภาคจะเรียกว่าการเรียงลำดับแบบฮีป ซึ่งมีประสิทธิภาพดีกว่าที่ O(n log n)

การวิเคราะห์

ประสิทธิภาพ

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

ตัวอย่างทีละขั้นตอน

การเรียงลำดับข้อมูลในรายการดังนี้ 64 25 12 22 11 ด้วยขั้นตอนวิธีแบบเลือก เริ่มต้นถือว่าทุกตัวในรายการยังไม่เรียง

ครั้งที่ 1 หาตัวที่มีค่าน้อยที่สุดในรายการส่วนที่ยังไม่เรียงนั่นคือ 11 สลับกับตัวแรกของข้อมูลที่ยังไม่เรียงนั่นคือ 64

(64 25 12 22 11)  (11 25 12 22 64)

ครั้งที่ 2 หาตัวที่มีค่าน้อยที่สุดนั่นคือ 12 สลับกับตัวแรกนั่นคือ 25

(11 25 12 22 64)  (11 12 25 22 64)

ครั้งที่ 3 หาตัวที่มีค่าน้อยที่สุดนั่นคือ 22 สลับกับตัวแรกนั่นคือ 25

(11 12 25 22 64)  (11 12 22 25 64)

เรียงเสร็จเรียบร้อย

การนำมาใช้งาน

ตัวอย่างรหัสเทียม

begin selectionSort ( A คือ แถวลำดับที่จะถูกเรียง )

   for i = 0 to ขนาดของ(A) - 1

      ให้ตำแหน่งของค่าน้อยสุด คือ i

      for j = i+1 to ขนาดของ(A) - 1

if A[j] < A[ตำแหน่งของค่าน้อยสุด] then

    ให้ตำแหน่งของค่าน้อยสุด คือ j

end if

      end for

      สลับ A[i] กับ A[ตำแหน่งของค่าน้อยสุด]

   end for

end

3.Insertion Sort

การเรียงลำดับแบบแทรก (อังกฤษ: insertion sort) เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่าย ทำงานโดยจะแบ่งข้อมูลในรายการเป็นสองส่วนคือส่วนที่เรียงแล้วและส่วนที่ยังไม่เรียง แน่นอนว่าในตอนเร่มแรกส่วนที่เรียงแล้วก็จะมีอย่างน้อยหนึ่งตัว และจะเริ่มหยิบข้อมูลตัวหนึ่งของส่วนที่ยังไม่เรียงมาเปรียบเทียบเพื่อหาตำแหน่งที่เหมาะสมในการแทรกลงในข้อมูลส่วนที่เรียงแล้ว ลักษณะเดียวกับการเรียงไพ่ในมือ และด้วยประสิทธิภาพ O(n²) ดังนั้นการเรียงลำดับแบบแทรกจึงไม่เหมาะในการทำงานในรายการที่มีจำนวนสมาชิกมากๆ ซึ่งขั้นตอนวิธีการเรียงลำดับซึ่งซับซ้อนกว่าเช่น การเรียงลำดับแบบเร็ว, การเรียงลำดับแบบผสาน, การเรียงลำดับแบบฮีป มีความเหมาะสมมากกว่า

ขั้นตอนวิธี

ตัวอย่างทีละขั้นตอน

การเรียงลำดับข้อมูลในรายการดังนี้ 3 9 8 6 7 ด้วยขั้นตอนวิธีแบบแทรก เริ่มต้นด้วยข้อมูลทุกตัวยกเว้นตัวแรกยังไม่ได้เรียง ข้อมูลที่อยู่ในเครื่องหมาย (..) ถือว่าเป็นข้อมูลที่เรียงจากน้อยไปมากแล้ว

ครั้งที่ 1

[ (3) 9 8 7 6 ]  [ (3 9) 8 7 6 ]

ครั้งที่ 2

[ (3 9) 8 7 6 ]  [ (3 9 8) 7 6 ]

[ (3 9 8) 7 6 ]  [ (3 8 9) 7 6 ]

ครั้งที่ 3

[ (3 8 9) 7 6 ]  [ (3 8 9 7) 6 ]

[ (3 8 9 7) 6 ]  [ (3 8 7 9) 6 ]

[ (3 8 7 9) 6 ]  [ (3 7 8 9) 6 ]

ครั้งที่ 4

[ (3 7 8 9) 6 ]  [ (3 7 8 9 6) ]

[ (3 7 8 9 6) ]  [ (3 7 8 6 9) ]

[ (3 7 8 6 9) ]  [ (3 7 6 8 9) ]

[ (3 7 6 8 9) ]  [ (3 6 7 8 9) ]

เรียงเสร็จเรียบร้อย

ตัวอย่างรหัสเทียม

begin insertionSort ( A : list of sortable items )

   for i = 1 to length (A) - 1

      item = A[i]

      cmpPos = i - 1

      while cmpPos >= 0 and item < A[cmpPos]

         A[cmpPos + 1] = A[cmpPos]

         cmpPos = cmpPos - 1

      end while

      A[cmpPos + 1] = item

   end for

end

4.Binary Sort

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);

}

}

5.Quick Sort

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

}

6.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]--;

      }

   }

}

Shell Sort

Shell Sort

     Shell sort เป็นการพัฒนาวิธีการ sort จาก insertion sort ให้มีประสิทธิภาพในการ sort มากยิ่งขึ้น ด้วยการลดช่องว่างของการ sort ลง โดยแบ่งข้อมูลออกเป็นส่วน ๆ (segment) ในการ sort และทาการ sort ข้อมูลในแต่ละส่วน หลังจากนั้นก็ทาการแบ่งออกเป็นส่วน ๆ อีกโดยให้มีจานวนของ segment น้อยกว่าการแบ่งครั้งแรก ทากระบวนการดังกล่าวไปจนกว่าจานวนของ segment จะมีค่าเป็นหนึ่ง จึงยุติการ sort

หลังจากที่เราได้แบ่งข้อมูลออกเป็น 5 ส่วนดังที่เห็นในภาพ เราก็ทาการจัดเรียงข้อมูลในแต่ละส่วน

หลังจากการจัดเรียงข้อมูลเมื่อ segment เท่ากับ 5 ได้สิ้นสุดลงแล้ว เราจะทาการแบ่งข้อมูลออกเป็นส่วน ๆ อีก โดยคราวนี้เราจะแบ่งข้อมูลออกเป็น 3 ส่วน

เมื่อแบ่งข้อมูลได้แล้วเราก็ทาการจัดเรียงข้อมูลในแต่ละส่วน

และในที่สุดเราก็มาถึงขั้นตอนสุดท้ายคือ จานวนของ segment เหลือเพียงแค่ segment เดียว การจัดเรียงข้อมูลก็เกิดขึ้นภายใน segment นี้

7.Algorithms Shell Sort

public static <T extends Comparable<? super T>>

void shell (T[] arr) {

    int i, j;

    T temp;

    //calculate increment value K (# of segments)

    //based on Knuth's interval sequence

    int k = 1;

    while(k <= arr.length / 3)

       k = k * 3 + 1; //1, 4, 13, 40, 121, ...

    //sort array until # of segment is 1

    while(k > 0) {

          //sorting items in each segment simultanously

          for(i = k; i < arr.length; i++) {

              temp = arr[i];

              j = i;

              //one sub-pass; using j as index through items

             //in each segment

             while(j > k - 1 && arr[j-k].compareTo(temp) >= 0) {

                   arr[j] = arr[j - k];

                   j -= k;

             }

             arr[j] = temp;

        }

        k = (k - 1) / 3; //decreasing K value

    }

}

8.Merge Sort

Merge Sort

     Merge sort เป็นการ sort ข้อมูลด้วยการแบ่งข้อมูลออกเป็นสองส่วน แล้วจึง sort ข้อมูลในแต่ละส่วน หลังจากนั้นจึงนาเอาข้อมูลทั้งสองส่วนมารวมกันตามตาแหน่งที่เหมาะสมของข้อมูลแต่ละตัว (merge) ทาการแบ่งและ merge ไปจนกว่าข้อมูลอยู่ในตาแหน่งที่ถูกต้อง

     

     ในการจัดเรียงด้วย Merge sort นั้น เราดึงเอาวิธีการของ Recursion เข้ามาใช้ดังนั้นเราจึงเห็นในรูปถึงการแบ่งข้อมูลออกเป็นสองส่วน คือส่วนที่มี 64, 21, 33, และ 70 กับส่วนที่มี 12, 85, 44 และ 3 แต่เรายัง merge ข้อมูลของทั้งสองไม่ได้เราจึงต้องแบ่งข้อมูลในส่วนแรกออกเป็นสองส่วนอีก คือส่วนที่มี 64 และ 21 กับส่วนที่มี 33 และ 70 และเนื่องจากทั้งสองส่วนแบ่งไม่ได้อีกแล้ว เราจึงทาการจัดเรียงข้อมูลในแต่ละส่วน ซึ่งทาให้เราได้ข้อมูลเป็น 21 กับ 64 และ 33 กับ 70 หลังจากนั้นเราจึง merge ข้อมูลของทั้งสองส่วนเข้าด้วยกัน เราก็ได้ 21, 33, 64 และ 70 ซึ่งเป็นข้อมูลที่มีการจัดเรียงที่เหมาะสมแล้ว

     หลังจากนั้นเราก็ทาแบบเดียวกันกับส่วนที่หนึ่ง เราจะได้ข้อมูลของส่วนหลังเป็น 3, 12, 44, 85 และเราก็ merge ข้อมูลทั้งสองส่วนเข้าด้วยกันเราจะได้ข้อมูลที่ถูกจัดเรียงเป็น 3, 12, 21, 33, 44, 64, 70, 85

ขั้นตอนการทางานของ Merge sort มีดังนี้คือ

1. ถ้าจานวนข้อมูลเป็น 0 หรือ 1 ให้ยุติการทางานนั้น (return)

2. ทาการจัดเรียงข้อมูลในส่วนทั้งสองด้วยวิธีการของ Recursion

3. รวมข้อมูลที่ได้รับการจัดเรียงในส่วนทั้งสองเข้าด้วยกัน

Algorithms Merge Sort

private static Object makeArray(Object source) {

        int length = Array.getLength(source);

        Class aClass = source.getClass();

        Class component = aClass.getComponentType();

        Object result = Array.newInstance(component, length);

        return result;

}

//Top-down merge sort

public static <T extends Comparable<? super T>>

void mergeSort(T[] arr) {

        T[] temp = (T[])makeArray(arr); //compiler warning!

         mergeSort(arr, 0, arr.length-1, temp);

}

//recursive merging routines

private static <T extends Comparable<? super T>>

void mergeSort(T[] arr, int left, int right, T[] temp) {

        //exit recursive call

        if(right <= left)

             return;

        int mid = (left + right) / 2; //divide into halves

        mergeSort(arr, left, mid, temp); //merge first half

        mergeSort(arr, mid+1, right, temp); //merge second half

        merge(arr, left, mid, right, temp); //merging two sorted halves

}

//merging two sorted lists

private static <T extends Comparable<? super T>>

void merge(T[] arr, int left, int mid, int right, T[] temp) {

       int i, j;

       //move first array

       for(i = mid+1; i > left; i--)

            temp[i-1] = arr[i-1];

//move second array

       for(j = mid; j < right; j++)

             temp[right+mid-j] = arr[j+1];

//merge those two arrays

        for(int k = left; k <= right; k++)

             if(temp[j].compareTo(temp[i]) < 0)

                  arr[k] = temp[j--];

             else

                  arr[k] = temp[i++];

}

9.Radix Sort

Radix Sort

     Radix sort เป็นการจัดเรียงแบบกระจายอีกแบบหนึ่งที่ใช้เทคนิคของ Bucket sort มาประยุกต์เพื่อให้เกิดประสิทธิภาพในการจัดเรียงที่ดีกว่า ในการจัดเรียงแบบ Radix sort นี้เราจะใช้จานวนสูงสุดของตัวเลข (digit) ที่มีอยู่ใน int (สมมติว่าข้อมูลที่ต้องการจัดเรียงเป็น int) เป็นตัวกาหนดจานวนครั้งของการกระจาย เราจะจัดเรียง digit ทีละรอบโดยเริ่มต้นจาก digit ทางด้านขวาสุด (least significant digit) จนกระทั่งเราไม่มี digit ใด ๆ เหลืออยู่ในตัวเลขนั้น  แสดงขั้นตอนการจัดเรียงด้วยการใช้ Radix sort algorithm (ตัวเลขที่เป็นตัวหนาแสดงถึง radix ที่ใช้เป็นตัวกาหนดการจัดเรียง)

     ในการเขียน code รองรับการทางานของ Radix sort นั้น เราเลือกใช้ LinkedList เป็นตัวเก็บข้อมูลตาม radix (หรือตาแหน่งของ digit ในตัวเลข) ที่หาได้โดยเราจะเก็บจาก digit ที่อยู่ทางขวาสุดก่อนเป็นอันดับแรก และจะเลื่อนไปทางซ้ายจนกว่าจะหมดจานวนของ digit ที่มีอยู่ และก่อนที่เราจะไปดูกันถึง code ของ Radix sort เรามาดูคาสั่งในการหา radix ก่อน

//return radix of a numver e.g.

//first radix of 3476 is 6, second is 7 etc.

private int getRadix(int number, int radix) {

     return (int)(number / Math.pow(10, radix - 1)) % 10;

}

    การหา radix ก็ไม่ยาก เราเพียงแค่หารตัวเลขที่เราต้องการหา radix ด้วย 10 ยกกาลังตาแหน่งของ digit ที่เราต้องการหาลบหนึ่ง เช่น ถ้าเราต้องการหา radix ที่ 2 ของ 3476 เราก็หาร 3476 ด้วย 10(2-1) ได้ผลลัพธ์เท่าไร เราก็หาเศษจากผลลัพธ์นี้ด้วยการนาสิบไปหาร (mod) เพราะฉะนั้นเราก็จะได้ radix เป็น (3476 / 101) % 10 = 347 % 10 = 7 เราก็จะเก็บข้อมูลทุกตัวที่มี radix เท่ากับ 7 ไว้ใน array list[7]เมื่อเราได้ radix ที่ว่าแล้วเราก็ใช้ radix ตัวนี้เป็นตัวกาหนด (key) ในการจัดเรียงเหมือนกับที่เราทาใน Bucket sort ส่วนของ code ที่เห็นนี้มี list เป็น LinkedList ที่เราใช้เก็บข้อมูลตาม radix ที่เราได้มา โดยเราจะใช้การนาเข้าด้านหลังของ LinkedList เป็นหลัก

for(int j = 0; j < arr.length; j++) {

     list[getRadix(arr[j], i)].add(arr[j]);

}

     หลังจากที่เราได้ข้อมูลใน LinkedList ซึ่งเป็นข้อมูลที่ถูกจัดเก็บตามค่าของ radix เราก็จะดึงเอาข้อมูลเหล่านี้ออกจาก LinkedList ซึ่งการนาออกนั้น เราจะใช้การนาออกทางด้านหน้าเป็นหลัก (ผู้อ่านอาจสงสัยว่าทาไมเราไม่ใช้ Queue ในการจัดเก็บนี้ คาตอบก็คือ เราสามารถทาได้แต่ Java ก็มีวิธีการนาเข้าและดึงออกในรูปแบบที่คล้ายกันกับการทางานของ Queue จาก class LinkedList ดังนั้นเราจึงเรียกใช้ LinkedList ของ Java แทน Queue)

เราจะนาข้อมูลที่เราดึงออกมาจาก LinkedList กลับเข้าสู่ array ใหม่เพื่อการจัดเรียงในรอบต่อไป ดัง code ที่เห็นนี้

for(int j = 0; j < list.length; j++) {

     while(!list[j].isEmpty()) {

           arr[index] = (Integer)list[j].removeFirst();

                index++;

      }

}

ส่วนสาคัญอีกส่วนหนึ่งที่เราต้องทาก่อนการจัดเรียงก็คือ เราต้องหาจานวนของ digit ที่มีอยู่ในตัวเลขที่มีค่าสูงสุดในกลุ่มของตัวเลขที่เราต้องการจัดเรียง เพื่อเอาไว้ใช้เป็นตัวกาหนดรอบของการจัดเรียง ซึ่งก็มีวิธีการง่าย ๆ ดังนี้

int max = 0;

for(int i = 0; i < arr.length; i++) {

      max = Math.max(max, arr[i]);

}

int digits = (int)(Math.log10((double)max)) + 1;

ก่อนอื่นเราต้องหาค่าสูงสุดที่มีอยู่ในกลุ่มเสียก่อน ซึ่งเราก็ทาง่าย ๆ ใน for i/loop ที่เห็น และเมื่อเราได้ค่าสูงสุดแล้ว เราก็หาจานวนของ digit ที่มีอยู่ในค่าที่ว่านี้ด้วยคาสั่ง

int digits = (int)(Math.log10((double)max)) + 1;

อย่างไรก็ตาม ถ้าจะให้ได้จานวนของ digit ในตัวเลขที่ไม่ต้องมีการคานวณจากฟังก์ชั่นทางคณิตศาสตร์ เราก็สามารถทาได้ด้วยการใช้ loop หาจานวนที่ว่านี้แทน

10.Heap Sort

การเรียงลำดับข้อมูลแบบฮีป (Heap Sort)

     การเรียงข้อมูลแบบฮีป คือการจัดเรียงข้อมูลโดยอาศัยหลักการ หรือโครงสร้างของไบนารีทรี (Binary Tree) มาเป็นกระบวนการหลักในการทางาน ซึ่งวิธีการเรียงลาดับแบบไบนารีทรีนี้ เป็นวิธีที่ดีที่สุดของการเรียงลาดับข้อมูล ทั้งยังสามารถทางานได้ดีในข้อมูลที่มีความซับซ้อนมากๆ แม้ว่าค่าเฉลี่ยของการทางานอาจจะไม่ได้เร็วที่สุดก็ตาม (ในกรณีที่มีปัจจัยอื่น ๆ คงที่) แต่คุณสมบัติของฮีปก็ยังสามารถเรียงลาดับชุดข้อมูลที่มีขนาดใหญ่ และซับซ้อนได้ดีกว่าการเรียงข้อมูลแบบอื่นจากที่ได้กล่าวมาในข้างต้นถึงกระบวนการทางานของฮีป ซึ่งการอาศัยหลักการของไบนารีทรีในการดาเนินการนั้น หากจะนับว่าโครงสร้างดังกล่าวเป็นฮีปทรี (Heap Tree) ได้นั้นต้องอยู่ภายใต้เงื่อนไขดังต่อไปนี้

1. ในทุก ๆ ระดับของฮีปทรี นั้นจะสามารถแตกสาขาออกไปได้ทั้งซ้ายและขวา เริ่มจากการแตกสาขาออกไปทางซ้ายก่อนแล้วค่อยสลับไปทางขวา และจะต้องมีโหนดให้ครบทั้งสองด้านก่อน จึงจะสามารถแตกโหนดในระดับต่อไปได้

2. โหนดในระดับสูงกว่า หรือคีย์โหนดจะต้องอยู่ในลักษณะของโหนดตัวแม่ กล่าวคือจะต้องมีค่ามากกว่าโหนดลูกเสมอ

     อัลกอริทึมการเรียงลำดับข้อมูลแบบHeap Sortได้มีการนำวิธีการเรียงลำดับข้อมูลแบบSelection  Sort มาปรับปรุงให้มีประสิทธิภาพดียิ่งขึ้นโดยHeap  Sort จะเริ่มต้นทำงานจากอาร์เรย์ที่มีการจัดเรียงลำดับข้อมูลแบบฮีพ  ซึ่งคุณสมบัติสำคัญของฮีพทรีก็คือ รูทโหนดจะมีค่ามากที่สุด  และในการแทนฮีพทรีในอาร์เรย์  ค่าที่มากที่สุดจะอยู่ที่ตำแหน่งแรกดังนั้นเราจะนำค่าที่มากที่สุดในตำแหน่งแรกสลับกับค่าสุดท้ายของฮีพและถือว่าโหนดสุดท้ายนี้ได้หลุดออกจากฮีพทรีแล้ว จากนั้นสมาชิกหรือข้อมูลส่วนที่เหลือก็จะมีการรีฮีพโครงสร้างใหม่ ซึ่งค่าที่มากที่สุดก็จะอยู่ที่ตำแหน่งแรกเช่นเดิมและจะดำเนินการเช่นนี้ไปจนกระทั่งได้จัดการกับข้อมูลทั้งหมดในฮีพก็จะได้ข้อมูลที่จัดเรียงเรียบร้อยอย่างสมบูรณ์พิจารณาจากรูปที่ซึ่งแสดงขั้นตอนการเรียงลำดับข้อมูลแบบ Heap Sort  จะเห็นได้ว่าในรอบแรกค่าที่มากที่สุดคือ  78  ซึ่งอยู่บนท็อปของฮีพ  หรืออยู่ในตำแหน่งแรกของอาร์เรย์  โดยเราจะทำการเปลี่ยนตำแหน่งนี้กับสมาชิกสุดท้ายที่อยู่ในฮีพซึ่งค่ามากที่สุดที่ย้ายมาท้ายลิสต์นี้จะเป็นส่วนที่จัดเรียงแล้ว จากนั้นก็จะนำสมาชิกส่วนที่เหลือมาจัดโครงสร้างฮีพทรี  เพื่อให้โหนดที่มีค่าสูงสุดอยู่ตำแหน่งแรก และจะดำเนินการเช่นนี้ไปจนกระทั่งหมดข้อมูลในฮีพทรี

var a = [4, 1, 3, 5, 2, 6]; 

console.log(a);

heapSort(a);

console.log(a);

function swap(a, i, j) {

    var tmp = a[i];

    a[i] = a[j];

    a[j] = tmp;

}

function max_heapify(a, i, length) {

    while (true) {

        var left = i*2 + 1;

        var right = i*2 + 2;

        var largest = i;

        if (left < length && a[left] > a[largest]) {

            largest = left;

        }

        if (right < length && a[right] > a[largest]) {

            largest = right;

        }

        if (i == largest) {

            break;

        }

        swap(a, i, largest);

        i = largest;

    }

}

function heapify(a, length) {

    for (var i = Math.floor(length/2); i >= 0; i--) {

        max_heapify(a, i, length);

    }

}

function heapSort(a) {

    heapify(a, a.length);

    for (var i = a.length - 1; i > 0; i--) {

        swap(a, i, 0);

        max_heapify(a, 0, i-1);

    }

}

</script>