## Kerala Plus One Computer Science Notes Chapter 8 Arrays

**Introduction:**

Array is a kind of data type derived from fundamental data types to handle large number of data easily.

**Need of an Array**

An array is a collection of elements of the same type placed in contiguous memory locations. Arrays are used to store a set of values of the same type under a single variable name. Each element in an array can be accessed using its position in the list, called index number or subscript. If we want to handle long and repetitive task, in this case arrays are very useful.

**Declaring an Array**

The array is to be declared properly before it is used. The syntax for declaring an array is,

data_type array_name[size];

where data_type is the type of data that the array variable can store, array_name is an identifier for naming the array and the size is a positive integer number that specifies the number of elements in the array.

eg., int num [10];

Each item in an array is called an element of the array. Since the elements in the array are stored sequentially, any element can be accessed by giving the array’s name and the element’s position. This position is called the index or subscript value. In C++, the array index starts with zero.

**Memory allocation for Array**

The amount of storage required to hold an array is directly related to its type and size.

For a single dimensional array, the total size allocated can be computed as,

total_bytes = sizeof(array_type)x size_of_ array

eg., total bytes allocated for the array declared as float a[1o]; will be 4 x 10 = 40 bytes.

**Array Initialisation**

An array can be initialized in the declaration by writing a comma-separated list of values enclosed in braces following an equal sign. When an array is initialized with val¬ues, the size can be omitted,

eg., int num [4] = {15, 31, 67, 24};

char code[3] = {‘d’, ‘e’, ‘t’};

int reg [ ] = {12, 88, 90, 58, 45>;

**Accessing Elements of Arrays**

The elements of an array can be accessed by specifying the array name followed by subscript in brackets. The last valid subscript is called upper bound,

eg., int num [2] = 67;

**Array Operations**

The operations performed on arrays include traversal, searching, insertion, deletion, sorting and merging.

**1. Traversal:**

Accessing each element of the array atleast once is called traversal. We can use this operation to check the correctness of operations during operations like insertion, deletion etc. Displaying all the elements of an array is an example of traversal.

eg., for (i=o; i<ia; i++)

cout<< a[i]<< “\t”;

**2. Sorting:**

It is the process of arranging the elements of the array in some logical

order. This logical order may be ascending or descending in case of numeric values or dictionary order in case of strings. It can be different types:

**i. Selection sort:** One of the simplest sorting techniques is the selection sort. To sort an array in ascending order, the selection sort algorithm starts by finding the minimum value in the array and moving it to the first position. At the same time, the element at the first position is shifted to the position of the smallest element. This step is then repeated for the second lowest value by moving it to the second position, and so on until the array is sorted.

The process of finding the smallest element and exchanging it with the element at the respective position is known as a pass. For ‘n’ number of elements there will be ‘n¬1′ passes.

**Algorithm for selection sort **Step 1: Start

Step 2: Accept a value in N as the number of elements of the array.

Step 3: Accept N elements into the array AR.

Step 4: Repeat Steps 5 to 9, (N – x) times. Step 5: Assume the first element in the list as the smallest and store it in MIN and its position in POS.

Step 6: Repeat Step 7 until the last element of the list.

Step 7: Compare the next element in the list with the value of MIN. If it is found smaller, store it in MIN and its position in POS.

Step 8: If the first element in the list and the value in MIN are not the same, then swap the first element with the element at position POS.

Step 9: Revise the list by excluding the first element in the current list.

Step 1o:Print the sorted array AR.

Step 11: Stop

**ii) Bubble sort:**

It is a sorting algorithm that works by repeatedly stepping through lists that need to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. This passing procedure is repeated until no swaps are required, indicating that the list is sorted. Bubble sort gets its name because larger element bubbles towards the top of the list. Algorithm for bubble sort

Step 1: Start

Step 2: Accept a value in N as the number of elements of the array.

Step 3: Accept N elements into the array AR.

Step 4: Repeat Steps 5 to 7, (N – 1) times.

Step 5: Repeat Step 6 until the second last element of the list.

Step 6: Starting from the first position,compare two adjacent elements in the list. If they are not in proper order, swap the elements.

