Question.

1
Answer.
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:

arr[] = 27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[0...9]

// and place it at beginning

27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[1...9]

// and place it at beginning of arr[1...9]

27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[2...9]

// and place it at beginning of arr[2...9]

27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[3...9]

// and place it at beginning of arr[3...9]

27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[4...9]

// and place it at beginning of arr[4...9]

27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[5...9]

// and place it at beginning of arr[5...9]
27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[6...9]

// and place it at beginning of arr[6...9]

27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[7...9]

// and place it at beginning of arr[7...9]

27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[8...9]

// and place it at beginning of arr[8...9]

27,15,12,14,17,9,11,25,5,3

// Find the minimum element in arr[9...9]

// and place it at beginning of arr[9...9]

27,15,12,14,17,9,11,25,5,3

#include <stdio.h>
#include<conio.h>

void swap(int *xp, int *yp)

{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void selectionSort(int arr[], int n)

{
int i, j, min_idx;

// One by one move boundary of unsorted subarray

for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
 // Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}

/* Function to print an array */

void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Driver program to test above functions

int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

Question.2
Answer:

QuickSort
Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as
pivot and partitions the given array around the picked pivot. There are many different
versions of quickSort that pick pivot in different ways.
1. Always pick first element as pivot.
2. Always pick last element as pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and an
element x of array as pivot, put x at its correct position in sorted array and put all
smaller elements (smaller than x) before x, and put all greater elements (greater than
x) after x. All this should be done in linear time.

Pseudo Code for recursive QuickSort function :

/* low --> Starting index, high --> Ending index */

quickSort(arr[], low, high)

if (low < high)

/* pi is partitioning index, arr[pi] is now

at right place */

pi = partition(arr, low, high);

quickSort(arr, low, pi - 1); // Before pi

quickSort(arr, pi + 1, high); // After pi

Partition Algorithm
There can be many ways to do partition, following pseudo code adopts the method
given in CLRS book. The logic is simple, we start from the leftmost element and keep
track of index of smaller (or equal to) elements as i. While traversing, if we find a
smaller element, we swap current element with arr[i]. Otherwise we ignore current
element.
/* low --> Starting index, high --> Ending index */

quickSort(arr[], low, high)

if (low < high)

/* pi is partitioning index, arr[p] is now

at right place */

pi = partition(arr, low, high);

 quickSort(arr, low, pi - 1); // Before pi

quickSort(arr, pi + 1, high); // After pi

Pseudo code for partition()

/* This function takes last element as pivot, places

the pivot element at its correct position in sorted

array, and places all smaller (smaller than pivot)

to left of pivot and all greater elements to right

of pivot */

partition (arr[], low, high)

// pivot (Element to be placed at right position)

pivot = arr[high];

i = (low - 1) // Index of smaller element

for (j = low; j <= high- 1; j++)

// If current element is smaller than or

// equal to pivot

if (arr[j] <= pivot)

i++; // increment index of smaller element

swap arr[i] and arr[j]

swap arr[i + 1] and arr[high])

return (i + 1)

}
Illustration of partition() :
arr[] = {70,90,40,30,15,25,20,10,67,5}

Indexes: 0 1 2 3 4 5 6 7 8 9

low = 0, high = 9, pivot = arr[h] = 5

Initialize index of smaller element, i = -1

Traverse elements from j = low to high-1

j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0
arr[] = {70,90,40,30,15,25,20,10,67,5} // No change as i and j
// are same

j = 1 : Since arr[j] > pivot, do nothing

// No change in i and arr[]

j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])

i = 1
arr[] = {70,90,40,30,15,25,20,10,67,5} // We swap 70 and 40

j = 3 : Since arr[j] > pivot, do nothing

// No change in i and arr[]

j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])

i = 2
arr[] = {70,90,40,30,15,25,20,10,67,5} // 20 and 15 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i = 3
arr[] = {70,90,40,30,15,25,20,10,67,5} // 10 and 90 Swapped

We come out of loop because j is now equal to high-1.

Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot)
arr[] = {70,90,40,30,15,25,20,10,67,5} // 80 and 70 Swapped

Now 70 is at its correct place. All elements smaller than

70 are before it and all

/* C implementation QuickSort */
#include<stdio.h>

// A utility function to swap two elements

void swap(int* a, int* b)
{
 int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places

the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)

{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort

arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before

// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */

void printArray(int arr[], int size)
{
 int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("n");
}

// Driver program to test above functions

int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: n");
printArray(arr, n);
return 0;
}

Question 3.
Answer.

Explanation Of Program :
Firstly find the length of the string using library function strlen().
j = strlen(str)-1;

1 j = strlen(str)-1;

Suppose we accepted String “Pritesh” then –

j = strlen(str)-1;
= strlen("Pritesh" ) - 1
=7-1
=6

1 j = strlen(str)-1;
2 = strlen("Pritesh") - 1
3 =7-1
4 =6
 As we know String is charracter array and Character array have character range between 0 to
length-1. Thus we have position of last character in variable ‘j’.Current Values of ‘i’ and ‘j’ are
–
i = 0;
j = 6;

1 i = 0;
2 j = 6;

‘i’ positioned on first character and ‘j’ positioned on last character. Now we are swapping
characters at position ‘i’ and ‘j’. After interchanging characters we are incrementing value of ‘i’
and decrementing value of ‘j’.
while (i < j) {
temp = str[i];
str[i] = str[j];
str[j] = temp;

1 while (i < j) {
2 temp = str[i];
3 str[i] = str[j];
4 str[j] = temp;
5 i++;
6 j--;
7 }

If i crosses j then process of interchanging character is stopped.

Program
#include<stdio.h>
#include<string.h>

int main() {
char str[100], temp,ecount=0,ccount=0,lcount=0;
int i, j = 0;

printf("\nEnter the string :");

 gets(str);

i = 0;
j = strlen(str) - 1;

while (i < j) {
temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
ecount++; //calculating total number of exchange operation
ccount++; //calculating total number of comparison operation
lcount++; //calculating total number of loop execution
}

printf("\nReverse string is :%s", str);

return (0);
}

Question 4.
Answer.

Binary Search
Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].
A simple approach is to do linear search.The time complexity of above algorithm is O(n). Another
approach to perform the same task is using Binary Search.
Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an
interval covering the whole array. If the value of the search key is less than the item in the middle of the
interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check
until the value is found or the interval is empty.
The idea of binary search is to use the information that the array is sorted and reduce the time
complexity to O(Log n).

// C program to implement iterative Binary Search

#include <stdio.h>

// A iterative binary search function. It returns

// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;

// Check if x is present at mid

if (arr[m] == x)
return m;

// If x greater, ignore left half

if (arr[m] < x)
l = m + 1;

// If x is smaller, ignore right half

else
r = m - 1;
}

// if we reach here, then element was

// not present
return -1;
}

int main(void)
{
int arr[] = {4,7,12,24,29,30,40,50,55,60};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present"
" in array")
: printf("Element is present at "
"index %d", result);

return 0;