ARRAYS

Unit :-2

ARRAYS

Definition of Array:

Array is a collection of items of the same variable type that are stored at contiguous memory locations.

The collection of homogeneous elements which has same data type and same name.

Properties of an Array:

1. All elements of an array must be of same data type.

2. Each element of an array is referred to be specifying the array name followed by one or more

subscript.

3. Each subscript must be expressed as a positive integer.

4. The subscript will begin with the number 0.

5. Array elements are always stored in sequential memory locations.

Advantages of Arrays:

1.          Efficient and Fast Access: Arrays allow direct and efficient access to any element in the collection with constant access time, as the data is stored in contiguous memory locations.

2.          Memory Efficiency: Arrays store elements in contiguous memory, allowing efficient allocation in a single block and reducing memory fragmentation.

3.          Versatility: Arrays can be used to store a wide range of data types, including integers, floating-point numbers, characters, and even complex data structures such as objects and pointers.

4.          Compatibility with hardware: The array data structure is compatible with most hardware

architectures, making it a versatile tool for programming in a wide range of environments.

Disadvantages:

1.          Fixed Size: Arrays have a fixed size set at creation. Expanding an array requires creating a new one and copying elements, which is time-consuming and memory-intensive.

2.          Memory Allocation Issues: Allocating large arrays can cause memory exhaustion, leading to crashes, especially on systems with limited resources.

3.          Insertion and Deletion Challenges: Adding or removing elements requires shifting subsequent elements, making these operations inefficient.

4.          Limited Data Type Support: Arrays support only elements of the same type, limiting their use with complex data type

5.          Lack of Flexibility: Fixed size and limited type support make arrays less adaptable than structures like linked lists or trees.

Types of Arrays :

Arrays can be classified as follows

1. One–Dimensional Array / 1-D Array

2. Two–Dimensional Array / 2-D Array

3. Multidimensional Array

1. One-Dimensional Array / 1-D Array:

It is a collection of homogeneous elements and same data type and same name, and with only one subscript is called as one-dimensional array.

Syntax or the general form or the declaration of one-dimensional array is To declare an array,

1. Here data type declares the type of elements to be stored in the array such as int, float, char,….

2. Array name is the name of the array

3. Size specifies maximum number of elements that can be stored in the array.

datatype arrayname[size];

Where

1. Datatype can be int, float, double, char etc.

2. array_ name should be a valid variable name.

3. size is an integer value.

4. Size of an array must not be in negative value.

 Array Size

End of the Statement

Declaration of an Array

Datatype Array Name

list[0] list[1] list[2] list[3] list[4]

Initialization of Array:

int arr[5]={10,20,30,40,50};

Pictorial Explanation:

2. Two-Dimensional Array

The two-dimensional array can be defined as an array of arrays.

The 2D array is organized as matrices which can be represented as the collection of rows and columns.

However, 2D arrays are created to implement a relational database looks like data structure.

It provides ease of holding the bulk of data at once which can be passed to any number of functions wherever required.

Declaring of Two-Dimensional Array :

The syntax to declare the 2D array is given below.

data_type array_name[rows][columns];

Consider the following example

Initialization of 2-D Array :

There are two ways to initialize a two-dimensional array during declaration.

int disp[2][4]={

{10,11,12,13}

{14,15,16,17}

};

(Or)

int disp[2][4]={10,11,12,13,14,15,16,17}

Rows, Columns	a[0]	a[1]	a[2]	a[3]
a[0]	10	11	12	13
a[1]	14	15	16	17

 

3. Multi-Dimensional Array

Collection of homogeneous elements which has same datatype and same name with more than two subscripts is called as Multi-Dimensional Array.

Syntax: datatype arrayname[size][size][size];

Operations of arrays :

There are six types of operations of arrays:

1. Traversal: processing each element in the array or to visit the element stored in it. Traversing an array means going through each element of an array exactly once is called as traversal.

2. Searching: Finding the location of the element with a given value in the array or the search operation is used to find a particular data item or element in an array is called searching.

3. Insertion: Adding a new element into an array. Based on the requirement, a new element can be added at the beginning, end or any given index of array is called insertion.