Step 7: Revise the list by excluding the last element in the current list.

Step 8: Print the sorted array AR.

Step 9: Stop

**3. Searching:**

It is the process of finding the location of the given element in the array. The search is said to be successful if the given element is found, that is the element

exists in the array; otherwise unsuccessful. There are basically two approaches to search operation:

** i. Linear search:** Also known as sequential search. It is a method for finding a particular value in a list. Linear search consists of checking each element in the list, one at a time in sequence starting from the first element, until the desired one is found or the end of the list is reached.

**Algorithm for Linear search **Step 1: Start

Step 2: Accept a value in N as the number of elements of the array

Step 3: Accept N elements into the array AR

Step 4: Accept the value to he searched in the variable ITEM Step 5: Set LOC = -1

Step 6: Starting from the first position, repeat Step 7 until the last element

Step 7: Check whether the value in ITEM is found in the current position. If found then store the position in LOC and Go to Step 8, else move to the next position.

Step 8: If the value of LOC is less than 0

then display “Not Found”, else dis-play the value of LOC + 1 as the position of the search value.

Step 9: Stop

eg., Assume that the element ‘45’ is to be searched from a sequence of elements 50, 18, 48, 35, 45, 26, 12.

**ii. Binary search:**

If the array contains a sorted list then we can use a more efficient search algorithm called binary search which can reduce the search time.

Binary search is an algorithm which uses minimum number of searches for locating the position of an element in a sorted list, by checking the middle, eliminating half of the list from consideration, and then performing the search on the remaining half. If the middle element is equal to the searched value, then the position has been found; otherwise the upper half or lower half is chosen for search, based on whether the element is greater than or less than the middle element.

**Algorithm for binary search**

Step 1: Start

Step 2: Accept a value in MAX as the number of elements of the array

Step 3: Accept MAX elements into the array LIST

Step 4: Accept the value to be searched in the variable ITEM

Step 5: Store the position of the first element of the list in FIRST and that of the last in LAST

Step 6: Repeat Steps 7 to 11 While (FIRST <= LAST)

Step 7: Find the middle position using the formula (FIRST + LAST)/2 and store it in MIDDLE

Step 8: Compare the search value in ITEM with the element at the MIDDLE of the list

Step 9: If the MIDDLE element contains the search value in ITEM then stop search, display the position and go to Step 12.

Step 10:If the search value is smaller than the MIDDLE element, then set LAST = MIDDLE – 1

Step 11:If the search value is larger than the MIDDLE element, then set FIRST = MIDDLE + 1

Step 12:Stop

eg., We have to search 45 in the array

Middle=(First+last)/2=(o+6)/2=3,

List[3] ≠ 45 First=middle +1=3+1 =4,

Last=6

Middle=(First+last)/2=(4+6)/2=5,

Here LIST[s] is not equal to 45 and

LIST[5] is greater than the search element therefore, we take First=4,

Last=middle -1=5-1 =4,

Middle=(First+last)/2=(4+4)/2=4,

Here LIST[4] is equal to 45 and the search terminate successfully.

**Two Dimensional (2D) Arrays**

A two dimensional array is an array in which each element itself is an array. The general form of a 2D array declaration is: data_type array_name[rows][columns];

The rows refers to the number of rows in the array and columns refers to the number of columns in the array. The indicts (subscripts) Of rows and columns, start at 0 and ends at (rows-1) and (columns-1) respectively.

eg., int marks[5][4];

The amount of storage required to hold a two dimensional array depends upon its base type, number of rows and number of columns. The formula to calculate total

number of bytes required for a 2D array is,

total_bytes = sizeof(base type) × number of rows x number of columns

eg., Array marks[s][4] requires 4×5×4=80

bytes.

**Matrices as 2D Arrays**

Matrices can be represented through 2D arrays with rows and columns. A nested loop is used to store and access elements in an array.

**Multi-dimensional arrays**

Each element of a 2D array may be another array. Such an array is called 3D (Three Dimensional) array.

Its declaration is:

data_type array_name[size_1] [size_2] [size 3];

The elements of a 3D array are accessed using three subscripts,

eg., int student [5][4][6];

## Leave a Reply