Array Data Structure

Array

Array is the most used data structure. Array structure helps us to store data in linear order.In this blogpost we are going to learn about arrays and different operations performed on arrays using various algorithms. We are going to see Row Major and Column Major Matrix, Sparse Matrix and Representation of Sparse Matrix, Different types of Sorting Techniques ,like bubble, Insertion,Merge,Quick sort , Different Searching Techniques like Linear Search and Binary Search. Please take a help of following menu to jump on specific topic

1. Introduction to Arrays
2. Row Major and Column Major
3. Sparse Matrix and Representation of Sparse Matrix
4. Sorting Techniques:- Bubble, Insertion, Merge, Quick
5. Searching Techniques:- Linear search, Binary Search

what is Array

Array is a collection of elements of similar data type. Array is a fixed size sequential collection of elements of same data type that share a common name. An Array is a derived data type. All elements of Array are stored in contiguous memory location.

Array is a linear type of data structure. Syntax of declaring Array:- data type arrayname[size];

This is called a single-dimensional array. The arraySize must be an integer constant greater than zero and type can be any valid C data type. For example, to declare a 5-element array of integer type we declare. int a[5]; There are 5 elements of similar data type (integer) stored sequentially.

Types of Arrays

There are basically two types of Arrays:-

• One dimensional Array
• Two dimensional Array

One Dimensional Arrays : A one-dimensional array is one in which only one subscript specification is needed to specify a particular element of the array. A one-dimensional array is a list of related variables. Such lists are common in programming. int a[5] Initializing One-Dimensional Array int a[5] ={2,3,4,5,6};

Accessing array elements

An element is accessed by indexing the array name. This is done by placing the index of the element within square brackets after the name of the array. For example − int a[0] It will help to access first index element in the array. int a[1]:- It will help to access second index element in the array.

We use for loop to access the elements of array For accepting as well as for displaying the elements of array we use a for loop.

C program to accept element and display array

//Program to accept element and display array #include <stdio.h> main () { int a[ 10 ]; /* a is an array of 10 integers */ int i; for ( i = 0; i < 10; i++ ) { printf(“enter the elements”); scanf(“%d”, &a[i]); } for (i = 0; i < 10; i++ ) { printf("Element is %d”, a[i] ); } }

simple program to find max element in the Array.

//Simple Program to find Maximum element from Array <code>#include <stdio.h> main () { int a[ 10 ],max=a[0],i; for ( i = 0; i < 10; i++ ) { printf(“enter the elements”); scanf(“%d”, &a[i]); } for (i = 1; i < 10; i++ ) { if(a[i]>max) max=a[i]; } printf(“Maximum Element of Array is %d”, max ); }</code>

Two dimensional arrays

Two dimensional arrays are also called table or matrix, two dimensional arrays have two subscripts.

Two dimensional array in which elements are stored column by column is called as column major matrix.

Two dimensional array in which elements are stored row by row is called as row major matrix.

First subscript denotes number of rows and second subscript denotes the number of columns. The simplest form of the Multi Dimensionl Array is the Two Dimensionl Array. A Multi Dimensionl Array is essence a list of One Dimensionl Arrays.

Syntax of declaring 2d array

int a[2][2]; This syntax declares a 2d array having 2 rows and 2 columns i.e.:- 2*2 matrix. Initializing Two-Dimensional Array int a[2][2]= {1,2,3,4};

Simple program to accept two dimensional Matrix and displaying

#include<stdio.h> main() { int a[3][3],i,j; for(i=0;i<3;i++) { for(j=0;j<3;j++) { scanf(“%d”,&a[i][j]); } } for(i=0;i<3;i++) { for(j=0;j<3;j++) { printf(“%d”,a[i][j]); } } }

Array represention

Array can be represented in two ways:-

• Row – major
• Column major

They describe the methods of representing arrays in memory

For example Consider a matrix : 11 12 13 14

Row major matrix

In this method the elements are stored row wise, i.e. n elements of first row are stored in first n locations, n elements of second row are stored in next n locations and so on.

E.g.:- A 2 x 2 array will stored as below:

11	22
33	44

11

Element	Subscript
a[0][0]

a[0][1] 22 a[1][0] 33 a[1][1] 44

Column major matrix

In this method the elements are stored column wise, i.e. m elements of first column are stored in first m locations, m elements of second column are stored in next m locations and so on.

E.g.:- A 2 * 2 array will stored as below:

11	22
33	44

a[0][1]

Element	Subscript
11	a[0][0]
33	a[1][0]
22

44 a[1][1]

Sparse Matrix

In computer programming, a matrix can be defined with a 2-dimensional array. Any array with 'm' columns and 'n' rows represent a m X n matrix.

There may be a situation in which a matrix contains more number of ZERO values than NON-ZERO values. Such matrix is known as sparse matrix.

When a sparse matrix is represented with a 2-dimensional array, we waste a lot of space to represent that matrix.

