Course: Fundamentals of Programming

Course Code: 24CS01TP0101

UNIT-4

P ro f . N I K I TA K ATA R IYA
D E PA RTM EN T O F C S E
R A M D EOBA BA U N I V E R S IT Y, N A G P U R
Contents
➢Arrays: 1-D, 2-D
➢Searching
➢Basic Sorting Algorithms (Bubble, Insertion and Selection)
➢ Pointers to the array
➢Command line arguments
Derived Data type
➢Data types that are derived from fundamental data types are called derived
data types.
➢Derived data types do not create new data types. Instead, they add some
functionality to the existing data types.
➢Derived data types are derived from the primitive data types by adding some
extra relationships with the various elements of the primary data types.
➢The derived data type can be used to represent a single value or multiple
values.
Given below are the various derived data types used in C:

1. Arrays: An array is an ordered sequence of finite data items of the same data
type that share a common name.
2. pointers: A pointer is a special type of variable used to hold the address of
another variable.
3. Functions: A function is a self-contained block of one or more statements with a
name.
4. Structures: A structure is a collection of different data type items stored in a
contiguous memory allocation.
5. Unions: A union is similar to a structure where the memory allocated to the
largest data type is reused for other types in the group.
Array
➢An array is defined as the collection of similar type of data items stored at contiguous memory
locations.
➢Arrays are the derived data type in C programming language which can store the primitive type
of data such as int, char, double, float, etc.
➢It also has the capability to store the collection of derived data types, such as pointers,
structure, etc.
➢ The array is the simplest data structure where each data element can be randomly accessed by
using its index number.
What is an Array?
➢ An array is a fixed-size sequenced collection of elements of the same data
type.
➢ It is simply a grouping of like-type data. In its simplest form, an array can be used
to represent a list of numbers, or a list of names.
➢ Some examples where the concept of array can be used are as under:
➢ List of temperatures recorded every hour in a day, or a month, or a year.
➢ List of employees in an organization.

➢ List of products and their cost sold by a store.

➢ Test scores of a class of students.

➢ List of customers and their telephone numbers. Etc.

"We have a list of 1000 students' marks of an integer type. If using
the basic data type (int), we will declare something like the

Arrays
following…"

int studMark1, studMark2, ..., studMark1000;

▪ Can you imagine how long we have to write the declaration

part by using normal variable declaration?
int main(void)
{
int studMark1, studMark2, studMark3, studMark4, …, …,
studMark998, stuMark999, studMark1000;
…
…
return 0;
}
Arrays
➢By using an array, we just declare like this,
➢int studMark[1000];
➢This will reserve 1000 contiguous memory locations for storing the students’ marks.
➢Graphically, this can be depicted as in the following figure.
Arrays
➢This absolutely has simplified our declaration of the variables.
➢We can use index or subscript to identify each element or location in the memory.
➢Hence, if we have an index of jIndex, studMark[jIndex] would refer to the jIndexth
element in the array of studMark.
➢For example, studMark[0] will refer to the first element of the array.
➢Thus by changing the value of jIndex, we could refer to any element in the array.
➢So, array has simplified our declaration and of course, manipulation of the data.
Understanding Array
Properties of Array
➢The array contains the following properties.
➢Each element of an array is of same data type and carries the same size, i.e., int = 2 bytes.
➢Elements of the array are stored at contiguous memory locations where the first element is
stored at the smallest memory location.
➢Elements of the array can be randomly accessed since we can calculate the address of each
element of the array with the given base address and the size of the data element.
Advantages of C Array
1) Code Optimization: Less code to the access the data.
2) Ease of traversing: By using the for loop, we can retrieve the elements of an
array easily.
3) Ease of sorting: To sort the elements of the array, we need a few lines of code
only.
4) Random Access: We can access any element randomly using the array.
Disadvantage of C Array
1) Fixed Size: Whatever size, we define at the time of declaration of the array, we can't exceed
the limit.
Declaration of C Array
➢We can declare an array in the c language in the following way.

data_type array_name[array_size];
➢Now, let us see the example to declare the array.
int marks[5];

➢Here, int is the data_type, marks are the array_name, and 5 is the array_size.
Initialization of C Array
➢The simplest way to initialize an array is by using the index of each element. We can initialize
each element of the array by using the index. Consider the following example.

