2. Sorting & searching (a) Give a recursive algorithm for insertion sort. Also,

Question

2. Sorting & searching

(a) Give a recursive algorithm for insertion sort. Also, output the number of inversions in the input array.

(b) Find the missing number. You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. Give an algorithm to find the missing integer. Give the worst case time complexity for your algorithm. Can you improve it? Example Input: 1,2,5,3,6,4,8. Output: 7.

(c) Given an array of 10,00,000 pixel color values, each of which is an integer in the range [0,255]. Which sorting algorithm is preferable for sorting them?

Explanation / Answer

// pseudo code

// Passing n array of numebrs of size n

void insertionSortRec(int arr[], int n)

{

// If there is only one element, it is already sorted.

if (n <= 1)

return;

// we will follow the algorithm where we srt the first (n-1) elements

// and then insert the last element, i.e. nth element at its proper position

insertionSortRec( arr, n-1);

// Now that the first n elements are sorted, lets put the nth element at its correct position

int last = arr[n-1];

int j = n-2;

// We will now move whatever elements are greaer than the last element, by one position to the right

while (j >= 0 && arr[j] > last)

{

arr[j+1] = arr[j];

j--;

}

// put the last element

arr[j+1] = last;

}

=======================================================

XOR(A,B,C) = XOR(XOR(A,B), XOR(C))

SO XOR(C) = XOR(XOR(A,B,C), XOR(A,B))

So if we find the XOR of numbers from 1 to n and then take the XOR of given numbers, we can find the XOR of the missing number...

We can XOR the numbers from 1 to n, lets suppose value is K1.

we will now take XOR of the given numbers, lets suppose value is K2.

missing value is K1 XOR K2.

=======================================================

For counting the numbers in a range, the counting sort is the best mechanism to use.. We can take an frequency array of long ints of size 256. We will go through the given array and whatever value is given, we will go to that index in frequency array and then increment the frequency by 1... Thus after this completion, we will get to know which value of 0 to 255, has occurred for how many times.. we can then go in sorted order and print the values as per their frequencies.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.