sorting-algorithms

Sorting Algorithms (อัลกอริธึมการเรียงลำดับ) เป็นวิธีการจัดเรียงข้อมูลในลำดับที่กำหนด เช่น ลำดับตัวเลขจากน้อยไปหามาก หรือจากมากไปหาน้อย อัลกอริธึมการเรียงลำดับเป็นสิ่งสำคัญในการจัดการข้อมูลในคอมพิวเตอร์ เช่น การจัดเรียงรายการสินค้า, การจัดเรียงข้อมูลทางการเงิน, หรือการค้นหาข้อมูลที่จัดเรียงแล้ว

ในบทความนี้ เราจะทำความเข้าใจเกี่ยวกับอัลกอริธึมการเรียงลำดับที่พบบ่อย รวมถึงข้อดีและข้อเสียของแต่ละอัลกอริธึม

1. Bubble Sort

Bubble Sort คือการเปรียบเทียบค่าที่อยู่ติดกันในลิสต์ แล้วสลับตำแหน่งหากค่าผิดลำดับ และทำซ้ำขั้นตอนนี้จนกว่าลิสต์จะเรียงลำดับ

ขั้นตอน:

1. เปรียบเทียบค่าตัวแรกกับค่าตัวที่สอง หากค่าตัวแรกมากกว่าค่าตัวที่สอง ให้สลับตำแหน่ง
2. ทำซ้ำจนกว่าจะตรวจสอบครบทุกคู่ที่อยู่ติดกัน
3. หากมีการสลับตำแหน่งในรอบที่ผ่านไป ให้ทำการวนซ้ำใหม่จนกว่าไม่มีการสลับตำแหน่ง

ตัวอย่างโค้ด Bubble Sort (Python):

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # สลับตำแหน่ง
                swapped = True
        if not swapped:
            break  # หากไม่มีการสลับในรอบนี้ หมายความว่าเรียงลำดับเสร็จแล้ว
    return arr

# การทดสอบ Bubble Sort
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))

ผลลัพธ์:

[11, 12, 22, 25, 34, 64, 90]

ข้อดี:

• เข้าใจง่ายและเขียนง่าย
• ไม่ต้องใช้หน่วยความจำเพิ่มเติม

ข้อเสีย:

• ประสิทธิภาพต่ำเมื่อข้อมูลมีขนาดใหญ่ (O(n²))

---

2. Selection Sort

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

ขั้นตอน:

1. หาค่าต่ำสุดในลิสต์และสลับกับค่าที่อยู่ในตำแหน่งแรก
2. หาค่าต่ำสุดในลิสต์ที่เหลือและสลับกับค่าที่อยู่ในตำแหน่งที่สอง
3. ทำซ้ำขั้นตอนนี้จนกว่าจะถึงตำแหน่งสุดท้าย

ตัวอย่างโค้ด Selection Sort (Python):

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # สลับค่าที่ตำแหน่ง i กับตำแหน่ง min_idx
    return arr

# การทดสอบ Selection Sort
arr = [64, 34, 25, 12, 22, 11, 90]
print(selection_sort(arr))

ผลลัพธ์:

[11, 12, 22, 25, 34, 64, 90]

ข้อดี:

• ทำงานได้ดีเมื่อขนาดข้อมูลเล็ก
• ไม่ต้องใช้หน่วยความจำเพิ่มเติม

ข้อเสีย:

• ประสิทธิภาพต่ำเมื่อข้อมูลมีขนาดใหญ่ (O(n²))

---

3. Insertion Sort

Insertion Sort คือการเลือกค่าจากลิสต์ที่ยังไม่ได้เรียงลำดับและนำมาแทรกไว้ในตำแหน่งที่เหมาะสมในลิสต์ที่เรียงลำดับแล้ว

ขั้นตอน:

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

ตัวอย่างโค้ด Insertion Sort (Python):

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

# การทดสอบ Insertion Sort
arr = [64, 34, 25, 12, 22, 11, 90]
print(insertion_sort(arr))