marks[0]=80;//initialization of array
marks[1]=60;
marks[2]=70;
marks[3]=85;
marks[4]=75;
C Array: Declaration with Initialization
We can initialize the c array at the time of declaration as
follows:
int marks[5]={20,30,40,50,60};
In such case, there is no requirement to define the size. So it
may also be written as the following code.
int marks[]={20,30,40,50,60};
ARRAY
➢ An Array is a derived data type
➢ Based on the basis of dimensions there are three types of array :
1. One - dimensional Arrays
2. Two - dimensional Arrays
3. Multi - dimensional Arrays
One Dimensional Array: Declaration
▪Dimension refers to the array's size, which is how big the array is.
▪A single or one dimensional array declaration has the following form,

◦ array_element_data_type array_name[array_size];

▪Here, array_element_data_type define the base type of the array, which is the
type of each element in the array.
▪array_name is any valid C / C++ identifier name that obeys the same rule for the
identifier naming.
▪array_size defines how many elements the array will hold.
One Dimensional Array
Its possible to initialize an array during declaration.

For example: int mark[5] = {9,4,6,3,5};

Another method of initialize array during declaration
int mark[ ] ={9,4,6,3,5};

Here,
mark[0] is equal to 9
mark[1] is equal to 4
mark[2] is equal to 6
mark[3] is equal to 3
mark[4] is equal to 5
One Dimensional Array- Initialization
▪Initialization of an array of type char for holding strings may take the following form,
▪ char array_name[size] = "string_lateral_constant";

▪For example, the array chVowel in the previous example could have been written more
compactly as follows,
char chVowel[6] = "aeiou";

▪When the value assigned to a character array is a string (which must be enclosed in double
quotes), the compiler automatically supplies the NULL character but we still have to reserve
one extra place for the NULL.
▪For unsized array (variable sized), we can declare as follow,
◦ char chName[ ] = "Mr. Dracula";

▪C compiler automatically creates an array which is big enough to hold all the initializer.
Run time initialization
An array can also be explicitly initialized at run time.
For example consider the following segment of a c program.

for(i=0;i<10;i++)
{
scanf(“%d”, &x[i]);
}
In the run time initialization of the arrays looping statements are almost compulsory.

Looping statements are used to initialize the values of the arrays one by one using assignment
operator or through the keyboard by the user.
One dimensional Array Program
#include<stdio.h>
void main()
{
int arr[5];
printf(“Enter 5 numbers to store them in array \n”);
for(i=0;i<5;i++)
{
scanf(“%d”, &arr[i]);
}
printf(“Element in the array are: \n”);
for(i=0;i<5;i++)
{
printf(“Element stored at a[%d] = %d \n”, i, arr[i]);
}
}
TASK Example
Program example 1: Sum of array’s element
▪Arrays allow programmers to group related items of the same data type in
one variable.
▪However, when referring to an array, one has to specify not only the array or
variable name but also the index number of interest.
▪Notice the array's element which is not initialized is set to 0 automatically.
Program example : Searching the smallest value
#include<stdio.h>
void main() {
int a[30], i, num, smallest;
printf("\nEnter no of elements :");
scanf("%d", &num);
for (i = 0; i < num; i++) //Read n elements in an array
scanf("%d", &a[i]);
smallest = a[0]; //Consider first element as smallest
for (i = 0; i < num; i++)
{ Output
if (a[i] < smallest) Enter no of elements : 5
{ 11 44 22 55 99
smallest = a[i]; Smallest Element : 11
}
}
// Print out the Result
printf("\n smallest Element : %d", smallest);
}
TASK Program example 3: Searching the biggest value. By
modifying the previous example we can search the
biggest value.
TASK Program example 4: Searching the location for the
given value in an array
Linear and Binary
Search
Linear Search
➢A linear search, also known as a sequential search, is a method of finding an element within a
list.
➢In Linear search, we simply traverse the list completely and match each element of the list with
the item whose location is to be found.
➢If the match is found, then the location of the item is returned; otherwise, the algorithm
returns NULL.
 Linear Search- Program
