UNIT FOUR

FUNDAMENTALS OF PROGRAMMING
Content
• Pointers:
• Pointer and address arithmetic,
• Pointer operations and declarations,
• Pointer and arrays,
• Pointer to structure.
• Call by value,
• Call by reference.
• Dynamic memory allocation.
• Sorting and searching algorithms:
• Selection sort,
• Bubble sort,
• Insertion sort,
• Linear and binary search.
 Pointers
Pointer is a special variable that can store some address.
Syntax for declaring pointer variable
Examples
Need of address of operator (&)
Like
Important points
Value of operator • Value of operator/indirection operator/dereference
operator is an operator that is used to access the
(*) value stored at the location pointed by the pointer.
We can also change the value of the object by the pointer.
Important point
One more point
Example: Incrementing and decrementing pointers

int arr[5] = {1, 2, 3, 4, 5};

int *ptr = &arr[0]; // Pointer to the first element of arr

ptr++; // Incrementing pointer

printf("Next element: %d\n", *ptr); // Outputs: 2

ptr--; // Decrementing pointer

printf("Previous element: %d\n", *ptr); // Outputs: 1

Pointer and Arrays

Arrays in C/C++ can be accessed using pointers.

Arrays and pointers are closely related in C/C++.

Example: Accessing array elements using pointers

int arr[5] = {10, 20, 30, 40, 50};

int *ptr = arr; // Pointer to the first element of arr

printf("First element: %d\n", *ptr); // Outputs: 10

ptr++; // Moving to the next element

printf("Second element: %d\n", *ptr); // Outputs: 20

Pointer to Structure

• Pointers can also be used with structures in C/C++.

• They allow efficient manipulation and passing of structures.

• Structures and unions are user-defined data types that allow storing different types of
data under a single name.

• Structures allocate memory for each member individually, while unions allocate
memory that is the size of the largest member.
 Structure is the best solution for such problems

• Structure is user defined data type that can be used to group elements of different types into a
single type.
Example: Using a pointer to access structure
members

struct Point {
int x;
int y;
};

struct Point p1 = {5, 10};

struct Point *ptr = &p1; // Pointer to struct Point

printf("Coordinates: (%d, %d)\n", ptr->x, ptr->y); // Accessing structure members using pointer
Searching algorithms
Linear search

Is the simplest search algorithm. It works by checking each element in a

list one by one until it finds the element it is looking for. Linear search is

not very efficient for large lists, but it can be effective for small lists.
Example
#include <stdio.h>
// Function to perform linear search
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // Return the index if key is found
}
}
return -1; // Return -1 if key is not found
}
int main() {
int arr[] = {12, 45, 23, 6, 78, 54, 39};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 78;
// Perform linear search
int index = linearSearch(arr, n, key);
if (index != -1) {
printf("Element found at index: %d\n", index);
} else {
printf("Element not found\n");
}
return 0;
}
Binary search

• Is a more efficient search algorithm than linear search. It works by

dividing the list in half and then searching the half that contains the

element it is looking for. Binary search can be used to search sorted

lists of any size.

Example
#include <stdio.h>
// Function to perform binary search
int main() {
int binarySearch(int arr[], int left, int right, int key) { int arr[] = {6, 12, 23, 45, 54, 78, 39};
while (left <= right) { int n = sizeof(arr) / sizeof(arr[0]);
int mid = left + (right - left) / 2; int key = 78;
// Check if key is present at mid
if (arr[mid] == key) { // Perform binary search (array must
return mid; be sorted)
} int index = binarySearch(arr, 0, n - 1,
// If key is greater, ignore left half
key);
if (arr[mid] < key) {
left = mid + 1; if (index != -1) {
} printf("Element found at index:
// If key is smaller, ignore right half %d\n", index);
else { } else {
right = mid - 1;
} printf("Element not found\n");
} }
// Key not found return 0;
return -1;
} }
Sorting Algorithms
Merge sort

• Is a sorting algorithm that works by dividing a list into two halves,

sorting each half, and then merging the two sorted halves

together. Merge sort is a very efficient sorting algorithm and can be

used to sort lists of any size.

 Example