4. Deletion: Removing an element from an array is called deletion.

5. Sorting: Arranging the element in some type of order or the processing of arranging the data in ascending or descending order. There are several types of sorting in data structures namely- bubble sort, insertion sort, selection sort, merge sort, quick sort etc.

6. Merging: Combining of two arrays into single array or when two or more arrays are merged to form a bigger array containing all the items of the merged arrays is called merging.

Abstract Data Type (ADT):

An abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. And this is organized in such a way that the specification of the values and operations on those values are separated from the representation of the values and the implementation of the operations.in simple terms, an abstract data type is a data type with associated operations, but whose representation is hidden.

Arrays as ADT:

1. An array is the fixed size sequence of element of an same type.

2. An array is the fundamental abstract datatype.

3. The basic operating includes direct access to each element in the array by specifying its position, so that values can be retrieved or stored in that position.

4. The most important operation of ADT is setting the value in a particular index and getting a value from a particular index.

Linear Array:

A linear array is a list of finite number n of homogeneous data element:

The element of the array are referenced respectively by an index set consisting of n consecutive numbers.

The elements of the array are stored respectively in successive memory locations

The number of elements is called the length or size of the array.

Length=UB-LB+1.

UB - Upper Bound(Largest Index)

LB -Lower Bound(Smallest Index)

Calculating the length of an array:

Example:If an array has 10,20,30,40,50,60. stored in locations 0,1,2,3,4,5 the

UB=5 and LB=0

The length of an array is (L) = 6.

Representation of Linear array in memory:

Let LA be a linear array in memory of the computer.

