บทความ IT เจ๋งๆ

ทักษะเรื่องการ Sorting (เรียงลำดับ) ถือเป็นทักษะหนึ่งที่ Software engineer และ Developer ทุกคนควรรู้ เพราะไม่เพียงใช้ในการสัมภาษณ์งานเท่านั้น แต่ถือเป็นพี้นฐานในการเขียน Program อีกด้วย สำหรับใครที่ใช้ Python เรามาดู ตัวอย่าง Python Code ของการ Sorting 5 รูปแบบ กัน

1. Bubble Sort

Bubble sort เป็นสิ่งที่มักสอนกันใน Class เรียนของ Computer Science มันแสดงให้เห็นอย่างชัดเจนว่า การ Sort นั้นทำงานอย่างไร ซึ่งเป็นสิ่งที่เข้าใจได้อย่างไม่ยาก Bubble sort จะทำการเปรียบเทียบ elements ที่อยู่ติดกันใน list ซึ่ง elements เหล่านั้นก็จะถูกสลับที่กันทีละคู่ไปเรื่อยๆ หากมันยังเรียงลำดับผิดอยู่และจะทำไปจนครบทุกค่า จากนั้นก็จะกลับมาทำซ้ำใหม่ จนทุก elements อยู่ในตำแหน่งที่เรียงลำดับถูกต้อง และเนื่องจากการ Sort ประเภทนี้จะถูกทำซ้ำๆ ดังนั้น จำนวนครั้งในการ Sort กรณีที่เป็น Worst case คือ O(n2)

2. Selection Sort

Selection sort เป็นวิธีที่ง่าย แต่บ่อยครั้งก็มีประสิทธิภาพค่อนข้างมากกว่า Bubble sort หากต้องเลือกระหว่าง 2 วิธีนี้ Selection sort ดูจะเป็นวิธีที่ดีกว่า สำหรับ Selection sort จะมีการแบ่ง list/array ออกเป็น 2 ส่วน คือ sublist ของ items ที่ถูก Sort แล้ว(Sorted list) และ sublist ของ items ที่เหลือ (Unsorted list) ซึ่งจะทำการ Sort ไปเรื่อยๆ ใน sublist นี้ โดยในขั้นแรกจะทำการหาค่าที่น้อยที่สุดใน Unsorted list และสลับค่าแรกกับค่าที่น้อยที่สุดนั้น ซึ่งค่าที่น้อยที่สุดนั้นจะอยู่ใน Sorted list แล้ว จากนั้นทำแบบเดิมกับ items ใน Unsorted list แล้วนำค่าน้อยที่สุดไปใส่ด้านหลังสุดของ Sorted list ซึ่งจะทำแบบนี้ไปเรื่อยๆ จนมันเรียงลำดับอย่างถูกต้อง

3. Insertion Sort

Insertion sort ถือเป็นวิธีที่ทั้ง เร็วกว่าและ(มีเหตุผลอ้างอิงว่า)ง่ายกว่า Bubble sort และ Selection sort หากใครนึกไม่ออก ก็ลองนึกถึงตอนที่คุณเรียงลำดับไพ่ที่อยู่ในมือตอนที่คุณกำลังเล่นไพ่นั่นแหละ โดย Insertion sort จะทำการ remove 1 element ออกจาก array จากนั้นก็นำไปแทรกลงในตำแหน่งที่เหมาะสมใน array ที่ทำการ Sort แล้ว และจะทำแบบนี้ไปเรื่อยๆ จนกว่าจะเรียงลำดับถูกต้อง

4. Merge Sort

Merge sort เป็นตัวอย่างที่ดีของ Divide and Conquer algorithm โดยมีการทำ 2 ขั้นตอน ดังนี้:

1. ทำการแบ่ง list ที่ยังไม่ได้ถูกเรียงลำดับ (Unsorted list) จนกว่าจะได้ N sublists ซึ่งแต่ละ sublist จะมี 1 element ที่ยังไม่ได้ถูกเรียงลำดับ (Unsorted) และ N คือจำนวนของ element  ใน array เดิม
2. ทำการ Merge แต่ละ sublist เข้าด้วยกัน จนเกิดเป็น sublist ใหม่ที่มีการเรียงลำดับเรียบร้อยแล้ว ทำไปเรื่อยๆ จนกว่าทุก element ถูกเรียงลำดับอย่างถูกต้อง

5. Quick Sort

Quick sort ใช้หลักการ Divide and Conquer algorithm คล้ายๆ กับ Merge sort แม้ว่ามันจะมีความซับซ้อนกว่าเล็กน้อย แต่ในการใช้งานตามมาตรฐานส่วนใหญ่แล้ว จะทำงานได้รวดเร็วกว่า Merge sort และแทบจะไม่เคยใช้จำนวนครั้งในการเรียงถึงขั้น worst case ถึง O(n2) เลย โดยมี 3 ขั้นตอนหลักๆ ดังนี้:

1. ก่อนอื่นทำการเลือกค่ามา 1 element จาก array ซึ่งจะเรียกว่า pivot
2. ทำการย้าย element ที่มีค่าน้อยกว่า pivot ไปไว้ด้านซ้ายของ pivot และย้ายค่าที่มากกว่า pivot ไปไว้ด้านขวา ซึ่งขั้นตอนนี้จะเรียกว่า partition operation
3. ตอนนี้เราได้ 2 sublists ขึ้นมา จากนั้นก็ย้อนกลับไปทำขั้นตอนที่ 1 และ 2 ของในแต่ละ sublist ซ้ำๆ ไปเรื่อยๆ จนกว่าจะเรียงลำดับอย่างถูกต้อง

โดย Concept แล้ว การ Sort เหล่านี้ สามารถนำไปใช้ได้กับภาษาอื่นๆ ได้ แต่ในบทความนี้เป็นตัวอย่างการใช้ Code ของ Python หวังว่าจะเป็นประโยชน์กับ Programmer/Developer ที่จะต้องนำไปประยุกต์ใช้งานได้

ที่มา:  https://medium.com/