Sparse Array In C++

In this article, we will discuss the sparse array in C++ with its example.

A sparse array represents a data array in which many of the elements contain a value of zero. As a result, in a full array, the majority of the components have non-zero values or are "full" of numbers. In computer data handling, a sparse array may be handled differently from a dense array.

Sparse array properties:

• ✅ A sparse array has most of its entries with the same value (the standard value is zero/Null ).
• ✅ Sparse matrices are arrays in which the majority of the elements are zero.
• ✅ A sparse array is one with no contiguous indexes beginning at zero.
• ✅ When there are fewer non-zero elements, sparse arrays can be used instead of arrays. Sparse arrays use less space to store each component and can save time in computation.

Example:

[[1 0 1],

[0 2 0],

[0 3 0]]

Why a sparse array is preferred over a simple array for storing elements:

Storage: When there are a majority of zero elements and the fewest non-zero elements, we choose a sparse array instead of a simple array since it uses a smaller amount of memory to store all of the elements. Something other than zero elements is stored in the sparse array.

Computation Time: Because we only keep non-zero components in the sparse array, traversing just non-zero components takes less time for computation.

Sparse Array Representation:

There are two ways to express sparse arrays:

• ✅ Linked List Representation
• ✅ Array Representation

1. Representation of an Array:

A sparse array is represented by a 2-D array with three rows: Row, Column, and Value.

Row: The starting position of the row containing non-zero elements.

Column: The number that represents the index of the column containing the non-zero element.

Value: A non-zero value found in the (Row, Columns) index.

2. Representation of Linked Lists:

Each of the nodes in a sparse array is represented by four fields: Row, Column, Value , and Next node .

Row: It is the starting position of the row containing non-zero elements.

Column: The value of the index of the column containing the non-zero element.

Value: A non-zero value found in the (Row, Column) index.

Next Node: It saves a subsequent node's address.

Algorithm

Begin
 1. Define a 2D array of integer datatype arr[10][10].
 Start some array values.
 2. Declare i, j, and count as integer datatypes.
 The count is set to zero at the start.
 3. Declare row and col as integer datatypes.
 Set row to 3 and col to 3.
 3. if (arr[i][j] == 0) count++ for (i = 0; i row; ++i) for (j = 0; j col; ++j) if (arr[i][j] == 0) 
 count++.
 Print "The matrix is:"
 ++i) for (i = 0; i row; ++i) for (j = 0; j col; ++j)
 Display the array's values.
 Text: "The number of zeros in the array is."
 4. If the count exceeds ((row * col)/ 2), then
 print "This represents a sparse matrix."
 else
 print: "This doesn't correspond to a sparse matrix."
End.

Filename: SparseArray.cpp

#include<iostream>
using namespace std;
int main () {
 // the array elements
 int arr[10][10] = { {1, 0, 9} , {3, 0, 0} , {1, 0, 0} };
 int i, j, c = 0;
 int rows = 3, cols = 3;
 for (i = 0; i < rows; ++i) {
 for (j = 0; j < cols; ++j) {
 if (arr[i][j] == 0)
 c++;
 }
 }
 // displaying the array
 cout<<"The given matrix is:"<<endl;
 for (i = 0; i < rows; ++i) {
 for (j = 0; j < cols; ++j) {
 cout<<arr[i][j]<<" ";
 }
 cout<<endl;
 }
 // condition to check whether the given array is sparse or not
 cout<<"The total number of zeros in the given array are "<< c <<endl;
 if (c > ((rows* cols)/ 2))
 cout<<"The given array is a sparse array."<<endl;
 else
 cout<<"Not a sparse array."<<endl;
 return 0;
}

Output:

The given matrix is:
1 0 9 
3 0 0 
1 0 0 
The total number of zeros in the given array are 5
The given array is a sparse array.