[CS for Non-Tech] Part 1 — Data Structures/Algorithms Zone [ไทย]

สวัสดีครับทุกคน มาต่อกันในส่วนของฝั่ง Software skill tree กัน สำหรับบทความนี้จะเน้นไปในเรื่อง Introduction, Big-O, Linear Data Structures และ Algorithms ที่เกี่ยวข้องกันครับ 😆

Part 1 - Data Structures/Algorithms Zone

Interpreter & Compiler

Interpreter เป็นโปรแกรมที่อ่านและรันโค้ดที่เขียนด้วย Programming Languages เมื่อเรียกใช้ Interpreter จะอ่านโค้ดและดำเนินการทีละบรรทัด Interpreter ส่วนมากอาจรันช้ากว่าโปรแกรมที่ compiled แล้ว ตัวอย่างเช่น Python และ Ruby

ในทางกลับกัน Compiler จะแปลงโค้ดที่เขียนด้วย Programming Languages ไปเป็น Machine Code ก่อน โดยอยู่ในรูปแบบของ Executable file (.exe) จากนั้น Machine Code ถูกประมวลผลโดยตรงโดย Processor ของคอมพิวเตอร์ ซึ่งมักจะเร็วกว่า Interpreter เช่น C, Go, Rust

และจะมีตัวที่ consider ว่าเป็น Compiler แต่ยืนอยู่ตรงกลาง process อย่าง Java ที่ใช้ bytecode for JVM และ C# ที่ใช้ CLR

Sequencing, Selection, Iteration (Structure theorem)

เป็นโครงสร้างการควบคุมในการเขียนโปรแกรมที่ให้สามารถระบุลำดับที่โค้ดจะถูกเรียกใช้ได้ Structure theorem เป็นผลลัพธ์ทางทฤษฎีที่บอกว่าทุกโปรแกรมสามารถเขียนได้โดยใช้โครงสร้างควบคุมทั้งสามนี้เท่านั้น

Sequencing รันตามลำดับที่เราจัดเรียง ตัวอย่างเช่น

int x = 1;
int y = 2;
int z = x + y;

Selection ควบคุมที่ให้ดำเนินการตามเงื่อนไขต่าง ๆ โดย base on condition true และ false

if (x > y) {
  // code to be executed if x is greater than y
} else {
  // code to be executed if x is not greater than y
}

Iteration การทำซ้ำเป็นโครงสร้างการควบคุมที่ให้คุณรันโค้ดชิ้นเดียวกันได้หลายครั้ง

for (int i = 0; i < 10; i++) {
  // code to be executed 10 times
}

Programming paradigm

เป็นรูปแบบหรือแนวทางการเขียนโปรแกรมที่ based on ตัว set of fundamental principles ต่าง ๆ Most commonly used จะเป็นด้านล่าง และ Programming languages ก็ implement แตกต่างกันออกไป

Procedural programming

เป็นกระบวนการเขียนโปรแกรมดั้งเดิม ที่มีพื้นฐานมาจากแนวคิดของการทำฟังก์ชันการทำงานเฉพาะ ดังนั้นโปรแกรมก็จะรันไหลจากบนลงล่างตามกระบวนการลำดับการทำงาน

ด้านล่างเป็นตัวอย่าง Factorial ด้วยภาษา C

#include <stdio.h>

