Algorithm พื้นฐาน

มารู้จักกับพื้นฐานแรกสุด

Merge Sort
Quick Sort

Merge Sort

Merge Sort คือขั้นตอนวิธีการเรียงลำดับข้อมูลโดยใช้หลักการ "แบ่งแยกและเอาชนะ" (Divide and Conquer) ซึ่งมีขั้นตอนดังนี้

แบ่ง array ออกเป็น 2 ส่วนที่มีขนาดเท่ากันหรือใกล้เคียงกันมากที่สุด (Divide)
เรียก function Merge Sort กับ array ย่อยทั้ง 2 ส่วนแยกกัน (Conquer)
- ถ้า array มีขนาดเล็กมาก เช่น มีข้อมูลแค่ 1 ตัว ก็ถือว่าเรียงลำดับเสร็จแล้ว ไม่ต้องแบ่งต่อ
- ถ้ายังแบ่งได้อีก ก็วนซ้ำเรียก Merge Sort กับ subarray ต่อไปเรื่อยๆ จนเหลือแค่ 1 ตัว
รวม subarray ที่เรียงลำดับแล้วทั้ง 2 ส่วนเข้าด้วยกัน (Merge) โดยนำข้อมูลที่น้อยกว่ามาก่อนทีละตัว จนครบทุกตัว
ได้ array ที่เรียงลำดับเสร็จสมบูรณ์

merge-sort

ref: https://en.wikipedia.org/wiki/Merge_sort

ความสัมพันธ์ระหว่าง Merge Sort กับ Divide and Conquer คือ Merge Sort เป็นตัวอย่างการประยุกต์ใช้ Divide and Conquer ในการเรียงลำดับข้อมูล โดยแบ่งปัญหาใหญ่ให้เล็กลง แก้ไขแยกกัน แล้วนำคำตอบย่อยมารวมกันเป็นคำตอบใหญ่

ตัวอย่าง code C++ ของ Merge Sort เป็นขั้นตอนดังนี้

#include <iostream>
using namespace std;

// functionสำหรับรวม subarray  2 ส่วนเข้าด้วยกัน
void merge(int arr[], int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;
  int L[n1], R[n2];

  for (int i = 0; i < n1; i++)
    L[i] = arr[left + i];
  for (int j = 0; j < n2; j++)
    R[j] = arr[mid + 1 + j];

  int i = 0, j = 0, k = left;
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}

// function Merge Sort หลัก
void mergeSort(int arr[], int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}

int main() {
  int arr[] = {12, 11, 13, 5, 6, 7};
  int n = sizeof(arr) / sizeof(arr[0]);

  mergeSort(arr, 0, n - 1);

  cout << "Sorted array: ";
  for (int i = 0; i < n; i++)
    cout << arr[i] << " ";
  return 0;
}

ผลลัพธ์

Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13

ขั้นตอนการทำงานของ code Merge Sort ในภาษา C++ มีดังนี้:

function mergeSort เป็น functionหลักที่เรียกตัวเองซ้ำ (recursive function) เพื่อแบ่ง array และเรียงลำดับ
- รับพารามิเตอร์ arr ( array ), left (ตำแหน่งซ้ายสุด), right (ตำแหน่งขวาสุด)
- ถ้า left < right แสดงว่ายังแบ่ง array ได้อีก ให้ทำต่อไปนี้:
  - หาตำแหน่งกลาง mid ของ array
  - เรียก mergeSort สำหรับครึ่งซ้ายของ array (left ถึง mid)
  - เรียก mergeSort สำหรับครึ่งขวาของ array (mid+1 ถึง right)
  - เรียก function merge เพื่อรวม subarray ที่เรียงลำดับแล้วทั้ง 2 ส่วนเข้าด้วยกัน
function mergeSort เป็น functionหลักที่เรียกตัวเองซ้ำ (recursive function) เพื่อแบ่ง array และเรียงลำดับ
- รับพารามิเตอร์ arr ( array ), left (ตำแหน่งซ้ายสุด), right (ตำแหน่งขวาสุด)
- ถ้า left < right แสดงว่ายังแบ่ง array ได้อีก ให้ทำต่อไปนี้:
  - หาตำแหน่งกลาง mid ของ array
  - เรียก mergeSort สำหรับครึ่งซ้ายของ array (left ถึง mid)
  - เรียก mergeSort สำหรับครึ่งขวาของ array (mid+1 ถึง right)
  - เรียก function merge เพื่อรวม subarray ที่เรียงลำดับแล้วทั้ง 2 ส่วนเข้าด้วยกัน