#include <stdio.h> for (i = 0; i < n; i++)
void main() {
{ if (array[i] == search) /* If required element is found */
int array[20], search, i, n; {
printf("Enter number of elements in array\n"); printf("%d is present at location %d.\n", search, i+1);
scanf("%d", &n); break;
printf("Enter %d integer(s)\n", n); }
for (i = 0; i < n; i++) }
scanf("%d", &array[i]); if (i == n)
printf("Enter a number to search\n"); printf("%d isn't present in the array.\n", search);
scanf("%d", &search); }
Linear Search- Program
Program example : Searching the location for the given value in an array
Binary Search
➢A Binary Search is used to search an element in a sorted array.
➢A binary search technique works only on a sorted array, so an array must be
sorted to apply binary search on the array.
➢Binary search follows the divide and conquer approach in which the list is
divided into two halves, and the item is compared with the middle element of
the list.
➢If the match is found then, the location of the middle element is returned.
➢Otherwise, we search into either of the halves depending upon the result
produced through the match.
Binary Search
Steps:
Compare x with the middle element.
If x matches with the middle element, we return the mid index.
Else If x is greater than the mid element, then x can only lie in the right half subarray after the
mid element. So we recur for the right half.
Else (x is smaller) recur for the left half.
 Program- Binary Search
#include <stdio.h> {
void main() middle=(first+last)/2;
{ if(array[middle]==search)
int i,first,last,middle,n,search,array[50]; {
printf("Enter number of elements\n"); printf("%d found at location %d.\n",search,middle+1);
scanf("%d",&n); break;
printf("Enter %d integers in sorted form\n",n); }
for(i=0;i<n;i++) else if(array[middle]<search)
scanf("%d",&array[i]); first=middle+1;
printf("Enter value to find\n"); else
scanf("%d",&search); last=middle-1;
first=0; }
last=n-1; if(first>last)
while(first<=last) printf("Not found! %d isn't present in the list.\n",search);
}
Sorting
What is sorting
A sorting algorithm is defined as an algorithm that puts the elements of a list in a certain order,
which can be either numerical order, lexicographical order, or any user-defined order.
Sorting Algorithms
➢Bubble Sort
➢Selection Sort
➢Insertion Sort
Bubble Sort
➢Bubble sort is the simplest sorting algorithm that works by repeatedly
swapping the adjacent elements if they are in wrong order.
➢In bubble sorting, consecutive adjacent pairs of elements in the array are
compared with each other.
➢If the element at the lower index is greater than the element at the higher
index, the two elements are interchanged so that the element is placed before
the bigger one. This process will continue till the list of unsorted elements
exhausts.
➢This procedure of sorting is called bubble sorting because elements ‘bubble’
to the top of the list.
➢Note that at the end of the first pass, the largest element in the list will be
placed at its proper position
"Bubbling Up" the Largest Element
Traverse a collection of elements
◦ Move from the front to the end
◦ “Bubble” the largest value to the end using pair-wise comparisons and swapping

1 2 3 4 5 6

77 42 35 12 101 5
"Bubbling Up" the Largest Element
Traverse a collection of elements
◦ Move from the front to the end
◦ “Bubble” the largest value to the end using pair-wise comparisons and swapping

1 2 3 4 5 6

42 Swap4277
77 35 12 101 5
"Bubbling Up" the Largest Element
Traverse a collection of elements
◦ Move from the front to the end
◦ “Bubble” the largest value to the end using pair-wise comparisons and swapping

42 77

1 2 3 4 5 6

42 7735 Swap35
77 12 101 5
"Bubbling Up" the Largest Element
Traverse a collection of elements
◦ Move from the front to the end
◦ “Bubble” the largest value to the end using pair-wise comparisons and swapping

42 35 77

1 2 3 4 5 6

42 35 12 Swap 12
77 77 101 5
"Bubbling Up" the Largest Element
Traverse a collection of elements
◦ Move from the front to the end
◦ “Bubble” the largest value to the end using pair-wise comparisons and swapping

42 35 12 77

1 2 3 4 5 6

42 35 12 77 101 5

No need to swap
"Bubbling Up" the Largest Element
Traverse a collection of elements
◦ Move from the front to the end
◦ “Bubble” the largest value to the end using pair-wise comparisons and swapping