Representation of sparse Matrix A sparse matrix can be represented by using TWO representations, those are as follows…

• Triplet Representation (Array Representation)
• Linked Representation.

Triplet represention
Triplet Representation (Array Representation) In this representation, we consider only non-zero values along with their row and column index values. In this representation, the 0th row stores the total number of rows, total number of columns and the total number of non-zero values in the sparse matrix.

For example, consider a matrix of size 5 X 6 containing 6 number of non-zero values.

Linked represention In linked representation, we use a linked list data structure to represent a sparse matrix. In this linked list, we use two different nodes namely header node and element node. Header node consists of three fields and element node consists of five fields.

Sorting Techniques

Sorting is a process of ordering or placing a list of elements from a collection in some kind of order. It is nothing but storage of data in sorted order.

Sorting can be done in ascending and descending order. It arranges the data in a sequence which makes searching easier.

Techniques used for sorting

• Bubble Sort
• Insertion Sort
• Merge Sort
• Quick Sort

Techniques used for Searching

• Linear Search
• Binary Search

Linear Search Algorithm

Searching is a process of finding a particular element among several given elements. The search is successful if the required element is found. Otherwise, the search is unsuccessful.

Algorithm for Linear Search

• Step1.Traverse the array using a for loop.
• Step 2.In every iteration, compare the target value with the current value of the array.
• Step 3. If the values matches, then return the current index of the array.
• Step 4.If the values do not match, move on to the next array element.
• Step 5. If after traversing entire array no match is found, return -1.

Stepwise Algorithm for Linear Search

• Step 1:- Accept n which represents number of elements in the array.
• Step 2:- Accept Array element by element using a for loop.
• Step 3:- Accept element to be searched from user.
• Step 4:-Traverse the array from the beginning using for loop.
• Step 4:- Check if the element to be searched is equal to the array element.
• Step 5:- If found display the position of the array element and stop searching.
• Step 6:- If not found display the message element not found.

Program for linear Search

#include<stdio.h> main() { int a[10],n, i, x; printf("enter the value of n"); scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d", &a[i]); } printf("enter element to search"); scanf("%d",&x); for(i=0;i<n;i++) { if(a[i]==x) printf("element found at %d",i); break; } printf("element not found"); }

Binary Search

It is a technique of searching an element in array. The main requirement is the array should be in sorted order. Linear search can be applied to both sorted as well as unsorted array but binary search can be applied only to sorted array.

A binary search is an advanced type of search algorithm that finds and fetches data from a sorted list of items. It works on the principle of divide and conquer.

Binary Search Algorithm

Accept array of n elements (The array should be in sorted order) Accept element to be searched Initialize low=0 high=n and find the mid value by using low + high/2 If the value to be searched is equal to the middle element of the array, then return the index of the middle element.

If not, then compare the middle element with the target value, If the target value is greater than the number in the middle index, then search in the rightmost part of the middle element and start with Step 3.where low=mid+1 and high=n If the target value is less than the number in the middle index, then search in the leftmost part of the middle element , and start with Step 3. where low=0 and high=mid-1 When a match is found, return the index of the element matched. If no match is found, then return -1

Example of binary Search There are 3 cases when we need to search a element in array by Binary search method. Case 1:- if element to be searched is 32 then the following procedure is applied for search. Low =0 high=n which is 3 i.e.:- no of elements in the array =4 Mid=low + high/2 0+3/2=3/2= 1 So mid element is second element which is 32. Therefore the element is found.

Case 2:- If element to be found is 12 Low =0 high=n =3 i.e.:- no of elements in the array =4 Mid=low + high/2 0+3/2=3/2= 1 compare 12 with 32 we see that 12<32 at="" find="" leftmost="" need="" p="" side.="" so="" to="" we="">

As we need to search element 12 which is less than the mid value so it will be searched at leftmost part. Now low =0 and high = 1 mid= 0+1/2= ½= 0 Compare the first element with the element to be searched 12 =12 therefore element searched.

Case 3:- If element to be found is 51 Low =1 high=n i.e.:- no of elements in the array =4 Mid=low + high/2 0+3/2=3/2= 1 In this case 65>32 therefore the element will be found at rightmost part of mid element. Now low=2 high=3 mid= 2+3/2 =2 mid =2 Compare 51 with the element at second position i.e.:- 51 with 51 search is successful.

Algorithm for binary Search

Binary search is implemented using following steps…

• Step 1 - Read the search element from the user.
• Step 2 - Find the middle element in the sorted list.
• Step 3 - Compare the search element with the middle element in the sorted list.
• Step 4 - If both are matched, then display "Given element is found!!!" and terminate the function.
• Step 5 - If both are not matched, then check whether the search element is smaller or larger than the middle element.
• Step 6 - If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left sublist of the middle element.
• Step 7 - If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right sublist of the middle element.
• Step 8 - Repeat the same process until we find the search element in the list or until sublist contains only one element.
• Step 9 - If that element also doesn't match with the search element, then display "Element is not found in the list!!!" and terminate the function.

