ការតម្រៀប

មាតិកា

1. ហេតុអ្វីត្រូវតម្រៀប
2. Bubble Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Stability
7. Array.sort និងអន្ទាក់ Default-String
8. Counting Sort និងដែនកំណត់ O(n log n)
9. Benchmark
10. រូបមន្ត៖ sorting.ts សម្រាប់ algolab
11. សាកល្បងដោយខ្លួនឯង

1. ហេតុអ្វីត្រូវតម្រៀប

ការតម្រៀបកម្រជាគោលដៅណាស់។ វាជា ជំហានរៀបចំ ដែលធ្វើឲ្យរឿងផ្សេងទៀតថោក៖

• Binary search (ជំពូកមុន) ត្រូវការទិន្នន័យដែលបានតម្រៀប។
• ការរកធាតុស្ទួនក្លាយជាងាយស្រួល៖ ធាតុស្មើគ្នាបញ្ចប់នៅជាប់គ្នា។
• ការ merge បញ្ជីដែលបានតម្រៀបពីរ ប្រើតែមួយ pass។
• មនុស្សរំពឹងចង់បានលទ្ធផលដែលបានតម្រៀប៖ ផលិតផលតាមតម្លៃ, សារតាមកាលបរិច្ឆេទ, leaderboard តាមពិន្ទុ។

ក្នុងការងារប្រចាំថ្ងៃ អ្នកស្ទើរតែតែងតែហៅ array.sort() ដែលមានស្រាប់។ ដូច្នេះហេតុអ្វីត្រូវរៀនសរសេរវា? មានហេតុផលបី។ ទីមួយ ការតម្រៀបគឺជាកន្លែងស្អាតបំផុតដើម្បីមើលថា algorithm ផ្សេងៗដោះដូរល្បឿន អង្គចងចាំ និងភាពសាមញ្ញយ៉ាងដូចម្តេច។ ទីពីរ គំនិតនៅក្នុង merge sort និង quick sort (divide and conquer) លេចឡើងម្តងទៀតក្នុង tree, heap និង dynamic programming។ ទីបី អ្នកសម្ភាសន៍សួរអំពីវា ហើយ function ដែលមានស្រាប់មានគែមមុតស្រួច (ផ្នែកទី 7) ដែលអ្នកអភិវឌ្ឍន៍ JavaScript គ្រប់រូបត្រូវដឹង។

ការតម្រៀបក្នុងជំពូកនេះចែកជាពីរគ្រួសារ៖

ចងចាំពី ជំពូក Big-O ថាគម្លាតនោះមានន័យអ្វី៖ សម្រាប់ 1,000,000 ធាតុ n² គឺមួយ trillion ជំហាន ខណៈពេលដែល n log n ប្រហែល 20 លាន។

ការតម្រៀបទាំងអស់របស់យើងធ្វើតាមទំនៀមទម្លាប់មួយ។ ពួកវាទទួល function compare(a, b) ដែលត្រឡប់លេខ អវិជ្ជមាន បើ a គួរមកមុន លេខ វិជ្ជមាន បើ b គួរមកមុន និង 0 បើស្មើគ្នា។ នេះគឺជាកិច្ចសន្យាដូចគ្នាដែល Array.prototype.sort ប្រើ។ ហើយពួកវាត្រឡប់ array ថ្មី ជំនួសឲ្យការផ្លាស់ប្តូរ input ដែលមានសុវត្ថិភាពជាង។

2. Bubble Sort

ដើរកាត់ array ហើយប្រៀបធៀបគូជិតគ្នានីមួយៗ។ បើគូណាមួយខុសលំដាប់ ប្តូរកន្លែងវា។ ក្រោយ pass ពេញមួយ ធាតុធំបំផុត "ផុស" ទៅចុង។ ធ្វើម្តងទៀតសម្រាប់ផ្នែកដែលនៅសល់។

មួយ pass លើ [5, 1, 4, 2, 8]៖

[5, 1, 4, 2, 8]   compare 5,1 -> swap
[1, 5, 4, 2, 8]   compare 5,4 -> swap
[1, 4, 5, 2, 8]   compare 5,2 -> swap
[1, 4, 2, 5, 8]   compare 5,8 -> fine

លេខ 8 នៅត្រឹមត្រូវកន្លែងរួចហើយ ហើយលេខ 5 បានផ្លាស់មកជាប់វា។ pass បន្ទាប់នីមួយៗជួសជុលធាតុមួយទៀតនៅចុង៖

type Compare<T> = (a: T, b: T) => number;

const byDefault = <T>(a: T, b: T): number => (a < b ? -1 : a > b ? 1 : 0);

function bubbleSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items]; // ធ្វើការលើច្បាប់ចម្លង

  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;

    for (let i = 0; i < a.length - 1 - pass; i++) {
      if (compare(a[i], a[i + 1]) > 0) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }

    if (!swapped) break; // គ្មានការប្តូរមានន័យថាតម្រៀបរួចហើយ
  }

  return a;
}

