Arrays-Programs

• Linear Arrays
  
  • Memory representation/address calculation
  • Operations
    • Traversal
    • Search
      • Linear
      • Binary
    • Insertion
      • Insertion at a position
      • Sorted Insertion
    • Deletion
      • Deletion from a position
      • Sorted deletion

Linear Arrays:

An array is a set of homogenous elements (of the same type) referenced under one name along with the subscript.  The subscript is the index or the position that contains the element.  In ‘C’, the subscript value begins with zero.  Arrays may be one-dimensional, two-dimensional or multi-dimensional.  Generally one-dimensional and two-dimensional arrays are used to represent real world entities for solving problems pertaining to a given domain.  A one dimensional array is declared in “C” as follows:

int arr[10];

The above declaration declares an integer array of 10 integers referred to by the name arr.  Similarly two dimensional arrays may be declared:

int arr[5][6];

The above declaration declares a two dimensional array, arr of 5 rows and 6 columns.  Total integers that may be stored in the above array are 5 x 6 = 30.  An array may be represented as an Abstract Data Type.

The address of the first element of the array is called its base address.  Arrays are by default passed to functions by reference using this base address.  Once the base address is available, remaining elements of the array may be accessed by manipulating the subscript identifier.  In ‘C’, arr[i] is equivalent to writing *(arr+i), which refers to the i^th element of the array.  Two dimensional arrays may be represented using row-major form, in which all the elements of the same rows are scanned first or in column-major form in which all the elements of the same column are scanned first beginning from the first column.  We can perform various operations on arrays which will be explained in separate posts with relevant ‘C’ program.

Program to perform Linear Search:

Linear Search:

Linear search involves searching the element from a given set of elements beginning from the first element upto the last element or upto its first occurrence if it is available in the given set.  The efficiency of Linear Search is O(n).  The program to perform linear search is given below:

/* Linear Search */
#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX],n,i,num,val;
printf(“\nEnter total numbers?”);
scanf(“%d”,&n);
for(i=0;i<n;i++){
printf(“\nEnter number?”);
scanf(“%d”,&arr[i]);
}
printf(“\nEnter the value to search?”);
scanf(“%d”,&val);
for(i=0;i<n;i++){
if(arr[i]==val){
printf(“\nNumber found.”);
return;
}
}
printf(“\nNumber not found.”);
}

Program to perform Binary Search:

Binary Search:

Binary Search involves reducing the search range to half by dividing the range into half of its original size.  Binary Search operates upon sorted array.  It compares the element at the mid of this range with the value to be searched, if the value is smaller than the mid value, then the value is looked up in the range from first element to mid, otherwise the new search range becomes mid to last element.  This process continues until the required element is located or lower bound becomes greater than upper bound.  Efficiency of Binary Search is O(log2n) in average and worst case and is O(1) in best case.  The ‘C’ program to perform Binary Search is given below:

/* Binary Search */
#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX],i,n,val;
int lb,ub,mid;
printf(“\nEnter total numbers?”);
scanf(“%d”,&n);
for(i=0;i<n;i++){
printf(“\nEnter number?”);
scanf(“%d”,&arr[i]);
}
printf(“\nEnter the value to search?”);
scanf(“%d”,&val);
lb=0;ub=n-1;
while(lb<=ub){
mid=(lb+ub)/2;
if(val<arr[mid])
ub = mid-1;
else if(val>arr[mid])
lb = mid+1;
else {
printf(“\nNumber found…!”);
return;
}
}
printf(“\nNumber not found…!”);
}

Program to insert a value in an array at a given position:

Insert a value at a given position in an array:

For inserting a value at a given position, the elements are shifted from the last element by one position to the right, and the element at the specified position is overwritten with the new value to be inserted.

/* Insertion at a position in an array */

#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX],n,i,pos,val;
printf(“\nEnter total numbers?”);
scanf(“%d”,&n);
for(i=0;i<n;i++){
printf(“\nEnter number?”);
scanf(“%d”,&arr[i]);
}
printf(“\nEnter the value to insert?”);
scanf(“%d”,&val);
printf(“\nEnter the position where to insert?”);
scanf(“%d”,&pos);
for(i=n-1;i>=pos;i–)
arr[i+1] = arr[i];
arr[pos] = val;
printf(“\nArray elements after insertion:”);
for(i=0;i<n+1;i++)
printf(“%d\t”,arr[i]);
}

