ARRAYs
(group of same type of elements)
ARRAY
We will start our discussion with an example:
WAP in C to find the average of 10 integers.
#include<stdio.h>
#include<stdio.h> int main()
int main() scanf(“%d”,&g); {
{ scanf(“%d”,&h); int a,b,c,d,e,f,g,h,i,j;
int a,b,c,d,e,f,g,h,i,j; scanf(“%d”,&i); float avg;
float avg; scanf(“%d”,&j); printf(“enter 10 numbers”);
printf(“enter 10 numbers”); avg=(a+b+c+d+e+f+g+h+i+j)/10.0;
scanf(“%d”,&a); printf(“%f”,avg); scanf(“%d%d%d%d%d%d%d%d%d%d”,
scanf(“%d”,&b); return 0; &a,&b,&c,&d,&e,&f,&g,&h,&i,&j);
scanf(“%d”,&c); } avg=(a+b+c+d+e+f+g+h+i+j)/10.0;
scanf(“%d”,&d); printf(“%f”,avg);
scanf(“%d”,&e); return 0;
scanf(“%d”,&f); }
ARRAY
Definition: An array is collection of same type of data elements.
Declaration: Name of array
Size of array
int n[10];
It means we are declaring 10 integers, namely:
n[0], n[1], n[2], n[3], n[4], n[5], n[6], n[7], n[8] and n[9]
Initialization: a[0] a[1] a[2] a[3] a[4]
int a[5]={23,25,10,9,18}; 23 25 10 9 18
int a[5]={0}; a[0] a[1] a[2] a[3] a[4]
0 0 0 0 0
int a[5]={2}; a[0] a[1] a[2] a[3] a[4]
2 0 0 0 0
a[0] a[1] a[2] a[3] a[4]
int a[5]={2,5};
2 5 0 0 0
ARRAY
Definition: An array is collection of same type of data elements.
Declaration: Name of array
Size of array
int n[10];
It means we are declaring 10 integers, namely:
n[0], n[1], n[2], n[3], n[4], n[5], n[6], n[7], n[8] and n[9]
Initialization:
int a[5]={23,25,10,9,18};
int a[5]={0};
int a[5]={2};
int a[5]={2,5};
ARRAY
Taking values from user via scanf():
int a[10], i;
for(i=0;i<=9;i++)
scanf(“%d”,&a[i]);
Printing values via printf():
for(i=0;i<=9;i++)
printf(“%d ”,a[i]);
scanf(“%d%d%d%d%d%d%d%d%d%d”,&a[0], &a[1], &a[2], …,&a[9]);
Very inconvenient.
ARRAY
WAP in C to find minimum element in an array.
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
5 33 44 4 88 22 2 55 99 45
min=a[0]
Initially we assume that first element of array is the minimum element,
i.e. min=a[0]
Now we will compare this min with every other element of array
If we find a number even less than this min, we will set min to that value
ARRAY
WAP in C to find minimum element in an array.
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
5 33 44 4 88 22 2 55 99 45
min=a[0]
Initially we assume that first element of array is the minimum element,
i.e. min=a[0]
Now we will compare this min with every other element of array
If we find a number even less than this min, we will set min to that value
ARRAY
WAP in C to find minimum element in an array.
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
5 33 44 4 88 22 2 55 99 45
min=a[3]
Initially we assume that first element of array is the minimum element,
i.e. min=a[0]
Now we will compare this min with every other element of array
If we find a number even less than this min, we will set min to that value
ARRAY
WAP in C to find minimum element in an array.
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
5 33 44 4 88 22 2 55 99 45
min=a[6]
Initially we assume that first element of array is the minimum element,
i.e. min=a[0]
Now we will compare this min with every other element of array
If we find a number even less than this min, we will set min to that value
Linear Search
To search an element in an array.
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
77 33 44 11 88 22 66 55 99 45
n=22
The linear search algorithm searches all elements in the array sequentially.
Linear Search is defined as a sequential search algorithm that starts at one end
and goes through each element of an array until the desired element is found,
otherwise the search continues till the end of the array.
When data is unsorted, a linear search algorithm is preferred.
Linear Search
To search an element in an array.
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
77 33 44 11 88 22 66 55 99 45
Search Unsuccessful
n=12
int linear_search(int a[], int n, int val)
{
for(int i=0; i<n; i++)
{
if(a[i]==val) val is found at index: i
return i;
}
return -1; val is not present in a[]
}
Binary Search
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
11 22 33 44 55 66 77 88 99 111 121
n=10
Binary Search
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
11 22 33 44 55 66 77 88 99 111 121
n=111
Binary Search
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
11 22 33 44 55 66 77 88 99 111 121
n=111
Binary Search
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
11 22 33 44 55 66 77 88 99 111 121
n=111
Search Successful
Binary Search
Search the following array a for 36(key):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46
1. (0+15)/2=7; a[7]=19;
too small; search 8..15
2. (8+15)/2=11; a[11]=32;
too small; search 12..15
3. (12+15)/2=13; a[13]=37;
too large; search 12..12
4. (12+12)/2=12; a[12]=32;
too small; search 13..12 ...but 13>12, so quit: 36 not found
Search the following array a for 36(key):
l mid r
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46
1. (0+15)/2=7; a[7]=19;
too small; search 8..15
Binary Search
Search the following array a for 36(key):
mid l r
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46
1. (0+15)/2=7; a[7]=19;
too small; search 8..15
2. (8+15)/2=11; a[11]=32;
too small; search 12..15
Binary Search
Search the following array a for 36(key):
l mid r
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46
1. (0+15)/2=7; a[7]=19;
too small; search 8..15
2. (8+15)/2=11; a[11]=32;
too small; search 12..15
Binary Search
Search the following array a for 36(key):
mid l r
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46
1. (0+15)/2=7; a[7]=19;
too small; search 8..15
2. (8+15)/2=11; a[11]=32;
too small; search 12..15
3. (12+15)/2=13; a[13]=37;
too large; search 12..12
Binary Search
Search the following array a for 36(key):
l mid r
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46
1. (0+15)/2=7; a[7]=19;
too small; search 8..15
2. (8+15)/2=11; a[11]=32;
too small; search 12..15
3. (12+15)/2=13; a[13]=37;
too large; search 12..12
Binary Search
Search the following array a for 36(key):
l r
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46
1. (0+15)/2=7; a[7]=19;
too small; search 8..15
2. (8+15)/2=11; a[11]=32;
too small; search 12..15
3. (12+15)/2=13; a[13]=37;
too large; search 12..12
Binary Search
Search the following array a for 36(key):
l r mid
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46
1. (0+15)/2=7; a[7]=19;
too small; search 8..15
2. (8+15)/2=11; a[11]=32;
too small; search 12..15
3. (12+15)/2=13; a[13]=37;
too large; search 12..12
int arr[]={2,5,7,99,123,678,4455};
int l,r,mid;
l=0;
r=n-1; // n is size of array
while(l<=r)
{
mid=(l+r)2;
if val==arr[mid]
element is present break
else if val > a[mid]
l=mid+1
else
r=mid-1
}
if l>r not present
int bin_search(int a[], int n, int val)
Binary search
{
int l=0; Task: to search val in array a[] of size n
int r=n-1;
while (l <= r)
{ val is found at index: mid
int mid = (l + r) / 2;
if (a[mid]==val)
return mid;
else if(a[mid]<val)
l=mid+1;
else
r=mid-1; val is not present in a[]
}
return -1;
}
Binary search
Recursive function:
int binary_search(a[], l, r, val)
{
if (l>r)
return 0;
mid=(l+r)/2;
if(a[mid]==val)
return 1;
if (val>a[mid])
return binary_search(a[],l,mid-1,val);
else
return binary_search(a[],mid+1,r,val);
}
Sorting
ARRAY
Sorting an array in ascending order:
0 1 2 3 4 5 6 7
77 33 44 11 88 22 66 55
Bubble sort
Selection sort
Insertion sort
Merge sort
Quick sort
Heap sort
0 1 2 3 4 5 6 7 Counting sort
11 22 33 44 55 66 77 88
Bubble Sort
first 77 and 33 will be compared.
0 1 2 3 4 5 6 7
77 33 44 11 88 22 66 55
since 77>33 , 33 must be on left side
So swap 77 and 33.
33 77 44 11 88 22 66 55
now 77 and 44 will be compared.
33 77 44 11 88 22 66 55
since 77>44 , So swap 77 and 44.
33 44 77 11 88 22 66 55
0 1 2 3 4 5 6 7
if(a[j]>a[j+1])
33 33
77 swap them
77 44 11 88 22 66 55
j++
0 1 2 3 4 5 6 7
77 33 44 11 88 22 66 55 if(a[j]>a[j+1])
swap them
33 77 44 11 88 22 66 55 j++
END OF PASS 1
LARGEST
33 44 77 11 88 22 66 55 ELEMENT
GETS ITS
33 44 11 77 88 22 66 55 POSITION.
33 44 11 77 88 22 66 55
33 44 11 77 22 88 66 55
33 44 11 77 22 66 88 55
33 44 11 77 22 66 55 88
0 1 2 3 4 5 6 7
PASS 2
33 44 11 77 22 66 55 88
33 44 11 77 22 66 55 88
END OF PASS 2
Second Largest
33 11 44 77 22 66 55 88 Element
Gets its position.
33 11 44 77 22 66 55 88
33 11 44 22 77 66 55 88
33 11 44 22 66 77 55 88
33 11 44 22 66 55 77 88
0 1 2 3 4 5 6 7
PASS 3
33 11 44 22 66 55 77 88
END OF PASS 3
11 33 44 22 66 55 77 88 Third Largest
Element
Gets its position.
11 33 44 22 66 55 77 88
11 33 22 44 66 55 77 88
11 33 22 44 66 55 77 88
11 33 22 44 55 66 77 88
0 1 2 3 4 5 6 7 PASS 4
11 33 22 44 55 66 77 88
11 33 22 44 55 66 77 88
End of
PASS 4
11 22 33 44 55 66 77 88
11 22 33 44 55 66 77 88
11 22 33 44 55 66 77 88
0 1 2 3 4 5 6 7 PASS 5
11 22 33 44 55 66 77 88
End of
PASS 5
11 22 33 44 55 66 77 88
11 22 33 44 55 66 77 88
11 22 33 44 55 66 77 88
0 1 2 3 4 5 6 7 PASS 6
11 22 33 44 55 66 77 88
End of
PASS 6
11 22 33 44 55 66 77 88
11 22 33 44 55 66 77 88
0 1 2 3 4 5 6 7 PASS 7
11 22 33 44 55 66 77 88
End of
11 22 33 44 55 66 77 88 PASS 7
Now no need of next pass for only one
item (11).
0 1 2 3 4 5 6 7
11 22 33 44 55 66 77 88
Bubble Sort
Some conclusions:
To sort an array of size N we need N-1 Passes
In each pass we compare adjacent elements
(element at index j and j+1) one by one and
if they are not in correct order, we swap them.
In each pass:
for( j=0; ;j++)
?
{ Condition will depend on
Pass number
if(A[j] > A[j+1])
swap A[j] and A[j+1]
} A[0] is compared with A[1]
A[1] is compared with A[2]
A[2] is compared with A[3]
...
….
0 1 2 3 4 5 6 7
77 33 44 11 88 22 66 55
PASS 1
33 77 44 11 88 22 66 55 For j=0 to N-2
33 44 77 11 88 22 66 55 For j=0 to 6
if(A[j]>A[j+1])
swap them
33 44 11 77 88 22 66 55
33 44 11 77 88 22 66 55
33 44 11 77 22 88 66 55
33 44 11 77 22 66 88 55
33 44 11 77 22 66 55 88
0 1 2 3 4 5 6 7
PASS 2
33 44 11 77 22 66 55 88
33 44 11 77 22 66 55 88 For j=0 to N-3
For j=0 to 5
33 11 44 77 22 66 55 88 if(A[j]>A[j+1])
swap them
33 11 44 77 22 66 55 88
33 11 44 22 77 66 55 88
33 11 44 22 66 77 55 88
33 11 44 22 66 55 77 88
0 1 2 3 4 5 6 7
PASS 3
33 11 44 22 66 55 77 88
For j=0 to N-4
11 33 44 22 66 55 77 88
For j=0 to 4
if(A[j]>A[j+1])
swap them
11 33 44 22 66 55 77 88
11 In33
Pass 122 44 66N-2 55 77 88
j=0 to
In Pass 2 j=0 to N-3
In
11 33 Pass 3 j=0 to
22 44 66 55N-4 77 88
…
In Pass N-1 j=0 to 0
11 33 22 44 55 66 77 88
Bubble Sort
Since there are N-1 Passes
for(i=1;
We will use a for loop for these passes, and this loop i<=N-1;i++)
will run N-1 times
for(i=1;i<=N-1;i++) {
{
for(j=0; j<=N-1-i; j++)
} {
When i=1 Pass 1 will be executed if(a[j] > a[j+1])
When i=2 Pass 2 will be executed {
…
When i=N-1 Pass N-1 will be executed
swap them
}
In Pass 1 j=0 to N-2 i=1 }
In Pass 2 j=0 to N-3 i=2 }
In Pass 3 j=0 to N-4 i=3
…
j=0 to N-1-i
In Pass N-1 j=0 to 0 i=N-1