1 2 3 4 5 6

42 35 12 77 1015 Swap 101

5
"Bubbling Up" the Largest Element
Traverse a collection of elements
◦ Move from the front to the end
◦ “Bubble” the largest value to the end using pair-wise comparisons and swapping

1 2 3 4 5 6

42 35 12 77 5 101

Largest value correctly placed

Items of Interest
Notice that only the largest value is correctly placed
All other values are still out of order
So we need to repeat this process

1 2 3 4 5 6

42 35 12 77 5 101

Largest value correctly placed

“Bubbling” All the Elements
1 2 3 4 5 6
42 35 12 77 5 101

1 2 3 4 5 6
35 12 42 5 77 101

1 2 3 4 5 6
12 35 5 42 77 101

1 2 3 4 5 6
12 5 35 42 77 101

1 2 3 4 5 6
5 12 35 42 77 101
Working
•Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not
swap them.
•Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm
needs one whole pass without any swap to know it is sorted.
•Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Fourth Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
 TASK
Bubble Sort
Consider the array elements =
{30,52,29,87,63,27,19,54}
Use Bubble sort to sort the array. How many passes
will the algorithm perform?

N-1
passes
Bubble Sort
Bubble Sort - Complexity
Time Complexities:
•Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending order then, the
worst case occurs.
•Best Case Complexity: O(n)
If the array is already sorted, then there is no need for sorting.
•Average Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither ascending
nor descending).
Space Complexity:
Space complexity is O(1) because an extra variable temp is used for swapping.
Selection sort algorithm
•The selection sort algorithm sorts an array by repeatedly finding the minimum
element (considering ascending order) from unsorted part and putting it at the
beginning. The algorithm maintains two subarrays in a given array.
1)The subarray which is already sorted.
2) Remaining subarray which is unsorted.
•In every iteration of selection sort, the minimum element (considering
ascending order) from the unsorted subarray is picked and moved to the
sorted subarray.
•Following example explains the above steps:
 TASK
Selection Sort
Consider the array elements =
{39,9,81,45,90,27,72,18}
Use Selection sort to sort the array. How many
passes will the algorithm perform?

N-1
passes
 Selection Sort
