Implement Stalin Sort 🃏

[Ink01101011]

Stalin Sort เป็นอัลกอริทึมสาย "Meme" ที่โด่งดังที่สุดในโลกอินเทอร์เน็ตครับ โดยชื่อของมันล้อเลียนแนวคิดของ Joseph Stalin ผู้นำสหภาพโซเวียตที่ขึ้นชื่อเรื่องการกำจัดคนที่ไม่เห็นด้วยออกไป

ในขณะที่อัลกอริทึมอื่นๆ พยายาม "จัดระเบียบ" ข้อมูลให้เข้าที่ Stalin Sort เลือกวิธีที่เด็ดขาดกว่านั้นคือ "ถ้าตัวไหนวางผิดที่ ก็ลบทิ้งไปซะ!"

---

💡 แนวคิดหลัก: การกำจัดจุดอ่อน (Elimination)

กฎของ Stalin Sort เรียบง่ายมากครับ:

1. เดินตรวจแถวข้อมูลจากซ้ายไปขวา
2. ถ้าเจอข้อมูลตัวไหนที่ "น้อยกว่า" ตัวก่อนหน้า (ซึ่งทำให้แถวไม่เรียงลำดับ)
3. ส่งมันไปกูลัก (Gulag): คือลบข้อมูลตัวนั้นออกจาก Array ทันที!
4. ผลลัพธ์ที่ได้คือ Array ที่เรียงลำดับจากน้อยไปมากแน่นอน (แต่ข้อมูลอาจจะหายไปเพียบ)

---

🛠 ขั้นตอนการทำงาน Step-by-Step

สมมติข้อมูลคือ [1, 2, 5, 3, 4, 7, 6]

1. เริ่มที่ 1 -> เก็บไว้
2. ตรวจ 2 (2 > 1) -> เรียงถูก -> เก็บไว้
3. ตรวจ 5 (5 > 2) -> เรียงถูก -> เก็บไว้
4. ตรวจ 3 (3 < 5) -> ผิดระเบียบ! -> ลบ 3 ทิ้ง
5. ตรวจ 4 (4 < 5) -> ผิดระเบียบ! -> ลบ 4 ทิ้ง
6. ตรวจ 7 (7 > 5) -> เรียงถูก -> เก็บไว้
7. ตรวจ 6 (6 < 7) -> ผิดระเบียบ! -> ลบ 6 ทิ้ง
   ผลลัพธ์สุดท้าย: [1, 2, 5, 7]

---

💻 ตัวอย่าง Code (TypeScript) สำหรับ exsorted

export const stalinSort = <T>(arr: T[]): T[] => {
  if (arr.length === 0) return [];

  const result: T[] = [arr[0]];

  for (let i = 1; i < arr.length; i++) {
    // เก็บเฉพาะตัวที่มากกว่าหรือเท่ากับตัวล่าสุดใน result เท่านั้น
    if (arr[i] >= result[result.length - 1]) {
      result.push(arr[i]);
    }
  }

  return result;
};

---

📊 วิเคราะห์ประสิทธิภาพ (Complexity)

• Time Complexity: $O(n)$ (เร็วระดับปีศาจ เพราะตรวจรอบเดียวจบ!)
• Space Complexity: $O(n)$ (สำหรับเก็บผลลัพธ์ใหม่)
• Data Integrity: 0% (ข้อมูลของคุณอาจหายไปเกือบหมดถ้ามันไม่ได้เรียงมาตั้งแต่แรก)

---