23CS213I PROGRAMMING FOR PROBLEM SOLVING IN C & C++

UNIT II
ARRAYS AND STRINGS
ARRAYS - INITIALIZATION - DECLARATION
An array in C is a fixed-size collection of similar data items stored in contiguous
memory locations. It can be used to store the collection of primitive data types such as int, char,
float, etc., and also derived and user-defined data types such as pointers, structures, etc.

C ARRAY DECLARATION
In C, we have to declare the array like any other variable before using it. We can declare
an array by specifying its name, the type of its elements, and the size of its dimensions. When
we declare an array in C, the compiler allocates the memory block of the specified size to the
array name.
Syntax of Array Declaration
data_type array_name [size];
or
data_type array_name [size1] [size2]...[sizeN];
where N is the number of dimensions.

The C arrays are static in nature, i.e., they are allocated memory at the compile time.
Example of Array Declaration
// C Program to illustrate the array declaration
#include <stdio.h>
int main()
{
// declaring array of integers
int arr_int[5];
// declaring array of characters
char arr_char[5];
return 0;
}

C ARRAY INITIALIZATION
Initialization in C is the process to assign some initial value to the variable. When the
array is declared or allocated memory, the elements of the array contain some garbage value.
So, we need to initialize the array to some meaningful value. There are multiple ways in which
we can initialize an array in C.
1. Array Initialization with Declaration
In this method, we initialize the array along with its declaration. We use an initializer
list to initialize multiple elements of the array. An initializer list is the list of values enclosed
within braces { } separated b a comma.
data_type array_name [size] = {value1, value2, ... valueN};
2. Array Initialization with Declaration without Size
If we initialize an array using an initializer list, we can skip declaring the size of the
array as the compiler can automatically deduce the size of the array in these cases. The size of
the array in these cases is equal to the number of elements present in the initializer list as the
compiler can automatically deduce the size of the array.
data_type array_name[] = {1,2,3,4,5};
The size of the above arrays is 5 which is automatically deduced by the compiler.
3. Array Initialization after Declaration (Using Loops)
We initialize the array after the declaration by assigning the initial value to each element
individually. We can use for loop, while loop, or do-while loop to assign the value to each
element of the array.
for (int i = 0; i < N; i++) {
array_name[i] = valuei;
}
Example of Array Initialization in C
// C Program to demonstrate array initialization
#include <stdio.h>
int main()
{
// array initialization using initialier list
int arr[5] = { 10, 20, 30, 40, 50 };
// array initialization using initializer list without
// specifying size
int arr1[] = { 1, 2, 3, 4, 5 };
// array initialization using for loop
float arr2[5];
for (int i = 0; i < 5; i++) {
arr2[i] = (float)i * 2.1;
}
return 0;
}
ACCESS ARRAY ELEMENTS
We can access any element of an array in C using the array subscript operator [ ] and
the index value i of the element.
array_name [index];
One thing to note is that the indexing in the array always starts with 0, i.e., the first element is
at index 0 and the last element is at N – 1 where N is the number of elements in the array.

Example of Accessing Array Elements using Array Subscript Operator

// C Program to illustrate element access using array
// subscript
#include <stdio.h>
int main()
{
// array declaration and initialization
int arr[5] = { 15, 25, 35, 45, 55 };
// accessing element at index 2 i.e 3rd element
printf("Element at arr[2]: %d\n", arr[2]);
// accessing element at index 4 i.e last element
printf("Element at arr[4]: %d\n", arr[4]);
// accessing element at index 0 i.e first element
printf("Element at arr[0]: %d", arr[0]);
return 0;
}

Output
Element at arr[2]: 35
Element at arr[4]: 55
Element at arr[0]: 15
TYPES OF ARRAY IN C
There are two types of arrays based on the number of dimensions it has. They are as follows:
1. One Dimensional Arrays (1D Array)
2. Two Dimensional Arrays (2D Array)
3. Multidimensional Arrays

ONE DIMENSIONAL ARRAY

One Dimensional Array in C

The One-dimensional arrays, also known as 1-D arrays in C are those arrays that have only one
dimension.
Syntax of 1D Array in C
array_name [size];

Example program for 1D Array

#include<stdio.h>
int main(){
int i=0;
int marks[5]={20,30,40,50,60};//declaration and initialization of array
//traversal of array
for(i=0;i<5;i++){
printf("%d \n",marks[i]);
}
return 0;
}
Output
20
30
40
50
60
 TWO DIMENSIONAL ARRAYS

Two-Dimensional Array in C

A Two-Dimensional array or 2D array in C is an array that has exactly two