int factorial(int n) {
  int result = 1;
  for (int i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

int main() {
  int n = 5;
  printf("The factorial of %d is %d\n", n, factorial(n));
  return 0;
}

Object-oriented programming

เป็นกระบวนการเขียนโปรแกรมที่มีพื้นฐานมาจากแนวคิดของการมองโค้ดให้เป็นเหมือนวัตถุรอบ ๆ และใช้ Object สื่อสารกัน

ด้านล่างเป็นตัวอย่าง Circle class ด้วยภาษา Kotlin ด้วยแนวคิดมอง วงกลม เป็นวัตถุ และภายในมี Method ใช้หาพื้นที่วงกลม

data class Circle(val radius: Double) {
  fun getArea(): Double {
    return Math.PI * radius * radius
  }
}

fun main(args: Array<String>) {
  val c = Circle(5.0)
  println("The area of the circle is ${c.getArea()}")
}

Functional programming

เป็นกระบวนการเขียนโปรแกรมที่มีพื้นฐานมาจากการมองการคำนวณเหมือนสูตรทางคณิตศาสตร์ มี topics ครอบอย่าง higher-order functions and immutable data

ด้านล่างเป็นตัวอย่าง Factorial ด้วยภาษา Kotlin แบบอ้างอิง Functional programming ด้วย Recursive

fun factorial(n: Int): Int {
  return if (n == 0) 1 else n * factorial(n - 1)
}

println("The factorial of 5 is " + factorial(5))

Big-O

Big-O Notation เป็นวิธีการอธิบายประสิทธิภาพหรือความซับซ้อนของอัลกอริทึม ใช้เพื่ออธิบายว่า เวลาทำงาน (Time Complexity) หรือการใช้พื้นที่ (Space Complexity) ของอัลกอริทึมเพิ่มขึ้นอย่างไรเมื่อขนาด Input นั้นเพิ่มขึ้น โดยส่วนใหญ่ที่เราใช้กัน จะใช้ตอนที่หา Worst case scenarios

หากสนใจเพิ่มเติม Big-O Cheat Sheet

Know Thy Complexities!

จะจบแค่นี้หรอ ยังก่อนครับ 55555 ผมยังมีตัวอย่างอีกเยอะ โดยผมอยากจะ Focus ทุกคนไปที่ตัว Time Complexity เป็นหลักนะครับ

A few rules about Big-O

• Dropping the constants โยนค่าคงที่ทิ้งไป

100n = n

10n^2 = n^2

n + 5 = n

• Sum or Multiply เราจะบวกหรือคูณลองพิจารณาดังนี้

level เดียวกัน -> + (Sum)
Nest operation in loop -> * (Multiply)

• Lower-order (non-dominant) terms are dropped อันไหนนัยสำคัญต่ำ/น้อยกว่าโยนทิ้งไป

int sum = 0;

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    sum++;
  }
}

for (int i = 0; i < n; i++) {
  sum++;
}

จากด้านบนเราจะได้ 1 + n² + n จัดดี ๆ เรียงตามเลขยกกำลังจะเป็น n² + n + 1 ดังนั้นโยนทิ้งเหลือแค่ n² คำตอบคือ O(n²)

• Different input means different variables ถ้า Input ต่างกัน ใช้ตัวแปรต่างกันแล้วนะ

int sum = 0;

for (int i = 0; i < m; i++) {
  for (int j = 0; j < n; j++) {
    sum++;
  }
}

จากด้านบน ไม่ใช่ n² แต่อย่างใด พยายามมีสติตอนสัมภาษณ์ 😂 ใช่แล้วครับ ด้านบน คำตอบคือ O(m * n)

Example case by case

• O(1): Constant time complexity

public class ConstantTime {

    public static void printData(int data) {
        System.out.println("data: " + data);
    }

    public static int accessData(int[] nums, int index) {
        if (index < 0) {
            throw new IllegalArgumentException("Index should not below than zero");
        }
        return nums[index];
    }
}

• O(log n): Logarithmic time complexity

public class LogNTime {

    public static int binarySearch(int[] array, int x) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (x < array[mid]) {
                right = mid - 1;
            } else if (x > array[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

}

• O(n): Linear time complexity

public class LinearTime {

    public static int sum(int n) {
        int result = 0;

        for (int i = 0; i < n; i++) {
            result += i;
        }

        return result;
    }
}

แล้วตัวนี้ล่ะ 2 อันไหนทำงานเร็วกว่ากัน findingMinMax1 หรือ findingMinMax2

public class LinearTime {


    public static List<Integer> findingMinMax1(int[] array) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            min = Integer.min(min, array[i]);
            max = Integer.max(max, array[i]);
        }
        return List.of(min, max);
    }

    public static List<Integer> findingMinMax2(int[] array) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            min = Integer.min(min, array[i]);
        }
        for (int i = 0; i < array.length; i++) {
            max = Integer.max(max, array[i]);
        }
        return List.of(min, max);
    }

}

โอ้ย findingMinMax1 อยู่แล้ว ก็ loop รอบเดียวนี้ ถูกมะ

Nooooo!!!!! ไม่ใช่แบบนั้นครับ อาจจะถูกแหละถ้ามองด้วยตา แต่เรามาลองตึงกันหน่อยครับ

