¿Qué se entiende por array dispersa?

Una array dispersa o array dispersa es una array en la que la mayoría de los elementos son cero.

Características de la array dispersa:

• La array dispersa es una array en la que la mayoría de los elementos tienen el mismo valor (el valor predeterminado es cero o nulo).
• Las arrays dispersas son aquellas arrays que tienen la mayoría de sus elementos iguales a cero.
• Una array dispersa es una array en la que los elementos no tienen índices contiguos que comiencen en cero.
• Las arrays dispersas se utilizan sobre arrays cuando hay elementos menores distintos de cero. Las arrays dispersas requieren menos memoria para almacenar los elementos y se puede ahorrar tiempo de cálculo. 

Ejemplos de array dispersa:

Por qué se requiere una array dispersa en lugar de arrays simples para almacenar los elementos:

• Almacenamiento: cuando existe la cantidad máxima de elementos cero y la cantidad mínima de elementos distintos de cero, usamos una array dispersa en lugar de una array simple, ya que requiere menos memoria para almacenar los elementos. En la array dispersa, solo almacenamos los elementos distintos de cero. 
• Tiempo de cálculo: en la array dispersa solo almacenamos elementos distintos de cero y, por lo tanto, atravesar solo elementos distintos de cero requiere menos tiempo de cálculo.

Representación de array dispersa:

Las arrays dispersas se pueden representar de dos maneras:

• Representación de arrays
• Representación de lista enlazada

1. Representación de array:

Para representar una array dispersa, se utiliza una array 2-D con tres filas, a saber: Fila, Columna y Valor.

Fila: índice de la fila donde están presentes los elementos distintos de cero.
Columna: índice de la columna donde está presente el elemento distinto de cero.
Valor: El valor distinto de cero que está presente en el índice (Fila, Columna).

Representación de array de array dispersa

2. Representación de lista enlazada:

Para representar una array dispersa mediante listas vinculadas, cada Node tiene cuatro campos, a saber: Fila, Columna, Valor y Siguiente Node.

Fila: índice de la fila donde están presentes los elementos distintos de cero.
Columna: índice de la columna donde está presente el elemento distinto de cero.
Valor: El valor distinto de cero que está presente en el índice (Fila, Columna).
Siguiente Node: Almacena la dirección del siguiente Node.

Representación de lista enlazada de array dispersa

Implementación de la representación de array de la array dispersa:

Implementación de la representación de array de la array dispersa

A continuación se muestra la representación de la array dispersa:

// Implementation of array representation
// of the sparse array
#include <iostream>
using namespace std;
 
int main()
{
    int sparse[4][4] = { { 0, 0, 7, 0 },
                         { 1, 0, 0, 0 },
                         { 2, 0, 5, 0 },
                         { 0, 8, 0, 4 } };
    int s = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            if (sparse[i][j] != 0)
                s++;
    int representsparse[3][s];
    int k = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            if (sparse[i][j] != 0) {
                representsparse[0][k] = i;
                representsparse[1][k] = j;
                representsparse[2][k] = sparse[i][j];
                k++;
            }
    cout << "Representation of Sparse array using arrays : "
            "\n";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < s; j++)
            cout << " " << representsparse[i][j];
        cout << "\n";
    }
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
  public static void main(String[] args)
  {
    int[][] sparse = { { 0, 0, 7, 0 },
                      { 1, 0, 0, 0 },
                      { 2, 0, 5, 0 },
                      { 0, 8, 0, 4 } };
    int s = 0;
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++)
        if (sparse[i][j] != 0)
          s++;
    int[][] representsparse = new int[3][s];
    int k = 0;
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++)
        if (sparse[i][j] != 0) {
          representsparse[0][k] = i;
          representsparse[1][k] = j;
          representsparse[2][k] = sparse[i][j];
          k++;
        }
    System.out.print(
      "Representation of Sparse array using arrays : ");
    System.out.println();
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < s; j++)
        System.out.print(" "
                         + representsparse[i][j]);
      System.out.println();
    }
  }
}
 
// This code is contributed by lokeshpotta20.

<script>
// Implementation of array representation
// of the sparse array
 
 
    let sparse =[[ 0, 0, 7, 0 ],
                         [ 1, 0, 0, 0 ],
                         [ 2, 0, 5, 0 ],
                         [ 0, 8, 0, 4 ] ];
    let s = 0;
    for (let i = 0; i < 4; i++)
        for (let j = 0; j < 4; j++)
            if (sparse[i][j] != 0)
                s++;
    let representsparse[3][s];
    let k = 0;
    for (let i = 0; i < 4; i++)
        for (let j = 0; j < 4; j++)
            if (sparse[i][j] != 0) {
                representsparse[0][k] = i;
                representsparse[1][k] = j;
                representsparse[2][k] = sparse[i][j];
                k++;
            }
    document.write("Representation of Sparse array using arrays : ");
            "\n";
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < s; j++)
           document.write(" " + representsparse[i][j]);
        document.write("\n");
    }
    </script>

Representation of Sparse array using arrays : 
 0 1 2 2 3 3
 2 0 0 2 1 3
 7 1 2 5 8 4