function main เป็นจุดเริ่มต้นของโปรแกรม
- ประกาศ array arr ที่ต้องการเรียงลำดับ
- หาขนาดของ array n
- เรียก function mergeSort โดยส่ง array ทั้งหมด (arr, 0, n-1)
- แสดงผล array ที่เรียงลำดับแล้ว สรุปคือ code Merge Sort จะเริ่มจาก function main ส่ง array ทั้งหมดไปให้ mergeSort เพื่อแบ่งครึ่งไปเรื่อยๆ จนเหลือ 1 ตัว จากนั้นจะเรียก function merge เพื่อรวม subarray ที่เรียงลำดับแล้วกลับขึ้นมาทีละคู่ จนในที่สุดได้ array ที่เรียงลำดับสมบูรณ์ การคำนวณความซับซ้อน (Big O) ของ code Merge Sort ในภาษา C++ มีขั้นตอนดังนี้
พิจารณา function mergeSort ซึ่งเป็น functionหลักที่เรียกตัวเองซ้ำ (recursive function)
- ในแต่ละครั้งที่เรียก mergeSort จะแบ่ง array ครึ่งซ้ายและครึ่งขวา โดยใช้เวลา O(1)
- จากนั้นเรียก mergeSort กับครึ่งซ้ายและครึ่งขวาแยกกัน ซึ่งเป็นการเรียกตัวเองซ้ำ (recursion)
- ดังนั้น mergeSort จะถูกเรียกทั้งหมด log n ครั้ง เพราะแบ่งครึ่งไปเรื่อยๆ จนเหลือ 1 ตัว
ในแต่ละครั้งที่เรียก mergeSort จะมีการเรียก function merge เพื่อรวม subarray เข้าด้วยกัน
- function merge จะวนลูปเพื่อเทียบค่าและรวมข้อมูลจาก subarray 2 ส่วน ใช้เวลา O(n)
- เนื่องจากมีการเรียก merge ทุกครั้งที่เรียก mergeSort ดังนั้นเวลาของ merge จะคูณกับจำนวนครั้งที่เรียก mergeSort
สรุป Big O ของ Merge Sort คือ
- ความซับซ้อนของ mergeSort: O(log n) เพราะแบ่งครึ่ง array ไปเรื่อยๆ log n ครั้ง
- ความซับซ้อนของ merge: O(n) เพราะต้องวนรวมข้อมูลของ subarray ขนาด n
- ดังนั้น Big O โดยรวมคือ O(n * log n) เพราะต้องรวม subarray n ตัว จำนวน log n ครั้ง ตัวอย่างการคำนวณ Big O สำหรับ array 8 ตัว

ครั้งที่ 1: แบ่งครึ่งเป็น 4 กับ 4 ใช้เวลารวม O(8)
ครั้งที่ 2: แบ่งครึ่งเป็น 2 กับ 2 สองครั้ง ใช้เวลารวม O(4) + O(4) = O(8)
ครั้งที่ 3: แบ่งครึ่งเป็น 1 กับ 1 สี่ครั้ง ใช้เวลารวม O(2) + O(2) + O(2) + O(2) = O(8)
รวมเวลาทั้งหมด: O(8) + O(8) + O(8) = O(8 * 3) = O(8 * log 8) = O(n * log n) สรุปคือ ความซับซ้อนของ Merge Sort คือ O(n * log n) ในทุกกรณี ไม่ว่า array จะเรียงลำดับมาก่อนแล้วหรือไม่ เพราะต้องแบ่งครึ่งและรวมข้อมูลเหมือนกันทุกครั้ง

Quick Sort

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

เลือกข้อมูลตัวหนึ่งมาเป็น Pivot
แบ่งข้อมูลออกเป็น 2 ส่วน โดยข้อมูลที่น้อยกว่าหรือเท่ากับ Pivot ให้ย้ายไปอยู่ทางซ้ายของ Pivot ส่วนข้อมูลที่มากกว่า Pivot ให้ย้ายไปอยู่ทางขวาของ Pivot
ทำซ้ำขั้นตอนที่ 1 และ 2 กับข้อมูลทางซ้ายและขวาของ Pivot จนกว่าข้อมูลจะเหลือน้อยกว่าหรือเท่ากับ 1 ตัว
รวมข้อมูลที่ผ่านการเรียงลำดับแล้วเข้าด้วยกัน