Big O is not about counting the code statements. 

เป้าหมายคือเพื่อแสดงการเติบโตของ running time 
หรือ space usage ของ algorithm อันเนื่องมาจากการเติบโตของ input size

Big O -> describes the runtime rate of increase.

ดังนั้นตัวนี้เลยมี O(n) เท่ากันครับ

แล้วตัวนี้ล่ะ Big-O ได้เท่าไหร่

public class LinearTime {

    public static boolean hasDuplicateElement(List<Integer> a, List<Integer> b) {
        Set<Integer> set = new HashSet<>();
        for (int n : a) {
            set.add(n);
        }
        for (int n : b) {
            if (b.contains(n)) {
                return true;
            }
        }
        return false;
    }
}

ใช่ครับผม คำตอบคือ O(a + b)

และตัวนี้ผมขอเสริม Space Complexity นิดเดียว จะเห็นว่าผมเอา a ใส่เข้าไปไว้ที่ Set ทั้งหมด แปลว่า Space Complexity ตอนนี้คือ O(a) แต่ถ้าผมสลับเป็นโยน b เข้าไปก่อน จะกลายเป็น O(b) ซึ่ง Input คนละตัวกัน

• O(n log n): Log-linear time complexity => Quick Sort (Ctrl/Cmd + F)
• O(n^2): Quadratic time complexity => Bubble Sort (Ctrl/Cmd + F)
• O(n^3): Cubic time complexity

public class QubicTime {

    public int[][] matrixMultiply(int[][] A, int[][] B) {
        int m = A.length;
        int n = A[0].length;
        int k = B[0].length;

        int[][] C = new int[m][k];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                C[i][j] = 0;

                for (int p = 0; p < n; p++) {
                    C[i][j] += A[i][p] * B[p][j];
                }
            }
        }

        return C;
    }

}

• O(2^n): Exponential time complexity

public class Subsets_78 {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtracking(nums, 0, new LinkedList<>(), result);
        return result;
    }

    private void backtracking(int[] nums, int currIndex,
                              LinkedList<Integer> tmpList, List<List<Integer>> result) {
        result.add(new ArrayList<>(tmpList));
        for (int i = currIndex; i < nums.length; i++) {
            tmpList.add(nums[i]);
            backtracking(nums, i + 1, tmpList, result);
            tmpList.pollLast();
        }
    }
}

• O(n!) : Factorial Time Complexity ตัวอย่างนี้ นู้นเลยไปที่ Permutation ที่เรื่อง Math พูดไว้ก่อนหน้านี้ (call stack recursive ลงไปแล้ว ยังอุตส่าห์สแกนทุกตัวด้วย Flag อีก)

public class Permutation_46 {
    public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        boolean[] isUsed = new boolean[nums.length];
        backtracking(nums, new LinkedList<>(), result, isUsed);
        return result;
    }

    private void backtracking(int[] nums, LinkedList<Integer> tmpList,
                              List<List<Integer>> result, boolean[] isUsed) {
        if (tmpList.size() == nums.length) {
            result.add(new ArrayList<>(tmpList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (isUsed[i]) {
                continue;
            }
            isUsed[i] = true;
            tmpList.add(nums[i]);
            backtracking(nums, tmpList, result, isUsed);
            isUsed[i] = false;
            tmpList.pollLast();
        }
    }
}

Array

โครงสร้างข้อมูลที่จัดเก็บตามลำดับ และมีขนาดคงที่ ข้อมูลต้องเป็นประเภทเดียวกัน โดยสามารถเข้าถึงข้อมูลได้ด้วย Index ใช้สำหรับการจัดเก็บข้อมูลจำนวนมากที่ต้องเก็บติดกันในหน่วยความจำ สามารถเข้าถึงได้อย่างรวดเร็ว

int[] numbers = new int[5];

// Assign the values of the array elements
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 3;
numbers[3] = 4;
numbers[4] = 5;

int first = numbers[0];  // first will be 1
int last = numbers[4];   // last will be 5

Linked List

Linked List เป็นโครงสร้างข้อมูล ที่มองเป็นกลุ่มของ Node โดยในแต่ละ Node ก็จะเก็บ reference ไปที่ element อื่น ๆ ภายใน List และด้วยเหตุนี้เอง Linked List ไม่จำเป็นต้องมี Memory Address ติดกัน และด้วยความที่ว่าถ้าต้องการ Access data ภายใน Linked List จะทำได้ช้ากว่า Array ดังนั้นมักจะใช้กับข้อมูลที่ไม่จำเป็น access ไว ๆ เพราะเหตุนี้เอง Linked List จึงเหมาะกับข้อมูลที่เราเองก็ไม่รู้ size ล่วงหน้า และใช้กับข้อมูลที่ต้อง Insert/Remove บ่อย ๆ

โดย Linked List ประกอบไปด้วย

Singly Linked List

Doubly Linked List

Circular Linked List

ตัวอย่าง Java Code ที่จะนำมายกตัวอย่างจะเป็น Singly Linked List

public class ListNode {

  public int val;
  public ListNode next;

  public ListNode() {
  }

  public ListNode(int val) {
    this.val = val;
  }

  public ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }

}