console.log(bubbleSort([5, 2, 9, 1, 5, 6])); // [ 1, 2, 5, 5, 6, 9 ]

- pass ក្នុង inner loop រំលងកន្ទុយដែលត្រូវបានជួសជុលរួច។ flag swapped ផ្តល់ការចេញមុនកំណត់៖ លើ input ដែលតម្រៀបរួច pass មួយរកមិនឃើញអ្វីត្រូវប្តូរ ហើយឈប់ ដូច្នេះករណីល្អបំផុតគឺ O(n)។

ករណីអាក្រក់បំផុត និងមធ្យមគឺ O(n²)៖ ប្រហែល n pass ដែលមានការប្រៀបធៀបប្រហែល n ដងក្នុងមួយ pass។ Bubble sort ភាគច្រើនជាឧបករណ៍បង្រៀន។ វាងាយយល់ ប៉ុន្តែយឺត ហើយគ្មាន library ពិតប្រាកដណាប្រើវាទេ។

3. Insertion Sort

គិតពីការតម្រៀបបៀរក្នុងដៃរបស់អ្នក។ អ្នកលើកបៀរម្តងមួយសន្លឹក ហើយរុញវាទៅឆ្វេងចូលកន្លែងត្រឹមត្រូវក្នុងចំណោមបៀរដែលអ្នកកាន់រួចហើយ។

[5, 2, 4, 1]
 i=1: take 2, shift 5 right        -> [2, 5, 4, 1]
 i=2: take 4, shift 5 right        -> [2, 4, 5, 1]
 i=3: take 1, shift 5, 4, 2 right  -> [1, 2, 4, 5]

function insertionSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];

  for (let i = 1; i < a.length; i++) {
    const current = a[i];
    let j = i - 1;

    // រុញធាតុធំជាងទៅស្តាំមួយជំហាន ដើម្បីបើកចន្លោះ
    while (j >= 0 && compare(a[j], current) > 0) {
      a[j + 1] = a[j];
      j--;
    }

    a[j + 1] = current; // ទម្លាក់វាចូលចន្លោះ
  }

  return a;
}

console.log(insertionSort([5, 2, 9, 1, 5, 6])); // [ 1, 2, 5, 5, 6, 9 ]

អ្វីៗនៅខាងឆ្វេងនៃ i តែងតែបានតម្រៀប (នេះគឺជា invariant ការពិតដែលនៅតែពិតរាល់ការវិលនៃ loop)។ ធាតុថ្មីនីមួយៗត្រូវបានបញ្ចូលដើម្បីរក្សាវាឲ្យនៅពិត។

ករណីអាក្រក់បំផុត (លំដាប់ត្រឡប់) គឺ O(n²)។ ប៉ុន្តែ insertion sort មានចំណុចខ្លាំងពិតប្រាកដមួយ៖ លើទិន្នន័យដែល ជិតតម្រៀបរួចហើយ វាជិត O(n) ព្រោះធាតុនីមួយៗផ្លាស់ទីតែមួយ ឬពីរជំហាន។ វាក៏មាន overhead ស្ទើរតែគ្មានដែរ។ នោះជាមូលហេតុដែល algorithm តម្រៀបដ៏ធ្ងន់ធ្ងរ រួមទាំងមួយនៅក្នុង V8 ប្តូរទៅ insertion sort សម្រាប់ចំណែកតូចៗ។

4. Merge Sort

Merge sort ប្រើ divide and conquer៖ បំបែកបញ្ហាជាពាក់កណ្តាល ដោះស្រាយពាក់កណ្តាលនីមួយៗ រួចបញ្ចូលចម្លើយ។ សម្រាប់ការតម្រៀប៖

1. បំបែក array ជាពាក់កណ្តាលខាងឆ្វេង និងពាក់កណ្តាលខាងស្តាំ។
2. តម្រៀបពាក់កណ្តាលនីមួយៗ (ដោយហៅ merge sort ម្តងទៀត ដែលជា recursion)។
3. Merge ពាក់កណ្តាលទាំងពីរដែលបានតម្រៀបទៅជា array មួយដែលបានតម្រៀប។

base case គឺ array ដែលមាន 0 ឬ 1 ធាតុ ដែលបានតម្រៀបរួចហើយ។

អព្ភូតហេតុស្ថិតនៅក្នុងជំហាន merge។ ការ merge បញ្ជីដែលបានតម្រៀបពីរគឺងាយ៖ រក្សា pointer មួយក្នុងបញ្ជីនីមួយៗ ហើយយកធាតុខាងមុខតូចជាងម្តងហើយម្តងទៀត។ ការ merge [1, 4, 7] និង [2, 3, 9]៖

left [1,4,7]   right [2,3,9]   take 1 -> [1]
left [4,7]     right [2,3,9]   take 2 -> [1,2]
left [4,7]     right [3,9]     take 3 -> [1,2,3]
left [4,7]     right [9]       take 4 -> [1,2,3,4]
left [7]       right [9]       take 7 -> [1,2,3,4,7]
left []        right [9]       copy 9 -> [1,2,3,4,7,9]

function mergeSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  if (items.length <= 1) return [...items];

  const mid = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, mid), compare);
  const right = mergeSort(items.slice(mid), compare);

  return merge(left, right, compare);
}

function merge<T>(left: T[], right: T[], compare: Compare<T>): T[] {
  const out: T[] = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    // <= យកពីខាងឆ្វេងនៅពេលស្មើគ្នា ដែលរក្សា sort ឲ្យ stable
    if (compare(left[i], right[j]) <= 0) out.push(left[i++]);
    else out.push(right[j++]);
  }

  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);

  return out;
}

console.log(mergeSort([5, 2, 9, 1, 5, 6])); // [ 1, 2, 5, 5, 6, 9 ]

ហេតុអ្វីបានជា O(n log n)? ការបែងចែក array ដែលមាន n ធាតុជាពាក់កណ្តាល ត្រូវការប្រហែល log₂ n កម្រិត ព្រោះអ្នកអាចបែងចែកជាពាក់កណ្តាលបានតែចំនួនដងមានកំណត់។ នៅគ្រប់កម្រិត ការ merge ទាំងអស់រួមគ្នាប៉ះធាតុទាំង n ម្តងម្នាក់។ ដូច្នេះសរុបគឺ n × log n៖

level 0:  [ 8 items ]                  merge work: 8
level 1:  [ 4 ]   [ 4 ]                merge work: 8
level 2:  [2] [2] [2] [2]              merge work: 8
level 3:  [1][1][1][1][1][1][1][1]     merge work: 8

បំបែកបីដង ហើយកម្រិតនីមួយៗចំណាយការងារ 8 ឯកតា៖ 8 × log₂ 8 = 24។ សម្រាប់មួយលានធាតុ គឺ 20 កម្រិត។ សំខាន់ណាស់ វាពិត គ្រប់ ករណី៖ input ដែលតម្រៀបរួច ត្រឡប់ ឬចៃដន្យ សុទ្ធតែចំណាយ O(n log n)។

តម្លៃដែលត្រូវបង់គឺអង្គចងចាំ។ Merge sort ត្រូវការ O(n) ទំហំបន្ថែមសម្រាប់ array បណ្តោះអាសន្ន។ គុណសម្បត្តិធំរបស់វាគឺល្បឿនដែលធានា និងការដែលវា stable (ផ្នែកទី 6)។

5. Quick Sort

Quick sort ក៏ divide and conquer ដែរ ប៉ុន្តែធ្វើការងារ មុន recursion ជំនួសឲ្យក្រោយ៖

1. ជ្រើសធាតុមួយជា pivot។
2. Partition៖ រៀបចំឲ្យគ្រប់ធាតុតូចជាង pivot នៅខាងឆ្វេងរបស់វា ហើយគ្រប់ធាតុធំជាងនៅខាងស្តាំ។ ឥឡូវ pivot ស្ថិតនៅទីតាំងចុងក្រោយរបស់វា។
3. តម្រៀបផ្នែកខាងឆ្វេង និងផ្នែកខាងស្តាំដោយ recursion។

គ្មានជំហាន merge ទេ ដូច្នេះ quick sort អាចធ្វើការ in place ដោយប្រើតែ O(log n) ទំហំបន្ថែមសម្រាប់ recursion។ ក្នុងការអនុវត្ត ជារឿយៗវាលឿនបំផុតក្នុងចំណោម sort ទូទៅទាំងអស់ ព្រោះវាប៉ះអង្គចងចាំតាមរបៀបដែលរួសរាយនឹង cache។

ជំហាន partition គឺជាផ្នែកឆ្លាតវៃ។ យើងប្រើ Lomuto scheme៖ ដាក់ pivot នៅចុង រក្សាព្រំដែន i រវាង "តូចជាង pivot" និង "ផ្នែកដែលនៅសល់" ហើយបោសសម្អាត j កាត់ជួរ៖

function quickSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];
  sortRange(a, 0, a.length - 1, compare);
  return a;
}

function sortRange<T>(a: T[], lo: number, hi: number, compare: Compare<T>): void {
  while (lo < hi) {
    const p = partition(a, lo, hi, compare);

    // recurse ចូលផ្នែកតូចជាង ហើយ loop លើផ្នែកធំជាង
    // ដូច្នេះ call stack មិនដែលជ្រៅជាង log n
    if (p - lo < hi - p) {
      sortRange(a, lo, p - 1, compare);
      lo = p + 1;
    } else {
      sortRange(a, p + 1, hi, compare);
      hi = p - 1;
    }
  }
}

function partition<T>(a: T[], lo: number, hi: number, compare: Compare<T>): number {
  // pivot ចៃដន្យ ផ្លាស់ទៅចុង
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [a[r], a[hi]] = [a[hi], a[r]];
  const pivot = a[hi];

  let i = lo; // អ្វីៗក្នុង [lo, i) តូចជាង pivot
  for (let j = lo; j < hi; j++) {
    if (compare(a[j], pivot) < 0) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  }

  [a[i], a[hi]] = [a[hi], a[i]]; // pivot ទៅកាន់ទីតាំងចុងក្រោយរបស់វា
  return i;
}

console.log(quickSort([5, 2, 9, 1, 5, 6])); // [ 1, 2, 5, 5, 6, 9 ]

ការ partition [3, 8, 1, 5] ដោយ pivot 5 (នៅចុងរួចហើយ)៖

i=0, j=0: 3 < 5 -> swap a[0] with itself, i=1     [3, 8, 1, 5]
i=1, j=1: 8 < 5? no                               [3, 8, 1, 5]
i=1, j=2: 1 < 5 -> swap a[1] and a[2], i=2        [3, 1, 8, 5]
finish:   swap a[2] and the pivot                 [3, 1, 5, 8]

Pivot 5 ស្ថិតនៅ index 2 អ្វីៗខាងឆ្វេងតូចជាង អ្វីៗខាងស្តាំធំជាង។

ការជ្រើស pivot សំខាន់។ បើអ្នកតែងតែជ្រើសធាតុចុងក្រោយ ហើយ input បានតម្រៀបរួច partition នីមួយៗបកបានតែមួយធាតុ ធ្វើឲ្យ O(n²)។ នោះជាមូលហេតុដែលយើងជ្រើស pivot ចៃដន្យ៖ គ្មាន input ណាមួយអាក្រក់ជាប្រចាំទេ។ បន្ទាប់មកករណីមធ្យមគឺ O(n log n) ហើយករណីអាក្រក់បំផុតកម្រខ្លាំងដល់ថាអ្នកអាចមិនអើពើ។

ភាពទន់ខ្សោយមួយនៅតែមាន។ partition របស់យើងចាត់ទុកធាតុស្មើ pivot ជា "មិនតូចជាង" ដូច្នេះពួកវាទាំងអស់ធ្លាក់ទៅខាងស្តាំ។ បើ array មាន តម្លៃស្ទួន ច្រើន ការបែងចែកក្លាយជាមិនស្មើគ្នាខ្លាំង។ ក្នុងការរត់ test មួយ quickSort របស់យើងលើលេខដូចគ្នា 50,000 ប្រើពេលលើសពីមួយវិនាទី ខណៈ array ចៃដន្យទំហំនោះតម្រៀបក្នុងពីរបីមីលីវិនាទី។ ការអនុវត្តពិតប្រាកដជួសជុលវាដោយ three-way partition (តូចជាង, ស្មើ, ធំជាង)។ អ្នកនឹងធ្វើវាក្នុងលំហាត់ទី 4។

6. Stability

Sort មួយ stable ប្រសិនបើធាតុដែលប្រៀបធៀបថាស្មើគ្នារក្សាលំដាប់ទាក់ទងដើមរបស់ពួកវា។ នេះស្តាប់ទៅដូចជាព័ត៌មានលម្អិត ប៉ុន្តែវាសំខាន់ពេលណាអ្នកតម្រៀបតាមវាលច្រើនជាងមួយ។

ស្រមៃតារាងមនុស្សដែលបានតម្រៀបតាមឈ្មោះរួចហើយ។ បន្ទាប់មកអ្នកប្រើចុច "sort by age"។ ជាមួយ stable sort មនុស្សដែលមានអាយុដូចគ្នានៅតែតាមលំដាប់ឈ្មោះ។ ជាមួយ unstable sort ពួកគេត្រូវបានលាយឡំ។

const people = [
  { name: "A", age: 30 },
  { name: "B", age: 25 },
  { name: "C", age: 30 },
  { name: "D", age: 25 },
];

const byAge = (x: { age: number }, y: { age: number }) => x.age - y.age;

console.log(mergeSort(people, byAge).map((p) => p.name).join(""));
// BDAC   (B before D, A before C: original order kept inside each age)

Insertion sort និង bubble sort ក៏ stable ដែរ (ពួកវាប្តូរតែធាតុដែលខុសលំដាប់យ៉ាងតឹងរ៉ឹង)។ merge sort របស់យើង stable ដោយសារ <= ក្នុង merge៖ នៅពេលស្មើគ្នា វាយកពីខាងឆ្វេង ដែលមកមុន។ quick sort របស់យើងមិន stable ទេ ព្រោះ partition លោតធាតុកាត់គ្នា។

តាំងពី ES2019 មក Array.prototype.sort ក្នុង JavaScript ត្រូវបានតម្រូវ ឲ្យ stable ដូច្នេះអ្នកអាចពឹងផ្អែកលើវានៅក្នុង browser និង Node.js បច្ចុប្បន្នទាំងអស់។ ល្បិចងាយស្រួលមួយកើតឡើង៖ ដើម្បីតម្រៀបតាម "នាមត្រកូល បន្ទាប់មកនាមខ្លួន" ត្រូវតម្រៀបតាម key បន្ទាប់បន្សំមុន ហើយ key ចម្បងទីពីរ។

7. Array.sort និងអន្ទាក់ Default-String

ឥឡូវនេះគឺជាអន្ទាក់ដែលចាប់អ្នកអភិវឌ្ឍន៍ JavaScript ស្ទើរតែគ្រប់គ្នា។ សាកល្បងកូដនេះ៖

console.log([10, 9, 1, 100, 25].sort());
// [ 1, 10, 100, 25, 9 ]

នោះមិនបានតម្រៀបទេ! មូលហេតុ៖ ពេលគ្មាន argument sort() បំប្លែងគ្រប់ធាតុទៅជា string ហើយប្រៀបធៀប string តាមលំដាប់វចនានុក្រម។ អត្ថបទ "10" មកមុន "9" ព្រោះ "1" មកមុន "9"។ លេខត្រូវការ comparator៖

console.log([10, 9, 1, 100, 25].sort((a, b) => a - b));
// [ 1, 9, 10, 25, 100 ]

console.log([10, 9, 1, 100, 25].sort((a, b) => b - a)); // descending
// [ 100, 25, 10, 9, 1 ]

comparator (a, b) => a - b ត្រឡប់លេខអវិជ្ជមានពេល a តូចជាង (ដូច្នេះ a មកមុន) វិជ្ជមានពេលធំជាង និងសូន្យពេលស្មើគ្នា។ នោះគឺជាកិច្ចសន្យាពីផ្នែកទី 1។

អន្ទាក់ និងច្បាប់បន្ថែម៖

• sort ផ្លាស់ប្តូរ array ហើយក៏ត្រឡប់វាដែរ។ const copy = [...arr].sort(...) ជៀសវាងការខូច array ដើម។ runtime ថ្មីៗក៏មាន toSorted() ដែលត្រឡប់ច្បាប់ចម្លង។

• អក្សរធំតម្រៀបមុនអក្សរតូច ក្នុងលំដាប់ default ដោយសារ character code៖

  console.log(["banana", "apple", "Cherry"].sort());
  // [ 'Cherry', 'apple', 'banana' ]
  

  Copy

• សម្រាប់អត្ថបទដែលមនុស្សអាន ប្រើ localeCompare ដែលស្គាល់ accent និង case៖

  console.log(["banana", "apple", "Cherry"].sort((a, b) => a.localeCompare(b)));
  // [ 'apple', 'banana', 'Cherry' ]
  
  console.log(["é", "e", "z", "a"].sort());
  // [ 'a', 'e', 'z', 'é' ]  (é is after z by character code)
  
  console.log(["é", "e", "z", "a"].sort((a, b) => a.localeCompare(b)));
  // [ 'a', 'e', 'é', 'z' ]
  

  Copy

• តម្លៃ undefined តែងតែត្រូវបានផ្លាស់ទៅចុង ដោយមិនបញ្ជូនទៅ comparator របស់អ្នក។

• កុំសរសេរ (a, b) => a > b។ comparator ដែលត្រឡប់ boolean ផ្តល់ true ឬ false ដែលក្លាយជា 1 និង 0៖ វាមិនដែលនិយាយថា "a មកមុន" ទេ។ លទ្ធផលមិនអាចទុកចិត្តបាន អាស្រ័យលើ engine។

• comparator ដកអាចបែកសម្រាប់តម្លៃធំៗ ឬ NaN។ a - b ល្អសម្រាប់លេខធម្មតា។ សម្រាប់តម្លៃជិត Number.MAX_SAFE_INTEGER ឬនៅពេល NaN អាចលេចឡើង ត្រូវប្រើការប្រៀបធៀបច្បាស់លាស់។

ការតម្រៀប object តាមវាលមួយ ហើយបន្ទាប់មកតាមវាលទីពីរជា tie-breaker៖

const products = [
  { name: "Mouse", price: 25, stock: 4 },
  { name: "Cable", price: 5, stock: 40 },
  { name: "Hub", price: 25, stock: 12 },
];

products.sort((a, b) => a.price - b.price || b.stock - a.stock);

console.log(products.map((p) => p.name));
// [ 'Cable', 'Hub', 'Mouse' ]

អានវាជា "តាមតម្លៃពីតូចទៅធំ; បើភាពខុសគ្នានៃតម្លៃគឺ 0 (ដែលជា falsy) ធ្លាក់ទៅ stock ពីធំទៅតូច"។ នៅពីក្រោយ V8 ប្រើ TimSort ដែលជាល្បាយនៃ merge sort និង insertion sort ដែល stable, O(n log n) ក្នុងករណីអាក្រក់បំផុត និងជិត O(n) លើទិន្នន័យដែលស្ទើរតែមានលំដាប់រួចហើយ។ សម្រាប់ការងារពិតប្រាកដ ប្រើ function ដែលមានស្រាប់។

8. Counting Sort និងដែនកំណត់ O(n log n)

តើយើងអាចយកឈ្នះ O(n log n) បានទេ? សម្រាប់ sort ដែលដំណើរការដោយ ប្រៀបធៀប ធាតុ គឺមិនអាចទេ៖ វាជាដែនកំណត់ក្រោមដែលបានបញ្ជាក់ជាផ្លូវការ។ ជាមួយ n ធាតុ មានលំដាប់អាចមាន n! ហើយការប្រៀបធៀបនីមួយៗឆ្លើយតែបាទ/ចាស ឬទេ ដែលផ្តល់បានច្រើនបំផុត 1 bit។ អ្នកត្រូវការការប្រៀបធៀបប្រហែល log₂(n!) ដែលប្រហែល n log n។

ផ្លូវចេញគឺ មិនប្រៀបធៀប។ បើតម្លៃជាចំនួនគត់តូចៗក្នុងជួរដែលស្គាល់ អ្នកអាចរាប់វា។ Counting sort៖

1. បង្កើត array counts ដែលមាន slot មួយសម្រាប់តម្លៃអាចមាននីមួយៗ។
2. សម្រាប់លេខនីមួយៗ បន្ថែម 1 ទៅ slot របស់វា។
3. ដើរកាត់ slot តាមលំដាប់ ហើយសរសេរតម្លៃនីមួយៗចេញចំនួនដងដែលវាត្រូវបានរាប់។

function countingSort(nums: number[], max: number): number[] {
  const counts = new Array<number>(max + 1).fill(0);
  for (const n of nums) counts[n]++;

  const out: number[] = [];
  for (let value = 0; value <= max; value++) {
    for (let k = 0; k < counts[value]; k++) out.push(value);
  }
  return out;
}

console.log(countingSort([3, 1, 4, 1, 5, 2, 3], 5));
// [ 1, 1, 2, 3, 3, 4, 5 ]

វាដំណើរការក្នុង O(n + k) ដែល k គឺជួរនៃតម្លៃ (ទីនេះគឺ max)។ វាល្អប្រសើរសម្រាប់ពិន្ទុប្រឡងពី 0 ដល់ 100, អាយុ, ការវាយតម្លៃផ្កាយ ឬខ្ទង់នៅក្នុង radix sort។ វាជាជម្រើសអន់នៅពេលជួរធំសម្បើម (ការតម្រៀប user ID ពីរបីដែលមានរហូតដល់មួយពាន់លាន នឹងត្រូវការ slot មួយពាន់លាន) ឬនៅពេលតម្លៃមិនមែនជាចំនួនគត់មិនអវិជ្ជមាន។ Radix sort និង bucket sort គឺជាបងប្អូនជីដូនមួយនៃគំនិតដូចគ្នា។

9. Benchmark

តោះមើលគម្លាត Big-O ពិតប្រាកដ។ រក្សាទុកកូដនេះជា bench-sort.ts ក្នុង algolab បន្ទាប់ពីបញ្ចប់រូបមន្តក្នុងផ្នែកបន្ទាប់៖

import {
  bubbleSort,
  insertionSort,
  mergeSort,
  quickSort,
  isSorted,
} from "./src/sorting.ts";

function randomNumbers(n: number): number[] {
  return Array.from({ length: n }, () => Math.floor(Math.random() * 1_000_000));
}

const algorithms: Record<string, (a: number[]) => number[]> = {
  bubble: (a) => bubbleSort(a),
  insertion: (a) => insertionSort(a),
  merge: (a) => mergeSort(a),
  quick: (a) => quickSort(a),
  "Array.sort": (a) => [...a].sort((x, y) => x - y),
};

for (const n of [2_000, 20_000]) {
  const data = randomNumbers(n);
  for (const [name, sort] of Object.entries(algorithms)) {
    const start = performance.now();
    const result = sort(data);
    const ms = performance.now() - start;
    console.log(`n=${n} ${name.padEnd(10)} ${ms.toFixed(1)} ms`,
      isSorted(result) ? "" : "NOT SORTED");
  }
}

npx tsx bench-sort.ts

ការរត់មួយលើ laptop បានបោះពុម្ពពេលវេលាទាំងនេះ (របស់អ្នកនឹងខុសគ្នា ប៉ុន្តែរូបរាងមិនគួរខុសទេ)៖

មើលអ្វីដែលកើតឡើងពេល n ធំឡើង 10 ដង។ sort quadratic យឺតជាងប្រហែល 70 ទៅ 80 ដង (ជិត 100 ដងដែល n² ព្យាករណ៍ ជាមួយ noise) ខណៈ merge sort កើនប្រហែល 3 ឬ 4 ដង ប្រហែលដូចដែល n log n ព្យាករណ៍។ នៅ 20,000 ធាតុ bubble sort យឺតជាង merge sort លើស 100 ដងរួចហើយ ហើយនៅមួយលានធាតុ វានឹងរត់ជាច្រើននាទី។

ពេលវេលាតូចៗនៅ n = 2,000 ភាគច្រើនជា noise រួមទាំងការ warm-up របស់ JIT ដូច្នេះគួរជឿតែគម្លាតធំៗ។ រត់ករណីនីមួយៗពីរបីដង មុនសន្និដ្ឋាន។

10. រូបមន្ត៖ sorting.ts សម្រាប់ algolab

បង្កើត src/sorting.ts ជាមួយគ្រប់ algorithm ពីជំពូកនេះ៖

export type Compare<T> = (a: T, b: T) => number;

const byDefault = <T>(a: T, b: T): number => (a < b ? -1 : a > b ? 1 : 0);

export function bubbleSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let i = 0; i < a.length - 1 - pass; i++) {
      if (compare(a[i], a[i + 1]) > 0) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return a;
}

export function insertionSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];
  for (let i = 1; i < a.length; i++) {
    const current = a[i];
    let j = i - 1;
    while (j >= 0 && compare(a[j], current) > 0) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = current;
  }
  return a;
}

export function mergeSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  if (items.length <= 1) return [...items];
  const mid = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, mid), compare);
  const right = mergeSort(items.slice(mid), compare);
  return merge(left, right, compare);
}

function merge<T>(left: T[], right: T[], compare: Compare<T>): T[] {
  const out: T[] = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (compare(left[i], right[j]) <= 0) out.push(left[i++]);
    else out.push(right[j++]);
  }
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

export function quickSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];
  sortRange(a, 0, a.length - 1, compare);
  return a;
}

function sortRange<T>(a: T[], lo: number, hi: number, compare: Compare<T>): void {
  while (lo < hi) {
    const p = partition(a, lo, hi, compare);
    if (p - lo < hi - p) {
      sortRange(a, lo, p - 1, compare);
      lo = p + 1;
    } else {
      sortRange(a, p + 1, hi, compare);
      hi = p - 1;
    }
  }
}

function partition<T>(a: T[], lo: number, hi: number, compare: Compare<T>): number {
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [a[r], a[hi]] = [a[hi], a[r]];
  const pivot = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (compare(a[j], pivot) < 0) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  }
  [a[i], a[hi]] = [a[hi], a[i]];
  return i;
}

// តម្លៃត្រូវតែជាចំនួនគត់ពី 0 ដល់ max។
export function countingSort(nums: number[], max: number): number[] {
  const counts = new Array<number>(max + 1).fill(0);
  for (const n of nums) counts[n]++;
  const out: number[] = [];
  for (let value = 0; value <= max; value++) {
    for (let k = 0; k < counts[value]; k++) out.push(value);
  }
  return out;
}

export function isSorted<T>(items: T[], compare: Compare<T> = byDefault): boolean {
  for (let i = 1; i < items.length; i++) {
    if (compare(items[i - 1], items[i]) > 0) return false;
  }
  return true;
}

ឥឡូវនេះ test ក្នុង src/sorting.test.ts។ Loop មួយរត់គ្រប់ algorithm លើករណីដូចគ្នា ហើយ test ទីពីរប្រៀបធៀបពួកវាជាមួយ sort ដែលមានស្រាប់លើទិន្នន័យចៃដន្យ៖

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  bubbleSort,
  insertionSort,
  mergeSort,
  quickSort,
  countingSort,
  isSorted,
} from "./sorting.ts";

const sorts = { bubbleSort, insertionSort, mergeSort, quickSort };

for (const [name, sort] of Object.entries(sorts)) {
  test(`${name} sorts the usual cases`, () => {
    assert.deepEqual(sort([]), []);
    assert.deepEqual(sort([1]), [1]);
    assert.deepEqual(sort([5, 2, 9, 1, 5, 6]), [1, 2, 5, 5, 6, 9]);
    assert.deepEqual(sort([3, 2, 1]), [1, 2, 3]);
    assert.deepEqual(sort([1, 2, 3]), [1, 2, 3]);
    assert.deepEqual(sort([7, 7, 7]), [7, 7, 7]);
  });

  test(`${name} does not change its input`, () => {
    const input = [3, 1, 2];
    sort(input);
    assert.deepEqual(input, [3, 1, 2]);
  });

  test(`${name} matches Array.sort on random data`, () => {
    for (let round = 0; round < 20; round++) {
      const data = Array.from({ length: 200 }, () =>
        Math.floor(Math.random() * 100),
      );
      const expected = [...data].sort((a, b) => a - b);
      assert.deepEqual(sort(data), expected);
    }
  });

  test(`${name} accepts a custom comparator`, () => {
    assert.deepEqual(sort([1, 3, 2], (a, b) => b - a), [3, 2, 1]);
  });
}

test("insertion sort and merge sort are stable", () => {
  const people = [
    { name: "A", age: 30 },
    { name: "B", age: 25 },
    { name: "C", age: 30 },
    { name: "D", age: 25 },
  ];
  const byAge = (x: { age: number }, y: { age: number }) => x.age - y.age;
  for (const sort of [insertionSort, mergeSort, bubbleSort]) {
    assert.equal(sort(people, byAge).map((p) => p.name).join(""), "BDAC");
  }
});

test("countingSort", () => {
  assert.deepEqual(countingSort([3, 1, 4, 1, 5, 2, 3], 5), [
    1, 1, 2, 3, 3, 4, 5,
  ]);
  assert.deepEqual(countingSort([], 5), []);
});

test("isSorted", () => {
  assert.equal(isSorted([1, 2, 2, 3]), true);
  assert.equal(isSorted([2, 1]), false);
  assert.equal(isSorted([]), true);
});

បន្ថែម export ទៅ src/index.ts៖

export * from "./sorting.ts";

ដំណើរការ test៖

npx tsx --test

test "matches Array.sort on random data" គឺជាល្បិចដូចគ្នានឹងក្នុងជំពូកមុន។ ទុកចិត្ត function ដែលមានស្រាប់ជា oracle ហើយប្រៀបធៀបជាមួយវាលើ input ចៃដន្យច្រើន។ ដោយសារ quickSort ប្រើ pivot ចៃដន្យ ការរត់វាច្រើនដងក៏ធ្វើឲ្យផ្លូវផ្សេងៗគ្នាជាច្រើនត្រូវបានសាកល្បងដែរ។

11. សាកល្បងដោយខ្លួនឯង

1. ទាយ default។ ដោយមិនរត់វា តើ [5, 25, 100, 1].sort() ត្រឡប់អ្វី? ចុះ ["b", "B", "a", "A"].sort()? បន្ទាប់មករត់ទាំងពីរ ហើយជួសជុលនីមួយៗដោយ comparator។
2. តម្រៀបតាមពីរ key។ ដោយមានបញ្ជី { name, score } តម្រៀបតាម score ពីធំទៅតូច ហើយបំបែកស្មើគ្នាតាម name ពីតូចទៅធំ។ ធ្វើវាដោយ comparator តែមួយប្រើល្បិច || ហើយបន្ទាប់មកម្តងទៀតដោយ stable sort ពីរ (key បន្ទាប់បន្សំមុន)។
3. រាប់ការងារ។ បន្ថែមកម្មវិធីរាប់ទៅ mergeSort និង bubbleSort ដែលរាប់ថា compare ត្រូវបានហៅប៉ុន្មានដង។ សម្រាប់ array នៃលេខចៃដន្យ 1,000 តើនីមួយៗធ្វើការប្រៀបធៀបប៉ុន្មានដង? តើ bubble sort ជិត n² / 2 ប៉ុណ្ណា ហើយ merge sort ជិត n log₂ n ប៉ុណ្ណា?
4. ជួសជុល quick sort សម្រាប់តម្លៃស្ទួន។ សរសេរ partition ឡើងវិញជា three-way partition ដែលដាក់ធាតុជាក្រុម < pivot, === pivot និង > pivot (គ្រោងការណ៍ "Dutch national flag") ហើយ recurse តែលើក្រុមទីមួយ និងក្រុមចុងក្រោយ។ វាស់ពេលវេលាលើលេខដូចគ្នា 50,000 មុន និងក្រោយ។
5. Merge sorted array (ការសម្ភាសន៍)។ ដោយមាន sorted array ពីរ ត្រឡប់ sorted array មួយក្នុង O(n + m)។ បន្ទាប់មកពង្រីក៖ ដោយមាន sorted array k merge ទាំងអស់។ តើ data structure អ្វីធ្វើឲ្យបញ្ជី k ងាយស្រួល? (ជំនួយ៖ វានៅចំងាយពីរបីជំពូក៖ heap។)
6. តម្រៀបពណ៌ (Sort colors) (ការសម្ភាសន៍)។ array មួយមានតែ 0, 1 និង 2។ តម្រៀបវា in place ក្នុង pass តែមួយ និង O(1) ទំហំបន្ថែម ដោយមិនហៅ sort។ ប្រៀបធៀបវាជាមួយ counting sort៖ មួយណាប្រើអង្គចងចាំតិចជាង? នេះពិតជា three-way partition ពីលំហាត់ទី 4។

ការតម្រៀបបំប្លែងទិន្នន័យរញ៉េរញ៉ៃទៅជាអ្វីមួយដែលអ្នកអាចស្វែងរក merge និងដាក់ជាក្រុមក្នុង pass តែមួយ។ ហើយមេរៀនកណ្តាលនៃពីរជំពូកចុងក្រោយគឺថា algorithm ល្អជាងយកឈ្នះកុំព្យូទ័រលឿនជាង។ បន្ទាប់ យើងផ្លាស់ពីបញ្ជីរាបស្មើទៅទិន្នន័យដែលមានរូបរាង។ ក្នុង Tree និង Binary Search Tree យើងជួបរចនាសម្ព័ន្ធនៅពីក្រោយ DOM និង file system ហើយមើលថា tree ផ្តល់ឲ្យយើងនូវការស្វែងរកលឿន និងការបញ្ចូលលឿនក្នុងពេលតែមួយយ៉ាងដូចម្តេច។