In this guide, we will explore the concept of a sparse array in C++ along with an illustrative example.
A sparse array is a type of data array where a large number of elements have a value of zero. Conversely, a dense array contains mostly non-zero values or is considered "full" of numbers. When it comes to computer data processing, handling a sparse array may involve different techniques compared to 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:
When a significant number of elements are zeros and there are limited non-zero elements, opting for a sparse array over a dense array is more efficient in terms of memory utilization. The sparse array stores elements that are not zero.
Computation Time: By retaining only non-zero elements in the sparse array, the process of traversing solely these non-zero elements reduces the computation time significantly.
Sparse Array Representation:
There are two ways to express sparse arrays:
- Linked List Representation
- Array Representation
- Representation of an Array:
A sparse array is illustrated using a two-dimensional array containing three rows: Row, Column, and Value.
The initial index of the row that holds elements with values other than zero.
Column: The numerical value indicating the position of the column where the non-zero element is located.
Value: A value that is not zero discovered at the (Row, Columns) position.
2. Representation of Linked Lists:
Each node within a sparse array is defined by four attributes: Row, Column, Value, and the Next node pointer.
Row: It marks the initial position of the row that holds elements with values other than zero.
Column: The index value of the column that holds the non-zero element.
Value: An integer value discovered at the (Row, Column) position.
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.