dimensions. They can be visualized in the form of rows and columns organized in a two-
dimensional plane.
Syntax of 2D Array in C
array_name[size1] [size2];
Here,
• size1: Size of the first dimension.
• size2: Size of the second dimension.

Example of 2D Array in C
// C Program to illustrate 2d array
#include <stdio.h>
int main()
{
// declaring and initializing 2d array
int arr[2][3] = { 10, 20, 30, 40, 50, 60 };
printf("2D Array:\n");
// printing 2d array
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
 printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
Output
2D Array:
10 20 30
40 50 60

STRING - STRING PROGRAMS

In C programming, a string is a sequence of characters terminated with a null
character \0. For example:
char c[] = "c string";
When the compiler encounters a sequence of characters enclosed in the double quotation
marks, it appends a null character \0 at the end by default.

Memory Diagram
How to declare a string?
Here's how you can declare strings:
char s[5];

String Declaration in C
Here, we have declared a string of 5 characters.
How to initialize strings?
You can initialize strings in a number of ways.
char c[] = "abcd";
char c[50] = "abcd";
char c[] = {'a', 'b', 'c', 'd', '\0'};
char c[5] = {'a', 'b', 'c', 'd', '\0'};
 String Initialization in C
Let's take another example:
char c[5] = "abcde";
Here, we are trying to assign 6 characters (the last character is '\0') to a char array having 5
characters. This is bad and you should never do this.
Read String from the user
You can use the scanf() function to read a string.
The scanf() function reads the sequence of characters until it encounters whitespace (space,
newline, tab, etc.).
Example 1: scanf() to read a string
#include <stdio.h>
int main()
{
char name[20];
printf("Enter name: ");
scanf("%s", name);
printf("Your name is %s.", name);
return 0;
}
Output
Enter name: Dennis Ritchie
Your name is Dennis.
Even though Dennis Ritchie was entered in the above program, only "Dennis" was stored in
the name string. It's because there was a space after Dennis.
Also notice that we have used the code name instead of &name with scanf().
scanf("%s", name);
This is because name is a char array, and we know that array names decay to pointers in C.
Thus, the name in scanf() already points to the address of the first element in the string, which
is why we don't need to use &.
STRING FUNCTIONS

Commonly Used String Functions

DEMONSTRATING COMMON STRING FUNCTIONS
#include <stdio.h>
#include <string.h>
int main()
{
char str1[50] = "Hello, world!";
char str2[50] = "Welcome to C programming!";
// strlen() - Find the length of a string
int len = strlen(str1);
printf("Length of str1: %d\n", len);
// strcpy() - Copy one string to another
strcpy(str2, str1);
printf("Copied str1 to str2: %s\n", str2);
// strcat() - Concatenate two strings
strcat(str1, " How are you?");
printf("Concatenated string: %s\n", str1);
// strcmp() - Compare two strings
int result = strcmp(str1, str2);
if (result == 0) {
printf("str1 and str2 are equal\n");
} else {
printf("str1 and str2 are different\n");
}
// strchr() - Find the first occurrence of a character
char *ptr = strchr(str1, 'w');
if (ptr) {
printf("First occurrence of 'w' in str1: %s\n", ptr);
} else {
printf("Character 'w' not found in str1\n");
}
return 0;
}
OUTPUT

Length of str1: 13
Copied str1 to str2: Hello, world!
Concatenated string: Hello, world! How are you?
str1 and str2 are different
First occurrence of 'w' in str1: world! How are you?
 SORTING
Sorting is the process of arranging elements in a list or array in a specific order, typically
in ascending or descending order. Sorting is a fundamental problem in computer science and
has many applications in areas such as searching, data compression, and data analysis.
There are many sorting algorithms that can be used to sort an array. Some of the most popular
algorithms include:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
1. BUBBLE SORT:
This is a simple sorting algorithm that repeatedly steps through the list, compares
adjacent elements, and swaps them if they are in the wrong order.
Algorithm
Repeat as many times as there are items in the list
Repeat for each success pair of elements
If this element > next element then swap elements

Program for bubble sort

/* Bubble sort code */
#include <stdio.h>
int main()
{
int array[100], n, c, d, swap;
 printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\t", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 0 ; c < n - 1; c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1]) /* For decreasing order use '<' instead of '>' */
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\t", array[c]);
return 0;
}

Output:
Enter number of elements 4
Enter 4 integers Sorted array:
11 10 28 25
Sorted list in ascending order
10 11 25 28

SELECTION SORT:
This algorithm sorts an array by repeatedly finding the minimum element from the
unsorted part of the array and putting it at the beginning.
Selection Sort Algorithm
selectionSort(array, size)
repeat (size - 1) times
 set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
end selectionSort

// Program for Selection sort in C

#include <stdio.h>
int main()
{
int array[100], n, c, d, position, t;
 printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 0; c < (n - 1); c++) // finding minimum element (n-1) times
{
position = c;
for (d = c + 1; d < n; d++)
{
if (array[position] > array[d])
position = d;
}
if (position != c)
{
t = array[c];
array[c] = array[position];
array[position] = t;
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}
OUTPUT
Enter number of elements 4
Enter 4 integers Sorted array:
11 10 28 25
Sorted list in ascending order
10 11 25 28

INSERTION SORT:
This algorithm builds the final sorted array one item at a time, by inserting each item in
the correct position in the array.
Algorithm
The simple steps of achieving the insertion sort are listed as follows -
Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
Step2 - Pick the next element, and store it separately in a key.
Step3 - Now, compare the key with all elements in the sorted array.
Step 4 - If the element in the sorted array is smaller than the current element, then move to the
next element. Else, shift greater elements in the array towards the right.
Step 5 - Insert the value.
Step 6 - Repeat until the array is sorted.
Working of Insertion sort Algorithm
To understand the working of the insertion sort algorithm, let's take an unsorted array.
It will be easier to understand the insertion sort via an example.
Let the elements of array are -

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending order. So, for
now, 12 is stored in a sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25. Along with
swapping, insertion sort will also check it with all elements in the sorted array.
For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12. Hence, the
sorted array remains sorted after swapping.

Now, two elements in the sorted array are 12 and 25. Move forward to the next elements that
are 31 and 8.
Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.

So, swap them.

Now, elements 12 and 8 are unsorted.

So, swap them too.

Now, the sorted array has three items that are 8, 12 and 25. Move to the next items that are 31
and 32.

Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.

Move to the next elements that are 32 and 17.

17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted.

Program to perform insertion sort
#include <stdio.h>
void insert(int a[], int n) /* function to sort an array with insertion sort */
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position
ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}
void printArr(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
Output:

MERGE SORT:
This algorithm divides the array into two halves, sorts each half separately, and then
merges the two halves together to form a sorted array.
• Declare left variable to 0 and right variable to n-1
• Find mid by medium formula. mid = (left+right)/2
• Call merge sort on (left,mid)
• Call merge sort on (mid+1,rear)
• Continue till left is less than right
• Then call merge function to perform merge sort.
To know the functioning of merge sort, lets consider an array arr[] = {38, 27, 43, 3, 9, 82, 10}
• At first, check if the left index of array is less than the right index, if yes then calculate
its mid point

Now, as we already know that merge sort first divides the whole array iteratively into equal
halves, unless the atomic values are achieved.
• Here, we see that an array of 7 items is divided into two arrays of size 4 and 3
respectively.
 Now, again find that is left index is less than the right index for both arrays, if found yes, then
again calculate mid points for both the arrays.

Now, further divide these two arrays into further halves, until the atomic units of the array is
reached and further division is not possible.

After dividing the array into smallest units, start merging the elements again based on
comparison of size of elements
• Firstly, compare the element for each list and then combine them into another list in a
sorted manner.

After the final merging, the list looks like this:

The following diagram shows the complete merge sort process for an example array {38, 27,
43, 3, 9, 82, 10}.
If we take a closer look at the diagram, we can see that the array is recursively divided into two
halves till the size becomes
• Once the size becomes 1, the merge processes come into action and start merging
arrays back till the complete array is merged.

// Merge sort in C
#include <stdio.h>
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {
// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
 // Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;
// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
// When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// m is the point where the array is divided into two subarrays
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted subarrays
merge(arr, l, m, r);
}
}
// Print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
printf("Sorted array: \n");
printArray(arr, size);
}
Output
Sorted array : 1 5 6 9 10 12
QUICK SORT:
This algorithm picks an element as a pivot and partitions the array around the pivot,
such that elements smaller than the pivot are on one side and elements larger than the pivot are
on the other side. It then recursively sorts the two sub-arrays.
The basic idea behind QuickSort is to select a “pivot” element from the array and partition the
other elements into two sub-arrays according to whether they are less than or greater than the
pivot. The sub-arrays are then sorted recursively. This process of partitioning and sorting
continues until the entire array is sorted.

// C Program to sort an array using qsort() function in C

#include <stdio.h>
#include <stdlib.h>
// Comparison function
int compare(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
int main()
{
int arr[] = { 4, 2, 5, 3, 1 };
int n = sizeof(arr) / sizeof(arr[0]);

qsort(arr, n, sizeof(int), compare);

printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
}
return 0;
}
C Program for Quick Sort
// C program to implement Quick Sort Algorithm
#include<stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
}
Output:
How many elements are u going to enter?: 10
Enter 10 elements: 2 3 5 7 1 9 3 8 0 4
Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9

SEARCHING
Searching algorithms are methods or procedures used to find a specific item or element
within a collection of data. These algorithms are widely used in computer science and are
crucial for tasks like searching for a particular record in a database, finding an element in a
sorted list, or locating a file on a computer.
These are some commonly used searching algorithms:
1. Linear Search: In this simple algorithm, each element in the collection is sequentially
checked until the desired item is found, or the entire list is traversed. It is suitable for
small-sized or unsorted lists, but its time complexity is O(n) in the worst case.
2. Binary Search: This algorithm is applicable only to sorted lists. It repeatedly compares
the middle element of the list with the target element and narrows down the search
range by half based on the comparison result. Binary search has a time complexity of
O(log n), making it highly efficient for large sorted lists.
LINEAR SEARCH ALGORITHM
Linear search is also called as sequential search algorithm. It is the simplest searching
algorithm. 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.
The steps used in the implementation of Linear Search are listed as follows -
o First, we have to traverse the array elements using a for loop.
o In each iteration of for loop, compare the search element with the current array
element, and -
o If the element matches, then return the index of the corresponding array
element.
o If the element does not match, then move to the next element.
o If there is no match or the search element is not present in the given array, return -1.
Working of Linear search
Now, let's see the working of the linear search Algorithm.
To understand the working of linear search algorithm, let's take an unsorted array. It will be
easy to understand the working of linear search with an example.
Let the elements of array are -

Let the element to be searched is K = 41

Now, start from the first element and compare K with each element of the array.

The value of K, i.e., 41, is not matched with the first element of the array. So, move to the next
element. And follow the same process until the respective element is found.
Now, the element to be searched is found. So algorithm will return the index of the element
matched.
Program: Write a program to implement linear search in C language.
#include <stdio.h>
int linearSearch(int a[], int n, int val) {
// Going through array sequencially
for (int i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1;
 }
int main() {
int a[] = {70, 40, 30, 11, 57, 41, 25, 14, 52}; // given array
int val = 41; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = linearSearch(a, n, val); // Store result
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", val);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
}
Output

BINARY SEARCH ALGORITHM

• Binary search is the search technique that works efficiently on sorted lists. Hence, to
search an element into some list using the binary search technique, we must ensure that
the list is sorted.
• 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.
Implementation of Binary Search
• Take a sorted array (mandatory)
• Find mid using formula m = (l+r)/2
• If the item to be searched is greater than mid
o Check the right subarray
• If the item to be searched is lesser than the mid
 o Check the left subarray
• If mid element == item return with the position where found
• Else keep doing the above steps until you violate the bounds of the array
Methods Discussed
We are going to be discussing two methods here –
• Method 1: Recursive Approach
• Method 2: Iterative Approach

Binary Search in C (Recursive Approach)

#include <stdio.h>
int binarySearch(int arr[], int left, int right, int item){
if (right >= left){
// calculation of new mid
int mid = left + (right - left)/2;
// returns position where found
if (arr[mid] == item)
return mid;
// goes to recursive calls in left half
if (arr[mid] > item)
 return binarySearch(arr, left, mid-1, item);
// goes to recursive calls in right half
else
return binarySearch(arr, mid+1, right, item);
}
// if element is not found we return -1
else
return -1;
}
int main(){
// array needs to be sorted to impliment binary search
int arr[8] = {10, 20, 30, 40, 50, 60, 70, 80};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 70;
int position = binarySearch(arr, 0, n-1, item);
if(position == -1)
printf("%d Not Found",item);
else
printf("%d Found at index : %d",item, position);
}
Output:-
70 Found at index : 6

Binary Search in C (Iterative Approach)

#include <stdio.h>
int binarySearch(int arr[], int l, int r, int item)
{
while (l <= r) {
int mid = l + (r - l) / 2;
// if item is at mid
if (arr[mid] == item)
 return mid;
// If item greater, ignore left half, consider only right half
if (arr[mid] < item)
l = mid + 1;
// If item is smaller, ignore right half, consider only left half
else
r = mid - 1;
}

// if we are able to reach here // means item wasn't present

return -1;
}
int main(void)
{
// array needs to be sorted to impliment binary search
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 30;
int position = binarySearch(arr, 0, n - 1, item);
if(position == -1)
printf("%d Not Found",item);
else
printf("%d Found at index : %d",item, position);
return 0;
}
Output
30 Found at index : 2