LOC(LA[K]=address of the element LA[K] of the array LA

 

. . . .

1000

1001

1002

1003

 

 

 

 

 

Computer Memory Cell

The computer does not need to keep track of the address of every element of LA, but needs to keep track only of the address of the element of LA, denoted by Base(LA) and called base address of LA.Using this address Base(LA), the computer calculates the address of any LA by the following formula:

LOC(LA[K]) = Base(LA)+W(K-LB)

Where Winumber of words per memory cell for the array LA.

Example 1: Consider an array of size 5,A[5].suppose that is stored at this storage address 200 to

wpm,find the address of a[3]?

W=2, K=3, LB=0.

LOC(LA[K]) =200 + 2(3-0)

=200+2(3)

LOC(LA[K]) =206.

Example 2: Suppose if a String S is used to store a String a, b, c, d, e with a starting address as

1000 find the address of 4th element?

Base=1000, W=1, K=3,LB=0.

LOC(LA[K]) = 1000+1(3-0)

=1000+3

=10003.

 

Inserting an element in to Array:

Adding a new element in to an array is called as Insertion of array.

Algorithm:

1. Set I=N

2. Repeat while (I>=LOC)

3. Set (A(I+1)=A(I)

4. Set I=I-1

5. Set A[LOC]=ITEM

6. Set N=N+1

7. EXIT

Delete an element from array:

The process of removing or deleting an element from an array is called as Deletion of Array.

Algorithm:

1. Set ITEM=A[LOC]

2. Repeat for I=LOC to N

3. Set A[1]=A[I+1]

4. Set N=N-1

5. EXIT

Traversing in Linear arrays:

1. Processing each element in the arrays atleast one.

2. Revisiting each element in a linear array only once is called Traversing.

3. Accessing each element of the array only once so that it can be processed is called as Traversing

Algorithm:

1. Start

2. Initialize counter Set k=LB

3. Repeat steps 4th and 5th

4. Visit element Apply process to LA[K]

5. Increment counter

K=k+1

6. Stop

Sorting:

Arranging the elements into ascending or descending order is called sorting.

Arranging the unordered elements in an array in ordered way is called sorting.

Applications of Sorting:

Data management: Sorting data makes it easier to search, retrieve, and analyze.

Database optimization: Sorting data in databases improves query performance. We typically keep the data sorted by primary index so that we can do quick queries.

Machine learning: Sorting is used to prepare data for training machine learning models.

Data Analysis: Sorting helps in identifying patterns, trends, and outliers in datasets. It plays a vital role in statistical analysis, financial modeling, and other data-driven fields.

Operating Systems: Sorting algorithms are used in operating systems for tasks like task scheduling, memory management, and file system organization.

Advantages of Sorting:

Efficiency: Sorting algorithms help in arranging data in a specific order, making it easier and faster to search, retrieve, and analyze information.

Improved Performance: By organizing data in a sorted manner, algorithms can perform operations more efficiently, leading to improved performance in various applications.

Simplified data analysis: Sorting makes it easier to identify patterns and trends in data.

Reduced memory consumption: Sorting can help reduce memory usage by eliminating duplicate elements.

Improved data visualization: Sorted data can be visualized more effectively in charts and graphs.

Disadvantages of Sorting:

Insertion: If we wish to keep data sorted, then insertion operation becomes costly as we have to maintain sorted order. If we do not have to maintain sorted order, we can simply insert at the end.

Algorithm selection: Choosing the most appropriate sorting algorithm for a given dataset can be challenging.

For a lot of problems hashing works better than sorting, for example, finding distinct elements, finding a pair with given sum.

Types of Sorting:

1. Bubble Sort

2. Selection Sort

3. Insertion Sort

4. Quick Sort

5. Merge Sort

BUBBLE SORT:

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high.

We sort the array using multiple passes. After the first pass, the maximum element goes to end (its correct position). Same way, after second pass, the second largest element goes to second last position and so on.

In every pass, we process only those elements that have already not moved to correct position. After k passes, the largest k elements must have been moved to the last k positions.

In a pass, we consider remaining elements and compare all adjacent and swap if larger element is before a smaller element. If we keep doing this, we get the largest (among the remaining elements) at its correct position.

Algorithm of Bubble Sort:

Step 1: for pass=1 to n-1

Step 2: for j=0 to n-pass-1

Step 3: if a[j]>a[j+1] then

Temp=a[j]

a[j]=a[j+1]

a[j+1]=temp

Step 4: end for

Step 5: end for

Advantages of Bubble Sort:

Bubble sort is easy to understand and implement.

It does not require any additional memory space.

It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in the sorted output.

Disadvantages of Bubble Sort:

Bubble sort has a time complexity of O(n2) which makes it very slow for large data sets.

Bubble sort has almost no or limited real world applications. It is mostly used in academics to teach different ways of sorting.

Complexity Analysis of Bubble Sort:

TimeComplexity: O(n2)

Auxiliary Space: O(1)

INSERTION SORT

Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is like sorting playing cards in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. Then, you pick a card from the unsorted group and put it in the right place in the sorted group.

We start with the second element of the array as the first element is assumed to be sorted.

Compare the second element with the first element if the second element is smaller than swap them.

Move to the third element, compare it with the first two elements, and put it in its correct position

Repeat until the entire array is sorted.

 

Algorithm:

1. Repeat step2 to 3 for pass=1 to n-1

2. set k=A[pass]

3. Repeat step 4 for j=pass-1 to 0

4. if (k<A[j]) a. A [j+1] = A[j]

b. A [j+1] = k

5. EXIT

Advantages of Insertion Sort

Simple and easy to implement.

Stable sorting algorithm.

Efficient for small lists and nearly sorted lists.

Space-efficient as it is an in-place algorithm.

Disadvantages

Inefficient for large lists.

Not as efficient as other sorting algorithms (e.g., merge sort, quick sort) for most cases.

Complexity Analysis of Insertion Sort

Time Complexity

Best case: O(n), If the list is already sorted, where n is the number of elements in the list.

Average case: O(n2), If the list is randomly ordered

Worst case: O(n2), If the list is in reverse order

Space Complexity

Auxiliary Space: O(1), Insertion sort requires O(1) additional space, making it a space-

efficient sorting algorithm.

SELECTION SORT

Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly

selecting the smallest (or largest) element from the unsorted portion and swapping it with the

first unsorted element. This process continues until the entire array is sorted.

1. First we find the smallest element and swap it with the first element. This way we get the

smallest element at its correct position.

2. Then we find the smallest among remaining elements (or second smallest) and swap it with

the second element.

3. We keep doing this until we get all elements moved to correct position.

Algorithm:

1. set location=0

2. Repeat step 3 and 4 for k=0 to n-1

3. Loc=call MIN (a,k,n)

4. (Interchange A[k] and A[loc]) i. Temp=A[k]

ii. A[k]=A[loc]

iii. A[loc]=temp

5. EXIT

Algorithm min(a[0------a-1];m,n)

1. Set min=A[k],loc=k

2. Repeat step3 for j=k+1 to n-1

3. if min>A[j] a. min =A[j]

b. loc =j

4. Return Loc;

 

Advantages:

 Simple and Easy to Implement:

Selection sort is straightforward to understand and implement, making it a good choice for

learning about sorting algorithms.

 Performs Well on Small Datasets:

For small arrays, selection sort can be a viable option due to its simplicity.

Disadvantages:

 Not Stable:

Selection sort is not a stable sorting algorithm, meaning it may change the relative order of

elements with the same value.

 Not Adaptive:

It's not adaptive to partially sorted input, meaning its performance doesn't improve if the input

is already partially sorted.

QUICK SORT

QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a

pivot and partitions the given array around the picked pivot by placing the pivot in its correct

position in the sorted array.

It works on the principle of divide and conquer, breaking down the problem into smaller sub-

problems.

There are mainly three steps in the algorithm:

1. Choose a Pivot: Select an element from the array as the pivot. The choice of pivot can

vary (e.g., first element, last element, random element, or median).

2. Partition the Array: Rearrange the array around the pivot. After partitioning, all elements

smaller than the pivot will be on its left, and all elements greater than the pivot will be on

its right. The pivot is then in its correct position, and we obtain the index of the pivot.

3. Recursively Call: Recursively apply the same process to the two partitioned sub-arrays

(left and right of the pivot).

4. Base Case: The recursion stops when there is only one element left in the sub-array, as a

single element is already sorted.

Another important point: When left and right element crosses each other then right element

will swap or interchange with the pivot element.

Algorithm For Sorting:

Step 1: if (low<high) then

Step 2: j=partition(A,low,high)

Step 3: Quick_ sort(A,low,j-1)

Step 4: Quick_ sort(A,j+1,high)

Step 5: End if

Step 6: EXIT

Algorithm of Quick Sort for Partition:

Step 1: set pivot=low

I=low

J=high

Step 2: Repeat step 3 to step 6 while(i<j)

Step 3: Repeat step 4 while (( i< high ) && (A[i]<=[pivot]))

Step 4: i=i+1

Step 5: Repeat step 6 while (A[j]>A[pivot])

Step 6: j=j-1

Step 7: if(i<j)

Swap a[i] & a[j]

End of step 2 while

Step 8: swap a[j] & pivot

Step 9: Return(j)

Advantages

 Efficiency: Sorting algorithms help in arranging data in a specific order, making it easier

and faster to search, retrieve, and analyze information.

 Improved Performance: By organizing data in a sorted manner, algorithms can perform

operations more efficiently, leading to improved performance in various applications.

 Simplified data analysis: Sorting makes it easier to identify patterns and trends in data.

 Reduced memory consumption: Sorting can help reduce memory usage by eliminating

duplicate elements.

 Improved data visualization: Sorted data can be visualized more effectively in charts and

graphs.

Disadvantages

 Insertion: If we wish to keep data sorted, then insertion operation becomes costly as we

have to maintain sorted order. If we do not have to maintain sorted order, we can simply

insert at the end.

 Algorithm selection: Choosing the most appropriate sorting algorithm for a given dataset

can be challenging.

 For a lot of problems hashing works better than sorting, for example, finding distinct

elements, finding a pair with given sum.

Searching

 Searching refers to finding for an element in any list.

 Searching in data structure refers to the process of finding location LOC of an element in

a list. This is one of the important parts of many data Structure algorithms, as one

operation can be performed on a element if and only if we find it.

 

Importance of Searching in Data Structures:

Searching is a fundamental operation in data structures. It allows us to find specific data items

within a collection of data. Efficient searching is crucial for many applications, including:

 Databases: Searching for records based on criteria

 Search engines: Finding web pages relevant to a query

 Artificial intelligence: Identifying patterns and making decisions

 Data analysis: Extracting insights from large datasets

Types of Searching:

There are two main types of searching:

 Linear search: Iterates through the entire collection, comparing each element to the target

value.

 Binary search: Divides the collection into smaller and smaller halves, narrowing down the

search range.

Linear Search

Linear search is a very simple algorithm. In this type of search, a sequential search is made over

all items one by one. Every item is checked and if a match is found the that particular item is

returned, otherwise the search continues till the end of the data collection.

For example: Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30

Algorithm

Linear search (A [] , n , key)

Let A [] be a linear array with n elements and key is an element to be searched in A [].

Step 1: Set i=0

Step 2: while (i<n) do

If A[i] = = key then

Return i; // key found at I th location

End while

Step 3: Return-1; //key not found

Application of Linear Search:

Linear search has several practical applications in computer science and beyond. Here are

some examples:

 Phonebook Search: Linear search can be used to search through a phonebook to find a

person's name, given their phone number.

 Spell Checkers: The algorithm compares each word in the document to a dictionary of

correctly spelled words until a match is found.

Algorithm

Linear search (A [] , n , key)

Let A [] be a linear array with n elements and key is an element to be searched in A [].

Step 1: Set i=0

Step 2: while (i<n) do

If A[i] = = key then

Return i; // key found at I th location

End while

Step 3: Return-1; //key not found

Application of Linear Search:

Linear search has several practical applications in computer science and beyond. Here are

some examples:

 Phonebook Search: Linear search can be used to search through a phonebook to find a

person's name, given their phone number.

 Spell Checkers: The algorithm compares each word in the document to a dictionary of

correctly spelled words until a match is found.

Finding Minimum and Maximum Values: Linear search can be used to find the

minimum and maximum values in an array or list.

 Searching through unsorted data: Linear search is useful for searching through unsorted

data.

Advantages of Linear Search:

 Simplicity: Linear search is a very simple algorithm to understand and implement.

 Works with unsorted data: Linear search works well with unsorted data. It does not

require any pre-processing or sorting of the data before performing the search.

 Low memory usage: Linear search only requires a small amount of memory to store the

index of the current element being searched.

 Easy to debug: Because linear search is a simple algorithm, it is easy to debug and

troubleshoot any issues that may arise.

Disadvantages of Linear search:

 Inefficient for large datasets: As the size of the dataset grows, the time taken by linear

search also increases proportionally.

 Limited applicability: Linear search is only suitable for datasets that are not too large or

not too complex.

 No early termination: Linear search does not have a mechanism to terminate early once

the target element is found.

 Inefficient for sorted data: When the data is already sorted, linear search is not efficient

because it needs to check each element one by one, even if it has already passed the target

element.

 

Binary Search

Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly

dividing the search interval in half. The idea of binary search is to use the information that the

array is sorted and reduce the time complexity to O(log N).

Conditions to apply Binary Search Algorithm in a Data Structure

To apply Binary Search algorithm:

 The data structure must be sorted.

 Access to any element of the data structure should take constant time.

Below is the step-by-step algorithm for Binary Search:

 Divide the search space into two halves by finding the middle index “mid”.

 Compare the middle element of the search space with the key.

If the key is found at middle element, the process is terminated.

 If the key is not found at middle element, choose which half will be used as the next search

space.

o If the key is smaller than the middle element, then the left side is used for next

search.

o If the key is larger than the middle element, then the right side is used for next

search.

 

 This process is continued until the key is found or the total search space is exhausted.

How does Binary Search Algorithm work?

To understand the working of binary search, consider the following illustration:

Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23.

 

Algorithm-Binary Search

(A[0---n-1],key)

Input: Given an array A of n elements is sorted under and key is an element to be sorted.

Output: Return the position of item element if successful and returns-1 otherwise.

Step 1: set first=0, last =n-1;

Step 2: repeat step 3 until (first,=last)

Step 3: find the middle location 9mid)=(f+l)/2

if key is equal to a[mid]

else if (key<a[mid]) then search element from first to mid-1

last=mid-1

else search element from mid+1 to last first= mid+1

end while

Step 4: return-1

Applications of Binary Search Algorithm

 Binary search can be used as a building block for more complex algorithms used in

machine learning, such as algorithms for training neural networks or finding the optimal

hyper parameters for a model.

 It can be used for searching in computer graphics such as algorithms for ray tracing or

texture mapping.

 It can be used for searching a database.

 

How to Implement Binary Search Algorithm?

The Binary Search Algorithm can be implemented in the following two ways

 Iterative Binary Search Algorithm

 Recursive Binary Search Algorithm

Iterative Binary Search Algorithm

// C program to implement iterative Binary Search

#include <stdio.h>

// An iterative binary search function.

int binarySearch(int arr[], int low, int high, int x)

{

while (low <= high) {

int mid = low + (high - low) / 2;

// Check if x is present at mid

if (arr[mid] == x)

return mid;

// If x greater, ignore left half

if (arr[mid] < x)

low = mid + 1;

// If x is smaller, ignore right half

else

high = mid - 1;

}

// If we reach here, then element was not present

return -1;

}

// Driver code

int main(void)

{

int arr[] = { 2, 3, 4, 10, 40 };

int n = sizeof(arr) / sizeof(arr[0]);

int x = 10;

int result = binarySearch(arr, 0, n - 1, x);

if(result == -1) printf("Element is not present in array");

else printf("Element is present at index %d",result);

}

OUTPUT:

Element is present at index 3

Recursive Binary Search Algorithm:

// C program to implement recursive Binary Search

#include <stdio.h>

// A recursive binary search function. It returns

// location of x in given array arr[low..high] is present,

// otherwise -1

int binarySearch(int arr[], int low, int high, int x)

{

if (high >= low) {

int mid = low + (high - low) / 2;

// If the element is present at the middle

// itself

if (arr[mid] == x)

return mid;

// If element is smaller than mid, then

// it can only be present in left subarray

if (arr[mid] > x)

return binarySearch(arr, low, mid - 1, x);

// Else the element can only be present

// in right subarray

return binarySearch(arr, mid + 1, high, x);

}

// We reach here when element is not

// present in array

return -1;

}

// Driver code

int main()

{

int arr[] = { 2, 3, 4, 10, 40 };

int n = sizeof(arr) / sizeof(arr[0]);

int x = 10;

int result = binarySearch(arr, 0, n - 1, x);

if (result == -1) printf("Element is not present in array");

else printf("Element is present at index %d", result);

return 0;

}

OUTPUT:

Element is present at index 3

 

Sparse Matrix:

Sparse matrix are those matrix which have the majority of the elements are ZERO.

0 0 1 2

1 0 0 3

1 0 0 0

Why to use sparse matrix instead of simple matrix:

Storage: There are lesser non-zero elements than zero ,so memory can be used to store elements.

Computing Time: Computing time can be saved by logically desiging a data structure traversing

only non-zero elements.

 

Some sparse array are:

1. Diagonal Matrix.                       2. Tridiagonal matrix.

2 0 0 0 0                                4 1 0 0 0

0 3 0 0 0                                0 3 2 0 0

0 0 5 0 0                                0 6 7 6 0

0 0 0 8 0                                0 0 5 5 0

0 0 0 0 7

 

Memory Representation of Sparse Matrix:

We can store non-zero elements with Triples (Row,Column,Value)

2D -Array is used to represent a sparse matrix in which there are 3 rows named as.

Row: Index of row, where non- element is located.

Column: Index of column, on-zero elements is located.

Value: value of the non-zero element located index (row, column)

Example:

0 0 4 0 5

0 0 0 3 6

0 0 0 2 0

0 0 3 0 0

 

ROW        0   0   1   1   2   3   3

COLUMN       2   4   3   4   3   1   2

VALUE            4   5   3   6   2   2   3

 

Example:

0 0 0 1

1 0 0 5

0 0 6 0

 

ROW        0   1   1   2

COLUMN       3   0   3   2

VALUE            1   1   5   6