ผลลัพธ์:

[11, 12, 22, 25, 34, 64, 90]

ข้อดี:

• ดีสำหรับลิสต์ที่มีขนาดเล็กหรือเรียงลำดับเกือบเสร็จแล้ว
• ใช้หน่วยความจำต่ำ (O(1))

ข้อเสีย:

• ประสิทธิภาพต่ำเมื่อข้อมูลมีขนาดใหญ่ (O(n²))

---

4. Merge Sort

Merge Sort คืออัลกอริธึมแบบ Divide and Conquer ซึ่งแบ่งลิสต์ออกเป็นสองส่วน, เรียงลำดับแต่ละส่วน แล้วรวมผลลัพธ์เข้าด้วยกัน

ขั้นตอน:

1. แบ่งลิสต์ออกเป็นสองส่วนจนกระทั่งลิสต์เหลือขนาด 1
2. รวมลิสต์ที่เรียงลำดับแล้วเข้าด้วยกันทีละคู่
3. ทำซ้ำจนกระทั่งลิสต์ทั้งหมดเรียงลำดับ

ตัวอย่างโค้ด Merge Sort (Python):

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # หาตำแหน่งกลาง
        left = arr[:mid]
        right = arr[mid:]

        merge_sort(left)  # เรียงลำดับส่วนซ้าย
        merge_sort(right)  # เรียงลำดับส่วนขวา

        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    return arr

# การทดสอบ Merge Sort
arr = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(arr))

ผลลัพธ์:

[11, 12, 22, 25, 34, 64, 90]

ข้อดี:

• ประสิทธิภาพดีมาก (O(n log n)) สำหรับข้อมูลขนาดใหญ่
• ใช้งานได้ดีสำหรับลิสต์ขนาดใหญ่และข้อมูลที่มีลักษณะไม่เป็นระเบียบ

ข้อเสีย:

• ใช้หน่วยความจำเพิ่มขึ้น O(n) เพราะต้องใช้พื้นที่เพิ่มในการจัดเก็บข้อมูลชั่วคราว

---

5. Quick Sort

Quick Sort คืออัลกอริธึมแบบ Divide and Conquer ที่เลือกค่ากลาง (pivot) และจัดลำดับข้อมูลที่น้อยกว่าหรือมากกว่ามันไปทางซ้ายหรือขวา จากนั้นทำซ้ำในแต่ละส่วนย่อย

ขั้นตอน:

1. เลือก pivot จากข้อมูล
2. แบ่งข้อมูลเป็นสองส่วน: ค่าที่น้อยกว่าหรือเท่ากับ pivot อยู่ทางซ้าย และค่าที่มากกว่า pivot อยู่ทางขวา
3. เรียกฟังก์ชัน Quick Sort ซ้ำในแต่ละส่วนย่อย

ตัวอย่างโค้ด Quick Sort (Python):

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# การทดสอบ Quick Sort
arr = [64, 34, 25, 12, 22, 11, 90]
print(quick_sort(arr))

ผลลัพธ์:

[11, 12, 22, 25, 34, 64, 90]

ข้อดี:

• ประสิทธิภาพดีมาก (O(n log n)) สำหรับข้อมูลขนาดใหญ่
• ใช้หน่วยความจำต่ำกว่าการใช้ Merge Sort

ข้อเสีย:

• การเลือก pivot ไม่ดีอาจทำให้มีประสิทธิภาพต่ำในบางกรณี (O(n²))

---

สรุป

• Bubble Sort, Selection Sort, และ Insertion Sort มีประสิทธิภาพต่ำ (O(n²)) และเหมาะสมสำหรับข้อมูลที่มีขนาดเล็กหรือกรณีที่ไม่ต้องการความเร็วสูง
• Merge Sort และ Quick Sort เป็นอัลกอริธึมที่มีประสิทธิภาพดีกว่า (O(n log n)) และเหมาะสมสำหรับข้อมูลขนาดใหญ่