Binary search

int binary(int arr[],int x, int start, int end) { mid=(low+high)/2; if(arr[mid]==x) {return mid;} if(low==high) {return -1;} if(x<arr[mid]) { return binary(arr,x,start,mid-1); } if(x>arr[mid]) { return binary(arr,x,mid+1,end); } }

Sorting Techniques

Sorting is a process of ordering or placing a list of elements from a collection in some kind of order. It is nothing but storage of data in sorted order.

Sorting can be done in ascending and descending order. It arranges the data in a sequence which makes searching easier.

Techniques used for Sorting

Sorting is a process of ordering or placing a list of elements from a collection in some kind of order. It is nothing but storage of data in sorted order.

Sorting can be done in ascending and descending order. It arranges the data in a sequence which makes searching easier.

Bubble sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements.

Bubble sort algorithm

• Step 1:- Accept array having n elements
• Step 2:- Display original array
• Step 3:- Compare the first element with its next adjacent elements till the end of the array
• Step 4:- if first element is greater than the adjacent element then swap. Otherwise keep it as it is.
• Step 5:- After first iteration we find that the first largest element of the array has got its correct position.
• Step 6: Repeat Step 3 and Step 4 till all elements get their exact position.

Insertion sort

This is an in-place comparison-based sorting algorithm. Insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its correct position i.e, the position to which it belongs in a sorted array.

It iterates the input elements by growing the sorted array at each iteration. It compares the current element with the largest value in the sorted array. If the current element is greater, then it leaves the element in its place and moves on to the next element else it finds its correct position in the sorted array and moves it to that position.

This is done by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted.

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hand. It build the final sorting array one item at a time.

Working of insertion sort

• Step 1:- Consider the first element of given array in sorted sub-list and remaining elements in Unsorted sub-list.
• Step 2:- Compare the first element of Unsorted Sub list one by one with all elements of sorted sublist in reverse order.
• Step 3:- While Comparing if element of Sorted sub list is greater than the element selected from Unsorted Sub list then move the element from Sorted sublist which is greater one position to the right side. Continue the step till all elements of Sorted sub list Comparison is over.
• Step 4:- Place the element selected from Unsorted sublist in its proper position. Step 5:- At every step Sorted sublist element will increase by 1 and Unsorted sublist element will decrease by 1.

Merge Sort Algorithm

Merge Sort algorithm is based on Recursion concept Merge sort is based on divide and conquer technique. Problem is divided into sub problems. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. Merge sort is one of the most efficient sorting algorithms Merge sort first divides the array into equal halves and then combines them in a sorted manner. Merge sort repeatedly breaks down a list into several sublists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list. If array has even number of elements then it divides the array into exact two halves i.e.:- if there are 8 elements then we will have two sub arrays containing 4 elements each.

Using the Divide and Conquer technique, we divide a problem into subproblems. When the solution to each subproblem is ready, we 'combine' the results from the subproblems to solve the main problem.

Divide:- We go on dividing the array till only one element remains in the array.

Conquer:-In the conquer step, we try to sort sub arrays.

Combine When the conquer step reaches the base step and we get two sorted sub arrays for we combine the results.

Merge Sort logic

if(low<high) { mid=(low+high)/2; mergesort(a,low,mid); mergesort(a,mid+1,high); merge(a,low,mid,high); } i=low; j=mid+1; k=0; while ((i<=mid) && (j<=high)) { if (a[i]<=a[j]) b[k++]=a[i++]; else b[k++]=a[j++]; } while (i<=mid) { b[k++]=a[i++]; } while (j<=high) { b[k++]=a[j++]; } //copy merged element from b to a for(j=low,k=0;j<=high;j++,k++) { a[j]=b[k]; }

Quick Sort

Like Merge Sort, Quick sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of Quick sort that pick pivot in different ways.

Always pick first element as pivot. Always pick last element as pivot Pick a random element as pivot. Pick median as pivot.

Quick Sort Algorithm

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays.

A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. On the basis of Divide and Conquer, quicksort algorithm can be explained as

Divide The array is divided into subparts taking pivot as the partitioning point. The elements smaller than the pivot are placed to the left of the pivot and the elements greater than the pivot are placed to the right.

Conquer The left and the right subparts are again partitioned using the procedure by selecting pivot elements for them. This can be achieved recursively passing the subparts into the algorithm.

Combine This step does not play a significant role in quicksort. The array is already sorted at the end of the conquer step.

Read Also

1. What is Data structure
2. What is Stack Data structure
3. Linked list
4. What is Struct in C
5. Graph Data Structure in C
6. Tree Data Structure, Learn Binary tree,Binary Search tree and Binary search tree algorithem.
7. What is the pointer in C|what is value at(*ptr) operator