Please answer these doubts related to Quiz on Sorting

#1

  1. In a permutation a1……an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1……n with at most n inversions?

  2. Let P be a Quicksort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?
    t1 = t2
    t1 > t2
    t1 < t2

  3. Which of the following is an external sorting?
    Insertion Sort
    Merge Sort
    Bubble Sort
    Tree Sort

4)Partition and exchange sort is ………
Quick Sort
Heap Sort
Bubble Sort

  1. The ususal O(n^2) implementation of insertion sort uses the linear search to to identify the position where an element is to be inserted into the already sorted part of the array. If instead, we use binary search to identify the position the worst case running time will be:
    O(n)
    O(nlogn)
    O(n^2)
    O(n(logn)^2)

  2. If quicksort is written so that partition algorithm always uses the median value of the segment as the pivot then worst case performance of quick sort will be?
    O(n)
    O(nlogn)
    O(n^2)

  3. 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 performance is
    O(n^2)
    O(nlogn)
    O(n)

#2

hello @sahilkhan2312000131

choosing the middle element minimizes the chances of encountering O(n2), but in worst case it can go to O(n2). Whichever element we take as Pivot, either first or middle, worst case will be O(n2) since Pivot is fixed in position

it will be nlogn becuase median will ensure that paritition are always divided into two equal halves.

then also it will be O(N^2) because shifting all elements to the right of newly inserted element will take O(N). and for N such iterations it will be N^2.

merge sort. using mergesort we can sort large files as well by dividing them in smaller chunks and sorting each chunks one by one and merginf them one by one

t>t2 because quicksort perfomance is poor for sorted data

Insertion sort runs in Θ(n + f(n)) time, where f(n) denotes the number of inversion initially present in the array being sorted.

#3

Can you please answer this:
Partition and exchange sort is ………
Quick Sort
Heap Sort
Bubble Sort

#4

this question is not clear

#5

Which sort is also called partition and exchange sort among these and why??
Quick Sort
Heap Sort
Bubble Sort

#6

exhnage/partition sort working is some what similar to bubble so if they talking on basis of similarity then it should be bubble sort

#7

But the answer they have given is quick sort. Can you please explain why?

#8

see they have not cleared the context , in what context they are talking.

if they are relating parition algorithm with quicksort becuase we use it while sorting then answer is quicksort.
but exchange sort is simialr to bubble sort so in that context answer will be bubble sort.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.