quicksort

ref: https://workat.tech/problem-solving/tutorial/sorting-algorithms-quick-sort-merge-sort-dsa-tutorials-6j3h98lk6j2w

ตัวอย่าง code C++ ของ Quick Sort

#include <iostream>
using namespace std;

// function Partition สำหรับแบ่งแยก array 
int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);

  for (int j = low; j <= high - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1], arr[high]);
  return (i + 1);
}

// function Quick Sort หลัก
void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

// functionสำหรับแสดง array 
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    cout << arr[i] << " ";
  cout << endl;
}

// function main สำหรับทดสอบการทำงาน
int main() {
  int arr[] = {64, 34, 25, 12, 22, 11, 90};
  int n = sizeof(arr) / sizeof(arr[0]);

  cout << "Original array: " << endl;
  printArray(arr, n);

  quickSort(arr, 0, n - 1);

  cout << "Sorted array: " << endl;
  printArray(arr, n);

  return 0;
}

ผลลัพธ์

Original array:
64 34 25 12 22 11 90
Sorted array:
11 12 22 25 34 64 90

อธิบาย code :

ประกาศ array arr ที่ต้องการเรียงลำดับ และหาขนาดของ array n
แสดง array เดิมก่อนเรียงลำดับด้วยfunction printArray
เรียกใช้function quickSort เพื่อเรียงลำดับ array โดยส่งพารามิเตอร์เป็น array arr, ตำแหน่งเริ่มต้น 0 และตำแหน่งสุดท้าย n-1
function quickSort จะเรียกใช้function partition เพื่อแบ่งแยก array ตาม pivot และเรียกตัวเองซ้ำกับ subarray ทางซ้ายและขวาของ pivot จนกว่าจะเรียงลำดับเสร็จ
แสดง array ที่เรียงลำดับแล้วอีกครั้งด้วยfunction printArray ขั้นตอนการคำนวณความซับซ้อน (Big O) ของ code Quick Sort ในภาษา C++ มีดังนี้:
พิจารณาfunction partition ซึ่งใช้ในการแบ่งแยก array ตาม pivot
พิจารณาfunction quickSort ซึ่งเป็นfunctionหลักที่เรียกตัวเองซ้ำ (recursive function)
สรุป Big O ของ Quick Sort คือ

ข้อสังเกต

ความซับซ้อนของ Quick Sort ขึ้นอยู่กับการเลือก pivot เป็นหลัก หากเลือกได้ดีจะได้ O(n log n) แต่ถ้าเลือกไม่ดีอาจเป็น O(n^2) ในกรณีเลวร้ายที่สุด
Quick Sort เป็น in-place sorting ไม่ต้องใช้ memory เพิ่ม แต่ใช้ recursion ลึกถึง log n ชั้น ซึ่งอาจทำให้ stack overflow ได้หากข้อมูลใหญ่มาก
Quick Sort มีค่าคงที่ (constant factor) ต่ำกว่า Merge Sort เพราะไม่ต้องคัดลอกและรวม subarray แต่ Merge Sort รับประกันได้ว่าจะได้ O(n log n) เสมอ สรุปคือ code นี้แสดงการใช้ Quick Sort เพื่อเรียงลำดับ array ตัวเลขจำนวนเต็ม โดยแสดง array ก่อนและหลังเรียงลำดับเพื่อให้เห็นผลลัพธ์ชัดเจน ซึ่งเป็นวิธีที่มีประสิทธิภาพสูงในการเรียงลำดับข้อมูลขนาดใหญ่ โจทย์ sort เพิ่มเติม https://leetcode.com/problems/sort-an-array/description/
ข้อนี้ชัดเจนว่าต้องใช้ Sort ที่เร็วกว่า O(n^2) เพราะขนาดข้อมูลใหญ่พอสมควร

ปัญหา Classic อื่นๆเพิ่มเติมของ Divide & Conquer

Karatsuba algorithm

Strassen’s Matrix Multiplication

Merge Sort​

Quick Sort​

ปัญหา Classic อื่นๆเพิ่มเติมของ Divide & Conquer​

Merge Sort

Quick Sort

ปัญหา Classic อื่นๆเพิ่มเติมของ Divide & Conquer