#include <stdio.h> if(a[i]>a[j])
void main() {
{ c=a[i];
int i,j,c,a[50],n; a[i]=a[j];
printf("Enter number of elements\n"); a[j]=c;
scanf("%d",&n);
}
printf("Enter %d integers \n",n);
}
for(i=0;i<n;i++)
}
scanf("%d",&a[i]);
printf("sorted array");
for(i=0;i<n;i++)
for(i=0;i<n;i++)
{
printf("\n%d",a[i]);
for(j=i+1;j<n;j++)
}
{
Insertion Sort

To insert 12, we need to

make room for it by moving
first 36 and then 24.
Insertion Sort
Insertion Sort
Insertion Sort
Insertion Sort
input array
5 2 4 6 1 3
at each iteration, the array is divided in two sub-arrays:

left sub-array right sub-array

sorted unsorted
Insertion Sort
 Insertion Sort
#include <stdio.h> while (j >= 0 && arr[j] > key)
void main() {
{ arr[j + 1] = arr[j];
int arr[10] , n ,i, j, key; j = j - 1;
printf("Enter number of elements\n"); }
scanf("%d",&n); arr[j + 1] = key;
printf("Enter %d integers \n",n); }
for(i=0;i<n;i++) printf("Sorted array: ");
scanf("%d",&arr[i]); for (i = 0; i < n; i++)
for (i = 1; i < n; i++) {
{ printf("%d ", arr[i]);
key = arr[i]; }
j = i - 1; }
Passing Arrays to Function
 Ways to pass array to functions
➢If you want to pass a single-dimension
array as an argument in a function, you
would have to declare a formal parameter
in one of following three ways and all
three declaration methods produce
similar results because each tells the
compiler that an integer pointer is going
to be received.
➢Similarly, you can pass multi-dimensional
arrays as formal parameters.
 FUNCTIONS WITH 1D ARRAYS
➢ Possible to pass the values of an array to a function
➢ To pass an array to a called function, it is sufficient to list the name
of the array without any subscripts, and the size of the array as
arguments
➢ The call:
largest(a,n);
will pass all the elements contained in the array a of size n.
➢ The called function expecting this call must be
appropriately defined
➢ The largest function header is
float largest(float array[], int size)
 FUNCTIONS WITH 1D ARRAYS
➢ The function header(largest) is defined to take two arguments, the
array name and the size of the array to specify the number of
elements in the array

➢ The declaration of formal argument array is

float array[];

➢ The pair of brackets informs the compiler that the arguments array
is an array of numbers.
➢ It is not necessary to specify the size of the array here.`
 FUNCTIONS WITH 1D ARRAYS
Here an array is transferred as parameter to a function.
void fun(int[],int); void fun(int b[], intn)
void main() {
{ int x;
int a[5],n; ………….
…………… ………….
fun(a,n); }
……………
}
 EXAMPLE
Program for addition of array elements by passing array.

#include<stdio.h> void add(int b[],int x)

#include<conio.h> {
void add(int[],int); int sum=0,i;
void main() for(i=0;i<x;i++)
{ sum=sum+b[i];
int a[5],i,n; printf("\nThe sum is: %d",sum);
printf("\n Enter the array size: "); }
scanf("%d",&n);
printf("\n Enter the Values: "); OUTPUT:
for(i=0;i<n;i++) Enter the array size: 5 Enter
the Values:
scanf("%d",&a[i]); 1
add(a,n); 2
} 3
4
5
The sum is: 15
EXAMPLE
Program for addition of array elements by passing array as pointer.

#include<stdio.h>
void add(int *b, int x)
#include<conio.h> {
void add(int[],int b); int sum=0,i;
void main() for(i=0;i<x;i++)
{ sum=sum+b[i];
int a[5],i,n; printf("\nThe sum is: %d",sum);
}
printf("\n Enter the array size: ");
OUTPUT:
scanf("%d",&n);
Enter the array size: 5
printf("\n Enter the Values: "); Enter the Values:
for(i=0;i<n;i++) 1
scanf("%d",&a[i]); 2
add(a,n); 3
} 4
5
The sum is: 15
Points to Remember
➢Arrays are pointers
➢To pass an array as a parameter to a function, pass it as a pointer (since
it is a pointer).
➢We can pass individual array elements by call by value or reference.
However, if we pass the entire array it is call by reference as array is
pointer.
Passing individual elements of
array to a function
Call by value Call by reference
 Write the following programs
using functions
1. Create an array of N element. Write a function Count_even_odd () in C to calculate the number of
even data items and odd data items present in an array and display both the results in the calling
function.
2. Write a C program to print the sum of N elements present in an array using recursion.
Pointers and array
Instead of printing the value of each array element, print the memory
address of each array element:
void main()
{
int myNumbers[4] = {25, 50, 75, 100};
int i;
for (i = 0; i < 4; i++)
{
printf("%u\n", &myNumbers[i]);
}

}
Example1 : Pointers and array
#include <stdio.h>
int main()
{
int i, x[6], sum = 0;
printf("Enter 6 numbers: ");
for(i = 0; i < 6; ++i)
{
scanf("%d", x+i); // Equivalent to scanf("%d", &x[i]);
sum += *(x+i); // Equivalent to sum += x[i]
}
printf("Sum = %d", sum);
return 0;
}
 Example 2: Arrays and Pointers
#include <stdio.h>
int main()
{
int x[5] = {1, 2, 3, 4, 5};
int* ptr;
// ptr is assigned the address of the third element
ptr = &x[2];
printf("*ptr = %d \n", *ptr); // 3
printf("*(ptr+1) = %d \n", *(ptr+1)); // 4
printf("*(ptr-1) = %d", *(ptr-1)); // 2
return 0;
}
Program to access Array of int Pointers
 Incrementing a Pointer
➢We prefer using a pointer in our program instead of an array because the variable pointer can be incremented, unlike
the array name which cannot be incremented because it is a constant pointer.
➢The following program increments the variable pointer to access each succeeding element of the array −
Decrementing a Pointer
The same considerations apply to decrementing a pointer, which decreases its value by
the number of bytes of its data type as shown below −
HAPPY LEARNING !