public class LinkedList {
    ListNode head;
    public LinkedList() {
        this.head = null;
    }

    public void add(int data) {
        ListNode newNode = new ListNode(data);
        if (head == null) {
            head = newNode;
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
    
    public void remove(int data) {
        if (head == null) return;
        if (head.val == data) {
            head = head.next;
            return;
        }
        ListNode current = head;
        while (current.next != null) {
            if (current.next.val == data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    public void print() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}

Stack

Stack เป็นโครงสร้างข้อมูลแบบ Linear ที่เก็บ elements ตามลำดับ Last In First Out (LIFO) Stack มักใช้เพื่อเก็บข้อมูลชั่วคราวระหว่างการเรียกใช้ฟังก์ชัน (call stack) หรือเมื่อต้อง Reverse ลำดับของ elements

ฮั๊นแน๊ เคยโดน stacktrace ด่ากันรึเปล่าน้าาาา 🥹

public class StackWithApi {

    public static void exampleWithStack() {
        // ตรงนี้สามารถใช้ ArrayDeque ได้ ทำให้ไม่ต้องผ่าน Vector
        Stack<Integer> stack = new Stack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);

        // Pop an element from the stack
        int popped = stack.pop();  // popped will be 5

        // Peek at the top element of the stack
        int top = stack.peek();  // top will be 4

        // Check if the stack is empty
        boolean isEmpty = stack.empty();  // isEmpty will be false

        // Get the size of the stack
        int size = stack.size();  // size will be 4
    }

}

อันนี้แบบ Own-Array และ Own-LinkedList

Queue

Queue เป็นโครงสร้างข้อมูลแบบ Linear ที่เก็บ elements ตามลำดับ First In First Out (FIFO) มักใช้เพื่อจัดเก็บข้อมูลที่ต้องประมวลผลตามลำดับ หรือเพื่อจัดส่งข้อมูลแบบ Asynchronous ระหว่างระบบ

public class QueueWithApi {

    public static void exampleByLinkedList() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);

        int removed = queue.remove();  // removed will be 1

        int head = queue.peek();  // head will be 2

        boolean isEmpty = queue.isEmpty();  // isEmpty will be false

        int size = queue.size();  // size will be 4
    }
}

String

ไม่มีอะไรมาก String เป็นข้อมูลที่ใช้ represent text พื้นหลังของ String คือ array of characters “Hello World!” โดยส่วนมากชุดข้อมูล String ในแต่ละภาษาจะเป็น Immutable (บางภาษาเหมือนมันเปลี่ยนได้ แต่พื้นหลังมันสร้าง String ใหม่)

Hash Function

Hash Function มักใช้เพื่อสร้างโครงสร้างข้อมูลที่สามารถจัดเก็บ ค้นหา และ Access ข้อมูลได้อย่างรวดเร็วและมีประสิทธิภาพ

Simple Hash Function แบบ Simple จริง ๆ

public int hash(int key) {
  return key % 6;  // Return the remainder of key divided by 6
}

โครงสร้างข้างในสามารถปรับเปลี่ยนได้ตามใจ แต่ต้องคำนึงว่า Hash แล้ว มัน Unique มากน้อยแค่ไหน และตัวข้างบนนี่คือตัวอย่างแบบง่าย ๆ

Hash Table

Hash Tableใช้ในการจัดเก็บ ค้นหา และเรียกใช้ข้อมูลอย่างรวดเร็วและมีประสิทธิภาพ Ideal time คือ O(1) โดยการทำงานคือ เมื่อได้รับ Input มาแล้ว จะได้ค่า Hash มา หลังจากนั้นเอาไปใส่ใน Hash Tabler

เวลาเรียกใช้งาน ก็จะเป็นประมาณนี้ จะเป็นการ Access ตรง ๆ กับ Hash Table

hash_key = hash_function(key)
data = HashTable[hash_key]

ถ้าเกิดว่าใช้งานด้วย HashMap ของ Java จะได้ดังนี้

public class HashTableWithHashMap {
    public static void example() {
        HashMap<Integer, String> map = new HashMap<>();
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        System.out.println(map.get(1));  // prints "One"
        System.out.println(map.get(2));  // prints "Two"
        System.out.println(map.get(3));  // prints "Three"
    }
}

Hash Collision & Resolve

Hash collision หรือ key ชน เกิดขึ้นเมื่อ key ที่แตกต่างกันสอง key ถูก Mapping เข้ากับ index ของ Hash Table ซึ่งอาจทำให้เกิดปัญหาเมื่อพยายามดึงข้อมูลหรืออัปเดตค่าบน key ตัวนี้ได้

วิธีแก้

1. Separate chaining
2. Open addressing
3. Rehashing

ด้านล่างคือรูปภาพตัวอย่างของ Separate chaining

อันนี้ตัวอย่าง Separate chaining แบบเป็นโค้ด ถ้าคุณผู้อ่านสนใจนะ 😆

ดังนั้นเมื่อเกิดการชนกันแล้ว Hash Table worst case Time Complexity จะกลายเป็น O(n)

Recursion

Recursion/Recursive เป็นเทคนิคการเขียนโปรแกรมที่ฟังก์ชันเรียกตัวเองโดยปรับเปลี่ยน Input ไปในแต่ละรอบ เพื่อ solve task ที่เล็กที่สุด มีประสิทธิภาพแก้ปัญหาสูง เพราะเป็นการใช้ฟังก์ชันเดิม แต่ปรับเปลี่ยน Input แต่เพราะแบบนั้น ทำให้ยากต่อการเข้าใจและนำไปใช้ได้อย่างถูกต้อง (แต่ไม่ได้บอกว่ายากจนเขาไม่ใช้นะ เขาก็ใช้กันเยอะแยะถ้าเข้าใจ)

Key components

• Base case จุดที่ Recursive หยุดลงและ return result ถ้าลืม เตรียมแตก
• Recursive case จุดที่ใช้ Recursive การแก้ปัญหา
• Recursive call จุดที่เราเรียกฟังก์ชันตัวมันเอง แต่เปลี่ยนแปลง Input

ตัวอย่างผมจะทำเลขยกกำลังอ่ะ

public double power(double x, int n) {
  if (n == 0) {
    return 1;  // base case
  }
  // recursive case: when n is greater than 0,  return x multiplied by the power of x at n - 1
  return x * power(x, n - 1);  // power(x, n - 1) -> recursive call
}

และในบางครั้งเนื่องจาก Recursive มี Cost computing สูงมาก เพราะเวลาทำงาน ก็จะ call เป็น call stack ไป และไอพวก base case ต้น ๆ เนี่ย มันก็ดันใช้ค่าเดิม ๆ ซ้ำกันอีก มันก็มีเลยแนวคิด Dynamic Programming ขึ้นมานั่นเอง 😂

Searching

ตรงตัวเลย มันคือการค้นหา element ที่เราต้องการภายใน Data Structure ที่จัดเก็บข้อมูลไว้

Linear Search

ก็คือหาไปตรง ๆ เนี่ยแหละ Worst case ของเราก็จะเป็น O(n)

public class LinearSearch {

    public static int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

Binary Search

การค้นหาด้วย Binary Search ทุกครั้งที่เราหาไม่เจอ ชุดของการตัดสินใจจะลดลงครึ่งนึง ใช้ได้กับเฉพาะข้อมูลที่ถูกจัดเรียงแล้วเท่านั้น

ก่อนหน้านี้ผมยกตัวอย่างไปรอบนึงแล้วใน Big-O ใช่มั้ยล่ะ 😁 งั้นขอยกมาไว้ตรงนี้อีกรอบนึง ชดเชยด้วยการใส่ Implement แบบ recursive ไปด้วย เพราะเพิ่งเรียนกันไป

Iterative

public class BinarySearch {

    public static int iterative(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (target < array[mid]) {
                right = mid - 1;
            } else if (target > array[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }
}

Recursive

public class BinarySearch {

    public static int recursive(int[] array, int target) {
        return recursive(array, 0, array.length - 1, target);
    }

    private static int recursive(int[] array, int left, int right, int target) {
        int mid = left + (right - left) / 2;
        if (array[mid] == target) {
            return mid;
        }
        if (target < array[mid]) {
            return recursive(array, left, mid -  1, target);
        } else if (target > array[mid]) {
            return recursive(array, mid + 1, right, target);
        }
        return -1;
    }
}

Sorting

เวลาที่คุณต้องการที่จะเรียงอะไรซักอย่างให้เป็นระเบียบ คุณมีวิธีการเรียงยังไงบ้าง

• มองหาตามตัวอักษร
• ตามลำดับตัวเลข
• จากน้อยไปมาก
• จากมากไปน้อย
• เอาตัวที่เราเห็นเอาเข้าไปแทรก

ทั้งนี้ทั้งนั้นอันนี้ก็คือผมพูดในเรื่องของโลกความจริง แล้ว Sorting ที่เรากำลังอ่านอยู่นี่ล่ะ 🤔

Sorting Algorithms ใช้เพื่อจัดเรียงข้อมูลใหม่ตามลำดับที่ระบุหรือเงื่อนไขที่เราได้กำหนดไว้

• ASC จากน้อยไปมาก
• DESC จากมากไปน้อย

ในที่นี้ขอยกตัวอย่างมาดังรายการข้างล่างดังนี้ โดยอ้างอิงจาก Repository ของทางผู้เขียน ร่วมด้วย

Insertion Sort

เมื่อต้องการจัดเรียง การจัดเรียงจะแทรกแต่ละ elements ลงในตำแหน่งที่ถูกต้องโดยจะค่อยเลื่อนไปทีละตัวจากตัวที่ได้จัดเรียงแล้ว

Source: Insertion Sort

package datastructurealgorithms.sorting;

import utility.Util;

public class InsertionSort {

  public static int[] sorted(int[] array) {
    for (int i = 1; i < array.length; i++) {
      int j = i;
      while (j > 0 && array[j] < array[j - 1]) {
        Util.swap(array, j, j - 1);
        j--;
      }
    }
    return array;
  }
}

Selection Sort

เลือก element ที่เล็กหรือใหญ่ที่สุดในแต่ละรอบโดยการไล่ค้นหาตลอดทั้งชุดข้อมูลที่ยังไม่ได้ถูกจัดเรียง เมื่อจบแต่ละรอบ จะทำการเอา element นั้นไปอยู่ในจุดที่ถูกต้อง

Source: Selection Sort Tutorials & Notes | Algorithms | HackerEarth

package datastructurealgorithms.sorting;

import utility.Util;

public class SelectionSort {

  public static int[] sorted(int[] array) {
    for (int i = array.length - 1; i >= 0; i--) {
      int largestIndex = 0;
      for (int j = 0; j <= i; j++) {
        if (array[j] > array[largestIndex]) {
          largestIndex = j;
        }
      }
      Util.swap(array, i, largestIndex);
    }
    return array;
  }
}

Bubble Sort

Bubble sort ทำงานโดยการวนซ้ำข้อมูลและสลับ element ที่อยู่ติดกันที่ไม่ได้จัดเรียงอย่างถูกต้องตามเงื่อนไข และทำซ้ำไปเรื่อย ๆจนกว่าข้อมูลจะถูกจัดเรียงอย่างสมบูรณ์

package datastructurealgorithms.sorting;

import utility.Util;

public class BubbleSort {

  public static int[] sorted(int[] array) {
    for (int i = array.length - 1; i >= 0; i--) {
      // j < i that's mean even i is last element
      // j will not equals i => j + 1 valid
      for (int j = 0; j < i; j++) {
        if (array[j] > array[j + 1]) {
          Util.swap(array, j, j + 1);
        }
      }
    }
    return array;
  }
}

Quick Sort

Key components

• Pivot (ตัวแรก/ตัวสุดท้าย/ตัวกลาง/สุ่ม)
• Partitioning
• Divide and Conquer

Quick Sort ทำงานโดยการเลือก Pivot element จากชุดข้อมูลและใช้เพื่อแบ่งข้อมูลออกเป็นสองส่วน

1. ส่วนที่เล็ก/น้อยกว่า Pivot
2. ส่วนที่ใหญ่/มากกว่า Pivot

จากนั้น Pivot element จะอยู่ระหว่าง 2 list และทำกระบวนการนี้ซ้ำบนทั้งสองส่วนที่แบ่งไป เมื่อ Base case ในทุก ๆ sub-sort แล้ว การ sorting จะเสร็จสมบูรณ์

Source: Quicksort vs. Heapsort | Baeldung on Computer Science

package datastructurealgorithms.sorting;

import utility.Util;

public class QuickSort {

  public static int[] sorted(int[] array) {
    quickSort(array, 0, array.length - 1);
    return array;
  }

  private static void quickSort(int[] array, int left, int right) {
    int partitionIndex = partition(array, left, right);
    if (left < partitionIndex - 1) {
      quickSort(array, left, partitionIndex - 1);
    }
    if (partitionIndex < right) {
      quickSort(array, partitionIndex, right);
    }
  }

  private static int partition(int[] array, int left, int right) {
    int pivotIndex = left + (right - left) / 2;
    int pivotData = array[pivotIndex];
    while (left <= right) {
      while (array[left] < pivotData) {
        left++;
      }
      while (array[right] > pivotData) {
        right--;
      }
      if (left <= right) {
        Util.swap(array, left++, right--);
      }
    }
    return left;
  }
}

Merge Sort

Key components

• Merging
• Divide and Conquer

Merge Sort ทำงานโดยแบ่งข้อมูล 2 ส่วนลงไปเล็กลง ๆ จนถึง Base case (1 element) หลังจากนั้นค่อย ๆ building ตัว sorting result แต่ละชุดขึ้นมา ด้วยการไล่พิจารณา merge ตัว result เข้าทีละตัว จนการ sorting เสร็จสมบูรณ์

Source: Merge sort — Wikipedia

package datastructurealgorithms.sorting;

public class MergeSort {

  public static int[] sorted(int[] array) {
    // Create helper array
    int[] helper = new int[array.length];
    mergeSort(array, helper, 0, array.length - 1);
    return array;
  }

  private static void mergeSort(int[] array, int[] helper, int start, int end) {
    if (start < end) {
      int mid = start + (end - start) / 2;
      mergeSort(array, helper, start, mid);
      mergeSort(array, helper, mid + 1, end);
      merge(array, helper, start, mid, end);
    }
  }

  private static void merge(int[] array, int[] helper, int start, int mid, int end) {
    // Copy to helper
    for (int i = start; i <= end; i++) {
      helper[i] = array[i];
    }
    // Places 2 pointers
    int helperLeft = start;
    int writeIndex = start;
    int helperRight = mid + 1;

    while (helperLeft <= mid && helperRight <= end) {
      if (helper[helperLeft] <= helper[helperRight]) {
        array[writeIndex] = helper[helperLeft++];
      } else {
        array[writeIndex] = helper[helperRight++];
      }
      writeIndex++;
    }

    int remaining = mid - helperLeft;
    for (int i = 0; i <= remaining; i++) {
      array[writeIndex++] = helper[helperLeft++];
    }
  }
}

ด้านล่างนี้เป็น Sorting Algorithms Time Complexity อาจจะจำเฉพาะตัวที่ทางผมยกตัวอย่างก็ได้ แต่ถ้าจำได้หมดเลย ก็ดีมากครับ แต่ผมจำได้ไม่หมดหรอก 🥹

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

ขอให้ทุกคนมีความสุขครับ 🙇‍♂️

FB ไว้ตอบปัญหา: Thanaphoom Babparn
FB Page ไว้ตอบปัญหา & แชร์ไปเรื่อย: TP Coder
LinkedIn: Thanaphoom Babparn
Linktree: https://linktr.ee/tpbabparn