Basic Sorting Algorithm

วันนี้มาคุยกันเรื่อง sorting algorithm เบื้องต้นกันดีกว่าครับ โดยพื้นฐานแล้ว programmer อย่างพวกเราควรจะเข้าใจและจำหลักการ sorting algorithm พื้นฐานต่างๆ รวมทั้ง Big Oh, best case, worst case ให้ได้ เพราะมีประโยชน์เป็นอย่างยิ่งในการเขียนโปรแกรมให้มีประสิทธิภาพ ตัวอย่าง basic sorting algorithms หลักๆ ก็มี

Sorting Best Average Worst Space Stable
Bubble Sort O(n^2) O(n^2) O(n^2)  O(1) O
Selection Sort O(n^2) O(n^2) O(n^2)  O(1)
Insertion Sort O(n) O(n^2) O(n^2)  O(1) O
Merge Sort O(n log n) O(n log n) O(n log n)  O(n) O
Quick Sort O(n log n) O(n log n) O(n^2)  O(log n)
Heap Sort O(n log n) O(n log n) O(n log n) O(n)

Note: หากอยากรู้รายละเอียดเพิ่มเติมของแต่อัน ให้คลิกลิงค์ในตารางเข้าไปเนื้อหาของแต่ละ sorting algorithm นะครับ

วิเคราะห์โดยภาพรวม(ให้จำได้ง่าย)

  1. Quick Sort เป็น sorting algorithm ที่ทุกคนเลือกใช้มากที่สุดในกลุ่มนี้ เนื่องจากในทาง practical แล้ว Quick Sort เป็น algorithm ที่เร็วที่สุดใน sorting algorithm ระดับ O(n log n) ด้วยกันเอง แต่ต้องจำไว้ว่า ไม่ได้เป็น Stable Sort และ ในกรณีที่มี ค่าเหมือนๆกันเยอะๆ จะช้า
  2. Merge Sort จะถูกเลือกใช้แทน Quick Sort ในกรณีที่ 1.) ต้องการ Stable Sort  2.) เมื่อจะใช้ linked list 3.) random operation ในการ access element ที่ Quick Sort ทำค่อนข้าง expensive แต่ต้องจำไว้ว่า Merge sort ค่อนข้างจะกินเนื้อที่ เนื่องจากใช้ในการ sort ตอน merge
  3. Insertion Sort จะถูกเลือกใช้ใน 1.) nearly sorted data เพราะมีคุณสมบัติ adaptive เร็วขึ้นถ้า data เรียงไว้อยู่แล้วจำนวนหนึ่งๆ 2.) problem size ขนาดเล็กๆ เพราะ implement ง่าย และมี overhead ต่ำ ไม่ต้องเสีย memory เพิ่มเติม
  4. Selection Sort ถือเป็นตัวเลือกท้าย จะถูกเลือกใช้ในกรณีที่ swap operation ค่อนข้างแพง เพราะ Selection Sort มี การ swap ต่ำ แค่ n ครั้ง
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s