Arrays
Let us see the simple algorithm that gets two integers, store it and then display them to user. Next converting it into code block so that inventory of task to study.
| Algorithm to function for study |
|
|
Algorithm: Get N Show 2 Integers
Input: 2 integers Output: value of 2 inputs
Step 1: declare 2 variables i1, i2. Step 2: ask user to input 2 integers. Step 3: store inputs in i1 & i2 i1 = Input1, i2 = Input2. Step 4: display i1, i2. Step 5: stop.
|
main() { int i1, i2; printf (“ Enter 2 integers.” ); scanf (“%d, %d”, &i1, &i2); printf (“n3 = %d” , n3); }
|
What if, the program has to store 120 student’s register number and show it when needed? Expanding above algorithm to accumulate 120 integers is not so wise option. Programmer has to declare 120 variables as said in step1, which not a practical way of programming.
Therefore, programmer needs different kind of data type to store such huge similar kind of data. The C language offers array for such tasks as shown below.
| Algorithm to function using array |
|
|
Algorithm: Get N Show 120 register numbers
Input: 120 register numbers Output: value of 120 register numbers
Step 1: declare int type array of size 120. Step 2: ask user to input 120 register numbers. Step 3: store inputs in array with respect to their index value Step 4: display 120 register numbers. Step 5: stop.
|
main() { int i, regNo[120]; for(i=0;i<120;i++) { printf (“ Enter %d RegNo:” ); scanf (“%d”, regNo[i]); } printf (“Entered Reg No are:\n”); for(i=0;i<120;i++) { printf(“%d : %d”, i,regNo[i]); }
}
|
What is an Array?
| |
| |
| |
| |
Usage of Arrays
Like any other variable, arrays must be declared before they are defined or used.
| data_type variable_name [size] ; | |||||||||||||||||||||||||||||||||||||
| DECLARE an array which holds 6 characters or GANDHI | DECLARE an array which holds 3 integers or 30, 51 & 809. | ||||||||||||||||||||||||||||||||||||
| char name[6] = { ‘G’,’A’,’N’,’D’,’H’,’I’}; | int Height[3] = { 30 , 51 , 809 }; | ||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||
| Here code reserves (1 byte * 6) = 6 bytes consecutive memory for array and stores memory address of name[0], i.e., 1001 in variable name. Since variable name is pointer to first array element, it traverses through array using offset value. So array size = 6, index value = 0-5. If user access name[6] value, it will be random data & may cause code to produce wrong output. | Here code reserves (2 byte * 3) = 6 bytes consecutive memory for array and stores memory address of Height[0], i.e., 1201 in variable Height.
Since variable Height is pointer to first array element, it traverses through array using offset value. So array size = 3, index value = 0-2. If user access Height[3] value, it will be random data & may cause code to produce wrong output. | ||||||||||||||||||||||||||||||||||||
| | |||||||||||||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||||||||||||
Array elements are stored in consequent memory locations, and accessed by pointer, which points to first element’s memory address. So, while getting value for array no need to mention ‘address operator’ or & [ampersand] before variable name [as it is necessary in char, int, long, double variables].
int i, regNo[120], fee;
for(i=0;i<120;i++)
{
printf (“ Enter %d RegNo:” );
scanf (“%d”, regNo[i]); //no need of &
printf (“ Enter Fee paid:” );
scanf (“%d”, &fee); //need of &
}
Arrays can be initialise at the time of declaration and uninitialized elements will contain random value.
| Initializing array at the time of declaration
int marks [5] = { 56 , 67, 15, 98, 12 };
| Declaring array then initializing in code block
int marks [5]; ……. marks[0]= 56; marks[1]= 67; marks[2]= 15; marks[3]= 98; marks[4]= 12; |
Processing with Arrays
Programmer can use an array element inside any instruction where he would use a variable-input or output commands or expressions. Program always refer to the individual element by its subscript number. Usually for() loop is used to traverse through array.
Array and Function
You can pass entire array from the function to another. When you pass an array, you are really passing the address of the array. C does not make a copy of the entire array but merely assigns the same address area, and thus its data to a second array name.
| //function prototype SendingArray( int a[], int i);
main() { int x, ar[10]; x = 2; … SendingArray ( ar , x ); //function call … }
//function implementation SendingArray(int br[], int a) { …. } |
with dummy arguments
with actual arguments, only array name ar is passed [as it is pointer to memory address].
function receiving values |
| passing array in function arguments [passing arguments by value] | |
| Passing an array by its address rather than by duplicating it saves memory, but it can have some side effects. Changing an array element in the receiving function will also change the value of the passed array. | |
Multi-dimensional Array
If you want to store matrix elements, you need multidimensional arrays. They are declared as n dimensional array, except that separate square bracket is required for each subscript. If it is two dimensional, two pair of square brackets and for n-dimensional array n pair of brackets.
| data_type variable_name [s1][s2][s3]...[sn] ; | |
|
//declaring 2-dimensional matrix matrix [0][0] = 1 ; //initialised matrix [0][1] = 2 ; matrix [0][2] = 3 ; matrix [1][0] = 4 ; matrix [1][1] = 5 ; matrix [1][2] = 6 ;
//declare & initialised int matrix [2] [3] = { 1 , 2 , 3 , 4 , 5 , 6 } ;
//in above example: first row=0 col=0,1,2 then row=1 col=0,1, 2 elements are stored. | |
| 2 dimension array example equivalent to square |
|
{ 1 , 2 },{ 3 , 4,}, { 5 , 6 }, { 7 , 8 } }; //is equivalent to below initialisation matrix [0][0] [0] = 1 ; matrix [1][0] [0] = 5 ; matrix [0][0] [1] = 2 ; matrix [1][0] [1] = 6 ; matrix [0][1] [0] = 3 ; matrix [1][1] [0] = 7 ; matrix [0][1] [1] = 4 ; matrix [1][1] [1] = 8 ; | ||
| //in above example: row=0 col0=0 col2=0 col2=1 col1=1 col2=0 col2=1 |
row=2 col0=0 col2=0 col2=1 col1=1 col2=0 col2=1 | |
| 3 dimension array example equivalent to cube | ||
It is evident from above examples, as dimensions increases complexity to understand them also increases. The 3-dimensions array is the maximum best choice size for human brain can analyze.
Sorting Operation
Sorting means arranging the data in a specific order, such as marks in descending order to get merit list. You can arrange the data either in ascending order or in descending order. There are many techniques or algorithm to solve such operations.
Bubble Sorting
In this Bubble sorting method the smallest element of array, come at the first position and in ascending order biggest number at the end.
As the bubble is coming to surface, it becomes bigger but lighter also. Therefore, at the beginning, number is bigger and goes on decreasing as it bubbles out and at top smallest number.
Bubble Sort: For N number of elements to arrange in ascending order, N-1 rounds are need. In each round largest number is sorted to last position in its order.
5 4 1 16 3
Above example has 5 numbers, so 5-1=4 rounds needed to sort it to ascending order.
Round 1: move largest of 5 numbers, i.e., 16 to last or 5th position in 5-1=4 steps.
Step 1: compare 1st Number [5] and 2nd number [4], interchange if 1st number is greater than 2nd number [yes in this step!]. After step 1 the result is:
4 5 1 16 3
Step 2: compare 2nd Number [5] and 3rd number [1], interchange if 2nd number is greater than 3rd number [yes in this step!]. After step 2 the result is:
4 1 5 16 3
Step 3: compare 3rd Number [5] and 4th number [16], interchange if 3rd number is greater than 4th number [No in this step!]. After step 3 the result is:
4 1 5 16 3
Step 4: compare 4th Number [16] and 5th number [3], interchange if 4th number is greater than 5th number [Yes in this step!]. After step 4 the result is:
4 1 5 3 16
Round 2: move second largest of 5 numbers, i.e., 5 to 4th position in 5-2=3 steps.
Step 1: compare 1st Number [4] and 2nd number [1], interchange if 1st number is greater than 2nd number [yes in this step!]. After step 1 the result is:
1 4 5 3 16
Step 2: compare 2nd Number [4] and 3rd number [5], interchange if 2nd number is greater than 3rd number [No in this step!]. After step 2 the result is:
1 4 5 3 16
Step 3: compare 3rd Number [5] and 4th number [3], interchange if 3rd number is greater than 4th number [Yes in this step!]. After step 3 the result is:
1 4 3 5 16
Round 3: move third largest of 5 numbers, i.e., 4 to 3rd position in 5-3=2 steps.
Step 1: compare 1st Number [1] and 2nd number [4], interchange if 1st number is greater than 2nd number [No in this step!]. After step 1 the result is:
1 4 3 5 16
Step 2: compare 2nd Number [4] and 3rd number [3], interchange if 2nd number is greater than 3rd number [Yes in this step!]. After step 2 the result is:
1 3 4 5 16
Round 4: move fourth largest of 5 numbers, i.e., 3 to 2nd position in 5-4=1 step.
Step 1: compare 1st Number [1] and 2nd number [3], interchange if 1st number is greater than 2nd number [No in this step!]. After step 1 the result is:
1 3 4 5 16
Searching Operation
Searching means locating the required item in collection of data and printing message as item found or not, if found its location and item itself. There are many algorithms or technique to search or find any item in database, and basic two methods are linear/sequential search and binary search.
Linear or Sequential Search
As name implies, in this searching method all elements are compared and traverse sequentially until required item is found. See the example program for details as it is very straightforward concept.
Binary Search
This search method applied to ascending ordered array. This divides given segment into three parts, mid, left and right and searches required item in it.
The Binary search works on increasingly ordered array and operates in 4 rounds. First round is to calculate midterm of the segment. Then it checks whether required item is in middle or left side or right side in later three rounds. If item is in middle, then just assigns the location. If item is on left side or right side, then it has to iterate through all that side elements to find the required item.
int a [5 ] = { 1 3 4 5 16 };
a[beg] a[beg+1] a[beg+2] a[beg+3] a[end]
a [0] a [1] a [2] a [3] a [4]
1 3 4 5 16
Left Side a[mid] Right side
| search here if(item < a[mid]) | store location if(item == a[mid]) | search here if(item > a[mid]) |
| If search item is 16 | So item = 16 initially found =0 after round4 found =1 | mid = 2 beg = 0 end = 4 |
Round 1: Find the midterm of segment
mid = INT (beg + end ) / 2;
mid = INT (0 + 4 ) /2 = 2
Round 2: Check whether midterm of segment is required item or not.
If (item == a[mid]) //false as 16 is not equal to 4
Round 3: Check whether required item is on left side or not.
if(item < a[mid]) //false as 16 is not less than 4
Round 4: Check whether required item is on right side or not.
if(item > a[mid]) //true as 16 is greater than 4
Step 1: beg = mid + 1 = 2 + 1 = 3 ;
Step 2: if (item == a[beg]) //false as 16 is not equal to 5
Step 3: if (item == a[beg+1]) //True as 16 is equal to 16
location = beg+1;//location is 4
found = 1 ;
Thus we found that required item 16 at a[4].
| If search item is 1 | So item = 1 initially found =0 after round3 found =1 | mid = 2 beg = 0 end = 4 |
Round 1: Find the mid term of segment
mid = INT (beg + end ) / 2;
mid = INT (0 + 4 ) /2 = 2
Round 2: Check whether midterm of segment is required item or not.
If (item == a[mid]) //false as 1 is not equal to 4
Round 3: Check whether required item is on left side or not.
if(item < a[mid]) //true as 1 is less than 4
Step 1: beg = beg = 0 ;
Step 2: if (item == a[beg]) //True as 1 is equal to 1
location = beg;//location is 0
found = 1 ;
Thus we found that required item 1 at a[0].
| If search item is 4 | So item = 4 initially found =0 after round 2 found =1 | mid = 2 beg = 0 end = 4 |
Round 1: Find the mid term of segment
mid = INT (beg + end ) / 2;
mid = INT (0 + 4 ) /2 = 2
Round 2: Check whether mid term of segment is required item or not.
If (item == a[mid]) //true as 4 is equal to 4
location = mid;//location is 2
found = 1;
Thus we found that required item 1 at a[2].
| If search item is 20 | So item = 20 initially found =0 after round4 found = 0 | mid = 2 beg = 0 end = 4 |
Round 1: Find the mid term of segment
mid = INT (beg + end ) / 2;
mid = INT (0 + 4 ) /2 = 2
Round 2: Check whether mid term of segment is required item or not.
If (item == a[mid]) //false as 20 is not equal to 4
Round 3: Check whether required item is on left side or not.
if(item < a[mid]) //false as 20 is not less than 4
Round 4: Check whether required item is on right side or not.
if(item > a[mid]) //true as 20 is greater than 4
Step 1: beg = mid + 1 = 2 + 1 = 3 ;
Step 2: if (item == a[beg]) //false as 20 is not equal to 5
Step 3: if (item == a[beg+1]) //false as 20 is not equal to 16
Step 4: if (end < beg + 2) //true as 4 < 3+2
found = 0 ;
Thus we found that required item 20 is not in segment. So search unsuccessful.
| Previous Page | Main Contents | Next Page |
No comments:
Post a Comment