การเรียงลำดับด้วย Selection Sort ใช้ภาษา Scala

 

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

 

Selection Sort คืออะไร?

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

 

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

1. เริ่มต้นที่ค่าแรกของอาร์เรย์ เราจะถือค่าที่ต่ำที่สุดในอาร์เรย์นี้

2. วิเคราะห์ค่าที่เหลือในอาร์เรย์เพื่อหาค่าต่ำสุดในกลุ่มที่ยังไม่ได้เรียง

3. สลับค่าที่ต่ำที่สุดที่เจอเข้าไปในตำแหน่งแรกที่ยังไม่ได้เรียง

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

 

ตัวอย่างโค้ด Selection Sort ในภาษา Scala

มาดูโค้ดตัวอย่างการทำงานของอัลกอริธึม Selection Sort ในภาษา Scala กัน:

 object SelectionSort {
  def selectionSort(arr: Array[Int]): Array[Int] = {
    val n = arr.length
    for (i <- 0 until n-1) {
      // ค้นหาค่าต่ำสุดในอาร์เรย์ที่ยังไม่ได้เรียง
      var minIndex = i
      for (j <- i + 1 until n) {
        if (arr(j) < arr(minIndex)) {
          minIndex = j
        }
      }
      // สลับค่าถ้าจำเป็น
      if (minIndex != i) {
        val temp = arr(i)
        arr(i) = arr(minIndex)
        arr(minIndex) = temp
      }
    }
    arr
  }

  def main(args: Array[String]): Unit = {
    val arr = Array(64, 25, 12, 22, 11)
    println("Array ก่อนเรียงลำดับ: " + arr.mkString(", "))
    val sortedArr = selectionSort(arr)
    println("Array หลังเรียงลำดับ: " + sortedArr.mkString(", "))
  }
}

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

 

Use Case ในโลกจริง

Selection Sort อาจไม่เหมาะสำหรับการใช้งานกับข้อมูลขนาดใหญ่ แต่ก็ยังมี use case ที่สามารถใช้ได้ โดยหนึ่งในตัวอย่างที่ชัดเจนคือการเรียงลำดับของข้อมูลที่มีขนาดเล็ก เช่น การจัดเรียงคะแนนของนักเรียนในห้องเล็กๆ หรือการจัดเรียงรายการสินค้าในร้านค้าที่มีจำนวนสินค้าน้อย

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

 

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

1. Complexity:

- เวลา (Time Complexity): O(n^2) ซึ่งเป็นการประเมินความซับซ้อนในกรณีแย่ เมื่อ n เป็นจำนวนข้อมูลในอาร์เรย์

- หน่วยความจำ (Space Complexity): O(1) เนื่องจากไม่ต้องใช้หน่วยความจำเพิ่มเติมนอกเหนือจากการเปลี่ยนตำแหน่งค่า

2. ข้อดี:

- เรียบง่ายและเข้าใจง่าย เหมาะสำหรับการสอนและเริ่มต้นเรียนรู้การจัดเรียงข้อมูล

- ทำงานในสถานการณ์ที่ไม่ต้องการจำนวนมากของข้อมูล มีประสิทธิภาพเมื่อใช้งานกับอาร์เรย์ขนาดเล็ก

3. ข้อเสีย:

- มีความไม่เหมาะสมในกรณีที่ขนาดข้อมูลใหญ่ เนื่องจากเวลาในการทำงานจะหลายเท่าตัว (O(n^2))

- การทำงานมีลักษณะที่ไม่จำกัด (In-place) และไม่เสถียร อาจทำให้เกิดความไม่แน่นอนในการจัดเรียงเนื่องจากการเปลี่ยนตำแหน่ง

 

สรุป

Selection Sort เป็นอัลกอริธึมที่เรียบง่ายและใช้งานง่าย เหมาะสำหรับการจัดเรียงข้อมูลขนาดเล็ก แม้ว่ามันจะไม่มีประสิทธิภาพอยู่มากนักเมื่อเทียบกับอัลกอริธึมที่ทันสมัย เช่น Quick Sort หรือ Merge Sort หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมและพัฒนาอัลกอริธึมเช่นนี้ พบว่าการเรียนรู้ที่ EPT (Expert-Programming-Tutor) เป็นทางเลือกที่ดีที่สุดสำหรับคุณ!

มาร่วมกันพัฒนาทักษะการเขียนโปรแกรมของคุณที่ EPT และเรียนรู้เทคนิคการเรียงลำดับและอื่นๆ ที่จะทำให้คุณเป็นโปรแกรมเมอร์ที่มีความรู้และทักษะมากยิ่งขึ้น!

 

 

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