#include <stdio.h> // Copy the remaining elements of L[], if any
while (i < n1) {
int main() {
// Function to merge two subarrays arr[left..mid] and arr[k] = L[i]; int arr[] = {12, 11, 13, 5, 6, 7};
arr[mid+1..right] i++; int n = sizeof(arr) / sizeof(arr[0]);
void merge(int arr[], int left, int mid, int right) { k++;
int n1 = mid - left + 1; }
int n2 = right - mid; printf("Original array: ");
// Copy the remaining elements of R[], if any
while (j < n2) {
for (int i = 0; i < n; i++) {
// Create temporary arrays arr[k] = R[j]; printf("%d ", arr[i]);
int L[n1], R[n2]; j++; }
k++; printf("\n");
// Copy data to temporary arrays L[] and R[] }
for (int i = 0; i < n1; i++) { }
}
L[i] = arr[left + i]; // Perform merge sort
// Function to perform merge sort on array mergeSort(arr, 0, n - 1);
for (int j = 0; j < n2; j++) { arr[left..right]
R[j] = arr[mid + 1 + j]; void mergeSort(int arr[], int left, int right) {
} if (left < right) {
int mid = left + (right - left) / 2;
printf("Sorted array: ");
// Merge the temporary arrays back into arr[left..right] for (int i = 0; i < n; i++) {
int i = 0, j = 0, k = left; // Sort first and second halves printf("%d ", arr[i]);
while (i < n1 && j < n2) { mergeSort(arr, left, mid); }
if (L[i] <= R[j]) { mergeSort(arr, mid + 1, right);
arr[k] = L[i]; printf("\n");
i++; // Merge the sorted halves
merge(arr, left, mid, right);
} else {
} return 0;
arr[k] = R[j]; } }
j++;
}
k++;
}
Selection sort

• Is a sorting algorithm that works by finding the smallest element in a

list and then swapping it with the first element in the list. Selection

sort is a simple sorting algorithm, but it is not very efficient for large

lists.
1 2

5
3 4
 Example
#include <stdio.h> int main() {
int arr[] = {64, 25, 12, 22, 11};
// Function to perform selection sort int n = sizeof(arr) / sizeof(arr[0]);
void selectionSort(int arr[], int n) { printf("Original array: ");
for (int i = 0; i < n - 1; i++) { for (int i = 0; i < n; i++) {
int minIndex = i; printf("%d ", arr[i]);
// Find the index of the smallest element in the unsorted }
part of the array printf("\n");
for (int j = i + 1; j < n; j++) { // Perform selection sort
if (arr[j] < arr[minIndex]) { selectionSort(arr, n);
minIndex = j;
} printf("Sorted array: ");
} for (int i = 0; i < n; i++) {
// Swap the smallest element with the first element of printf("%d ", arr[i]);
the unsorted part }
int temp = arr[i]; printf("\n");
arr[i] = arr[minIndex];
arr[minIndex] = temp; return 0;
} }
}
Insertion sort

• Is a sorting algorithm that works by inserting each element of a list

into its correct position in the sorted list. Insertion sort is a simple

sorting algorithm, but it is not very efficient for large lists.

 Example
#include <stdio.h>
int main() {
// Function to perform insertion sort int arr[] = {12, 11, 13, 5, 6};
void insertionSort(int arr[], int n) { int n = sizeof(arr) / sizeof(arr[0]);
int i, key, j; printf("Original array: ");
for (i = 1; i < n; i++) { for (int i = 0; i < n; i++) {
key = arr[i]; printf("%d ", arr[i]);
j = i - 1; }
printf("\n");
// Move elements of arr[0..i-1], that are greater
than key, to one position ahead of their current position // Perform insertion sort
while (j >= 0 && arr[j] > key) { insertionSort(arr, n);
arr[j + 1] = arr[j]; printf("Sorted array: ");
j = j - 1; for (int i = 0; i < n; i++) {
} printf("%d ", arr[i]);
arr[j + 1] = key; }
} printf("\n");
}
return 0;
}
Bubble sort

• Is the simplest sorting algorithm that works by repeatedly

swapping the adjacent elements if they are in the wrong order.

This algorithm is not suitable for large data sets as its average

and worst-case time complexity is quite high.

QuickSort

• is a sorting algorithm based on the divide and conquer

algorithm that picks an element as a pivot and partitions the

given array around the picked pivot by placing the pivot in its

correct position in the sorted array.

Important Point

• The best sorting and searching algorithm to use will depend on the

specific needs of the application. For example, if the list is small,

linear search may be the best option. If the list is large and sorted,

binary search may be the best option. If the list is large and not

sorted, merge sort or quick sort may be the best option.