Program to insert a value in an array such that array remains sorted:

Sorted insertion in an Array:

Whenever a new value is inserted, appropriate place is located to insert this value.  After locating that place, shifting of elements is required from that position to the last element by one position to the right.  Then the located position may be assigned the new element to be inserted.  The ‘C’ program for the same is given below:

/* Program for sorted insertion */
#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX]={0},n,i,j,k,num,ct=0;
printf(“\nEnter total numbers?”);
scanf(“%d”,&n);
for(i=0;i<n;i++){
printf(“\nEnter number to insert?”);
scanf(“%d”,&num);
for(j=0;j<ct && arr[j]<=num;j++);
for(k=n-1;k>=j;k–)
arr[k+1] = arr[k];
arr[j] = num;
ct++;
}
printf(“\nArray elements are: “);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
}

Program to delete a value from a given array from a given position:

Deletion from a position in an array:

Deletion of a value is straightforward, since the elements from the given position are overwritten with the subsequent elements upto the last element, last element is initialized with zero and variable n indicating total number of elements is decremented by one.

/* Deletion from a position */

#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX],i,n,pos;
printf(“\nEnter total numbers?”);
scanf(“%d”,&n);
for(i=0;i<n;i++){
printf(“\nEnter number?”);
scanf(“%d”,&arr[i]);
}
printf(“\nEnter the position from where to delete element?”);
scanf(“%d”,&pos);
for(i=pos;i<n;i++)
arr[i] = arr[i+1];
arr[i] = 0;
n–;
printf(“\nArray elements after deletion:”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
}

Program to delete a value from a given array such that array remains sorted:

Sorted Deletion in an Array:

Deletion is same as in previous post with the only difference that if the given array is sorted, then the deletion automatically will result in a sorted array.

/* Sorted Deletion */

#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX],n,i,num;
printf(“\nEnter total numbers?”);
scanf(“%d”,&n);
for(i=0;i<n;i++){
printf(“\nEnter number?”);
scanf(“%d”,&arr[i]);
}
printf(“\nEnter the number to delete?”);
scanf(“%d”,&num);
for(i=0;i<n;i++){
if(arr[i] == num)
break;
}
if(i == n){
printf(“\nNumber not found”);
return;
}
for(;i<n;i++)
arr[i] = arr[i+1];
printf(“\nArray after deletion:”);
for(i=0;i<n-1;i++)
printf(“%d\t”,arr[i]);
}

Array Representation – Column-major & Row-major:

Array Representation:

• Column-major
• Row-major

Arrays may be represented in Row-major form or Column-major form.  In Row-major form, all the elements of the first row are printed, then the elements of the second row and so on upto the last row.  In Column-major form, all the elements of the first column are printed, then the elements of the second column and so on upto the last column.  The ‘C’ program to input an array of order m x n and print the array contents in row major and column major is given below.  The following array elements may be entered during run time to test this program:

Input:     Rows: 3;  Columns: 3;

1     2     3

4     5     6

7     8     9

Output:

Row Major:

1     2     3

4     5     6

7     8     9

Column Major:

1     4     7

2     5     8

3     6     9

/* Program to input an array and display in row-major and column major form */

#include <stdio.h>

#define MAX 10

int main(){
int arr[MAX][MAX],m,n,i,j;
printf(“\nEnter total number of rows?”);
scanf(“%d”,&m);
printf(“\nEnter total number of columns?”);
scanf(“%d”,&n);
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf(“\nEnter number?”);
scanf(“%d”,&arr[i][j]);
}
}
printf(“\n\nRow-Major Order:\n”);
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf(“%d\t”,arr[i][j]);
}
printf(“\n”);
}
printf(“\n\nColumn-Major Order:\n”);
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf(“%d\t”,arr[j][i]);
}
printf(“\n”);
}
}