ทำความรู้จักกับ Insertion Sort ในภาษา Scala

การจัดเรียงข้อมูลเป็นหัวข้อสำคัญในโลกของการเขียนโปรแกรม โดยเฉพาะในด้าน Algorithm การจัดเรียง (Sorting Algorithms) ที่ช่วยให้เราสามารถจัดระเบียบข้อมูลในวิธีที่มีประสิทธิภาพ และหนึ่งใน Algorithm ที่น่าสนใจคือ Insertion Sort ซึ่งมีลักษณะการทำงานที่เข้าใจง่าย ทว่าเหมาะสำหรับการใช้งานในสภาพแวดล้อมบางประเภท ในบทความนี้ เราจะพูดถึง Insertion Sort ว่าคืออะไร มีการทำงานอย่างไร พร้อมกับตัวอย่าง code ในภาษา Scala และบริบทการใช้งานจริง รวมถึงการวิเคราะห์ Complexity และข้อดีข้อเสียของ Algorithm นี้

Insertion Sort คืออะไร?

Insertion Sort เป็น Algorithm ที่ใช้ในการจัดเรียงข้อมูล โดยทำงานตามหลักการที่เราจัด "ไพ่" ในมือ โดยเริ่มจากการสร้างกลุ่มข้อมูลที่เรียงแล้วจากซ้ายไปขวา แล้วนำข้อมูลใหม่มาวางในตำแหน่งที่เหมาะสมในกลุ่มที่จัดเรียงแล้ว ข้อมูลที่วางใหม่จึงเรียงต่อไปเรื่อยๆ จนได้กลุ่มข้อมูลที่ถูกจัดเรียงอย่างสมบูรณ์

วิธีการทำงานของ Insertion Sort

1. เริ่มจากตำแหน่งแรกของข้อมูล ซึ่งถือว่าเรียงแล้ว

2. ดูข้อมูลตัวถัดไป และทำการเปรียบเทียบกับข้อมูลที่อยู่ในกลุ่มที่เรียงแล้ว

3. หากข้อมูลใหม่เล็กกว่าข้อมูลในกลุ่มที่เรียงแล้ว จะต้องเลื่อนข้อมูลในกลุ่มที่เรียงแล้วไปที่ตำแหน่งถัดไปเพื่อวางข้อมูลใหม่เข้าที่

4. ทำซ้ำขั้นตอนที่ 2 และ 3 จนกว่าข้อมูลทั้งหมดจะถูกจัดเรียง

ตัวอย่าง Code ในภาษา Scala

 object InsertionSort {
  def insertionSort(arr: Array[Int]): Array[Int] = {
    for (i <- 1 until arr.length) {
      val key = arr(i)
      var j = i - 1

      // เลื่อนข้อมูลที่อยู่ในกลุ่มที่เรียงแล้วไปข้างหน้าเพื่อหาตำแหน่งที่ถูกต้องของ key
      while (j >= 0 && arr(j) > key) {
        arr(j + 1) = arr(j)
        j -= 1
      }
      arr(j + 1) = key
    }
    arr
  }

  def main(args: Array[String]): Unit = {
    val arr = Array(5, 2, 4, 6, 1, 3)
    val sortedArr = insertionSort(arr)
    println(sortedArr.mkString(", "))
  }
}

ในตัวอย่าง code ข้างต้น เราสร้างฟังก์ชัน `insertionSort` ที่รับค่าเป็น Array ของจำนวนเต็ม (Int) และจะคืนค่าที่ถูกจัดเรียงแล้ว จากนั้นใช้ฟังก์ชันนี้ในฟังก์ชัน `main` เพื่อทดสอบการจัดเรียงตั้งแต่ค่าเริ่มต้น

Use Case ในโลกจริง

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

สำหรับธุรกิจขนาดเล็กที่มีการจัดเก็บรายละเอียดของลูกค้าหรือข้อมูลการขายแบบไม่ซับซ้อน Insertion Sort ก็เป็นหนึ่งในทางเลือกที่ดีในการจัดเรียงข้อมูลเพียงเล็กน้อย

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

Time Complexity

- ในกรณีที่ดีที่สุด (เมื่อข้อมูลถูกจัดเรียงแล้ว): O(n)

- ในกรณีเฉลี่ยและกรณีที่เลวร้ายที่สุด: O(n²)

Space Complexity

- O(1) เนื่องจาก Insertion Sort ทำงานในพื้นที่ที่คงที่ ไม่ต้องใช้พื้นที่เสริมเพิ่มเติม

ข้อดีและข้อเสียของ Insertion Sort

ข้อดี

1. ง่ายต่อการเข้าใจและนำไปปฏิบัติ

2. มีประสิทธิภาพสูงในกรณีที่มีข้อมูลขนาดเล็ก

3. เป็น Stable Sort หมายถึงไม่ส่งผลต่อการเรียงลำดับที่มีค่าเท่ากัน

4. ด้วยเวลาที่ส่งผ่านไปได้เรื่อยๆ จึงทำให้ทำงานได้เร็วถ้าข้อมูลส่วนใหญ่อยู่ในลำดับที่แทบเรียงแล้ว

ข้อเสีย

1. ไม่เหมาะสำหรับข้อมูลขนาดใหญ่ เนื่องจาก Time Complexity ของกรณีที่เลวร้าย (O(n²))

2. ค่อนข้างช้าเมื่อเปรียบเทียบกับ Algorithm ที่มีประสิทธิภาพมากกว่า เช่น Quick Sort หรือ Merge Sort

สรุป

Insertion Sort ถือเป็น Algorithm ที่มีความน่าสนใจ โดยเฉพาะเมื่อใช้ในกรณีที่ข้อมูลในระบบมีขนาดเล็กหรือมีการเปลี่ยนแปลงบ่อย ๆ ถึงแม้จะมีข้อจำกัดที่ทำให้ไม่เหมาะสำหรับข้อมูลขนาดใหญ่ แต่ความเรียบง่ายในการเข้าใจและใช้งาน ทำให้มันยังคงมีความสำคัญในหลายพื้นที่

หากคุณสนใจในเทคโนโลยีและต้องการเรียนรู้เกี่ยวกับการเขียนโปรแกรมและ Algorithm ต่างๆ ในเชิงลึก เราขอเชิญให้คุณมาสมัครเรียนที่ EPT (Expert-Programming-Tutor) ด้วยหลักสูตรที่หลากหลายและทรัพยากรการเรียนรู้เพียบพร้อม ที่จะช่วยเสริมสร้างทักษะด้านการเขียนโปรแกรมสำหรับคุณ!

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง