Program JavaScript untuk mengisih senarai terpaut 0, 1 dan 2

Dalam tutorial ini, kita akan mempelajari program JavaScript untuk mengisih senarai terpaut 0, 1 dan 2. Algoritma pengisihan adalah penting untuk mana-mana bahasa pengaturcaraan, dan JavaScript tidak terkecuali. Mengisih senarai terpaut 0s, 1s dan 2s ialah masalah biasa yang dihadapi pembangun dalam temu bual pengekodan dan aplikasi dunia sebenar.

Jadi, mari kita mendalami cara mengisih senarai terpaut 0, 1 dan 2 menggunakan pengaturcaraan JavaScript.

Apakah pengisihan?

Isih ialah proses penyusunan elemen dalam susunan tertentu (menaik atau menurun). Ia adalah operasi asas dalam sains komputer dan mempunyai banyak aplikasi dalam senario dunia sebenar. Algoritma pengisihan digunakan untuk menyusun data untuk carian yang cekap, mengurangkan lebihan dan mengoptimumkan kerumitan ruang dan masa.

Berikut ialah beberapa contoh pengisihan dalam JavaScript:

Contoh 1 - Isih susunan nombor dalam tertib menaik:

Input: ar[]= [5, 3, 8, 1, 2, 9]
Output: [1, 2, 3, 5, 8, 9]

Contoh 2 - Isih tatasusunan rentetan mengikut abjad:

Input: ['apple', 'banana', 'orange', 'grape']
Output: ['apple', 'banana', 'grape', 'orange']

Apakah senarai terpaut?

Senarai terpaut ialah struktur data linear yang terdiri daripada nod yang dipaut bersama oleh penunjuk. Setiap nod mengandungi elemen data dan rujukan kepada nod seterusnya dalam senarai. Senarai terpaut sering digunakan dalam struktur data dinamik di mana saiz data sering berubah.

Pernyataan Masalah

Matlamatnya adalah untuk menyusun dan memaparkan senarai terpaut yang terdiri daripada 0, 1 dan 2 mengikut urutan. Mari kita fahami dengan contoh:

Contoh

Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL 
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL
Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL 

Algoritma untuk mengisih senarai terpaut 0, 1 dan 2

Langkah untuk mengisih senarai terpaut 0, 1 dan 2 menggunakan algoritma isihan mengira -

Langkah 1 - Takrifkan senarai isihan(kepala) fungsi yang mengambil sebagai input kepala senarai terpaut.

STEP2 - Mulakan kiraan tatasusunan kiraan[] bersaiz 3, dengan semua elemen sama dengan 0.

LANGKAH 3 - Lintas senarai terpaut dan naikkan kiraan data nod pada indeks yang sepadan dalam tatasusunan kiraan.

LANGKAH 4 - Lintas senarai terpaut sekali lagi dan gantikan data nod dengan nilai indeks terendah dengan kiraan lebih daripada 0.

Langkah 5 - Kurangkan kiraan data nod untuk setiap penggantian.

Langkah 6 - Cetak senarai terpaut sebelum dan selepas mengisih.

Sekarang mari kita cuba memahami algoritma di atas dengan contoh melaksanakannya menggunakan JavaScript.

Contoh

Atur cara JavaScript berikut mengisih senarai terpaut yang mengandungi 0, 1 dan 2 menggunakan algoritma isihan mengira. Algoritma mula-mula mengira kekerapan kejadian 0, 1, dan 2 dalam senarai, dan kemudian mengemas kini nilai nod dalam senarai berdasarkan kiraan setiap nilai.

/* Link list node */
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
   }
   push(new_data) {
      const new_node = new Node(new_data);
      new_node.next = this.head;
      this.head = new_node;
   }
   printList() {
      let currentNode = this.head;
      let value = "";
      while (currentNode !== null) {
         value += currentNode.data + " -> ";
         currentNode = currentNode.next;
      }
      console.log(value + "null");
   }
   sortList() {
      const count = [0, 0, 0]; // Initialize count of '0', '1' and '2' as 0
      let ptr = this.head;
      while (ptr !== null) {
         count[ptr.data] += 1;
         ptr = ptr.next;
      }
      ptr = this.head;
      let i = 0;
      while (ptr !== null) {
         if (count[i] === 0) {
            ++i;
         } else {
            ptr.data = i;
            --count[i];
            ptr = ptr.next;
         }
      }
   }
}
const linkedList = new LinkedList();
linkedList.push(0);
linkedList.push(1);
linkedList.push(0);
linkedList.push(2);
linkedList.push(1);
linkedList.push(1);
linkedList.push(2);
linkedList.push(1);
linkedList.push(2);
console.log("Before sorting:");
linkedList.printList();
linkedList.sortList();
console.log("After sorting:");
linkedList.printList();

Kesimpulan

Secara keseluruhan, program Javascript di atas menunjukkan cara yang cekap untuk mengisih senarai terpaut yang mengandungi hanya 0, 1 dan 2 menggunakan teknik pengiraan. Algoritma ini mempunyai kerumitan masa O(n) dan kerumitan ruang O(1), menjadikannya penyelesaian optimum untuk masalah pengisihan tertentu ini.

Atas ialah kandungan terperinci Program JavaScript untuk mengisih senarai terpaut 0, 1 dan 2. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!