sorting

The pseudocode of a function fun () is given below: fun(int A[0,...,n-1]){ for i=0 to n-2 for j=0 to n-i-2 if (A[j]>A[j+1]) then swap A[j] and A[j+1] } Let A[0, ...,29] be an array...

Given an integer array of size N, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass throug...

Let A be an array containing integer values. The distance of A is defined as the minimum number of elements in A that must be replaced with another integer so that the resulting ar...

Consider the following array. 23 32 45 69 72 73 89 97 Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort above arr...

Consider the following snippet of a C program. Assume that swap(&x, &y) exchanges the contents of x and y. int main() { int array[] = {3, 5, 1, 4, 6, 2}; int done = 0; int i; while...

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE ? $$\,\,\,\,\,\,...

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case...

Which of the following sorting algorithms has the lowest worst-case complexity?

Which one of the following in place sorting algorithms needs the minimum number of swaps?

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

The usual $$\Theta ({n^2})$$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorte...

A sorting technique is called stable if:

There are five records in a database. Name Age Occupation Category Rama 27 CON A Abdul 22 ENG A Jennifer 28 DOC B Maya 32 SER D Dev 24 MUS C There is an index file associated with...

Give the correct matching for the following pairs: Group - 1 (A) $${\rm O}(\log n)$$ (B) $${\rm O}(n)$$ (C) $${\rm O}(n\log n)$$ (D) $${\rm O}({n^2})$$ Group - 2 (P) Selection (Q)...

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot i) 1, 2, 3,......., n ii) n, n-1, n-2,......, 2, 1 Let C 1 and C 2 be the number...

Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…n] are to be sorted, give an input for which Quicksort tak...

Following algorithm(s) can be used to sort n integers in the range [1....... n 3 ] in O(n) time

Minimum number of comparisons required to sort 5 elements

Let P be a quicksort program to sort numbers in ascending order. Let t 1 and t 2 be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1], respectively. Which of t...