What is meant by Sparse Array?
A sparse array or sparse matrix is an array in which most of the elements are zero.
Characteristics of Sparse array:
- The sparse array is an array in which most of the elements have the same value(the default value is zero or null).
- Sparse matrices are those array that has the majority of their elements equal to zero.
- A sparse array is an array in which elements do not have contiguous indexes starting at zero.
- Sparse arrays are used over arrays when there are lesser non-zero elements. Sparse arrays require lesser memory to store the elements and the computation time can be saved.
Examples of Sparse array:
Why sparse array is required over simple arrays to store the elements:
- Storage: When there is the maximum number of zero elements and the minimum number of non-zero elements then we use a sparse array over a simple array as it requires less memory to store the elements. In the sparse array, we only store the non-zero elements.
- Computation Time: In the sparse array we only store non-zero elements and hence, traversing only non-zero elements takes less computation time.
Representation of Sparse Array:
Sparse arrays can be represented in two ways:
- Array Representation
- Linked List Representation
1. Array Representation:
To represent a sparse array 2-D array is used with three rows namely: Row, Column, and Value.
Row: Index of the row where non-zero elements are present.
Column: Index of the column where the non-zero element is present.
Value: The non-zero value which is present in (Row, Column) index.
2. Linked List Representation:
To represent a sparse array using linked lists, each node has four fields namely: Row, Column, Value, and Next node.
Row: Index of the row where non-zero elements are present.
Column: Index of the column where the non-zero element is present.
Value: The non-zero value which is present in (Row, Column) index.
Next node: It stores the address of the next node.
Implementation of array representation of the sparse array:
Below is the representation of the sparse array:
C++
// 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; } |
Java
/*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. |
Python3
# Implementation of array representation # of the sparse array sparse = [[ 0 , 0 , 7 , 0 ], [ 1 , 0 , 0 , 0 ], [ 2 , 0 , 5 , 0 ], [ 0 , 8 , 0 , 4 ]] s = 0 for i in range ( 4 ): for j in range ( 4 ): if (sparse[i][j] ! = 0 ): s + = 1 representsparse = [[ 0 for i in range (s)] for i in range ( 3 )] k = 0 for i in range ( 4 ): for j in range ( 4 ): if (sparse[i][j] ! = 0 ): representsparse[ 0 ][k] = i representsparse[ 1 ][k] = j representsparse[ 2 ][k] = sparse[i][j] k + = 1 print ( "Representation of Sparse array using arrays : " ) for i in range ( 3 ): for j in range (s): print (representsparse[i][j], end = " " ) print ("") # This code is contributed by saurabh_jaiswal. |
C#
using System; public class GFG{ static public void Main (){ // initializing sparse array 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++; } } } for ( int i = 0; i < 3; i++) { for ( int j = 0; j < s; j++){ Console.Write(representsparse[i,j]+ " " ); } Console.WriteLine(); } }} |
Javascript
<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> |
Output
Representation of Sparse array using arrays : 0 1 2 2 3 3 2 0 0 2 1 3 7 1 2 5 8 4
Contact Us