Register

Recent questions tagged sorting

1.1k
views
3 answers
0 votes
Radix Sort Problem
The complexity of Radix Sort is $O(wn)$, for $n$ keys which are integers of word size $w$.Here, $w=log_2(n^k)=k\times log_2(n)$So, the ... input in linear time?Similar Concept used to solve : https://gateoverflow.in/3353/gate2008-it-43
User Avatar
2.2k
views
2 answers
7 votes
CMI2017-A-08
A $\text{stable sort}$ ...
User Avatar
1.0k
views
1 answers
1 votes
me test series
Given two unsorted singly-linked lists each with n distinct elements. There exists an efficient intersection algorithm, that computes and returns a new list with common elements between ... .......i think it should be O(n^2)...please verify
User Avatar
1.8k
views
2 answers
1 votes
Worst Case Time Complexity
What is the worst case time complexity to find kth smallest element into an array of ‘n’ element?
User Avatar
249
views
1 answers
1 votes
Algorithms
A sorting algorithm is stable if duplicate elements remain in the same relative position after sorting.What is the meaning of this statement
User Avatar
3.1k
views
3 answers
3 votes
number of comparison require in RADIX sort
I am not able to get this formula (number of input * number of digit *base of number )I am not getting how base of number is important ?Thanks :)
User Avatar
2.6k
views
1 answers
3 votes
quick sort
You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest lower bound for the best case performance isa) O(n2)b) O(nlogn)c) Θ(nlogn)d) O(n3)
User Avatar
1.0k
views
1 answers
2 votes
Ace Test series: Algorithms - Sorting
User Avatar
1.1k
views
1 answers
3 votes
MadeEasy Test Series 2017: Algorithms - Sorting
Given a set of n distinct integers, it is required to determine the three smallest integers of this array using comparisons, The no of comparison needed are (A) n + O( log n )(B) n + O( 1 )(C) O ( n )(D) O ( log2n ) ANSWER GIVEN ::- A
User Avatar
587
views
0 answers
1 votes
Sorting
Consider an execution of Quicksort with the first item of an array segment acting as pivot or splitter. After first pass of running quicksort on an array (Assume that we ... 16,10 I want to know what will be the sequence for the first pass
User Avatar
1.9k
views
1 answers
1 votes
ISRO-DEC2017-48
Quick-sort is run on $2$ inputs shown below to sort in ascending order :$1,2,3\ldots n$n,n-1,n-2\ldots 1$Let $C$1 and $ ... A and B respectively. Then, $C1>C2$C1=C2$C1<C2$Cannot say anything for arbitrary $n$
User Avatar
490
views
2 answers
2 votes
Nielit
I studies in my book that time complexity of buble sort in best case =n^2 but I found it here ....its wrong ? If correct then how
User Avatar
1.4k
views
1 answers
1 votes
Find the element that appears once in a sorted array.
In a sorted array, every element is repeated more than once except one. what will be the time complexity to find that element in the worst case?
User Avatar
3.5k
views
1 answers
0 votes
more than n/2
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers isΘ(n)Θ(logn)Θ(log∗n)Θ(1)isnt O(1) ... give in this site is log Ncan i get a counter on why O(1) wont work ?
User Avatar
8.4k
views
1 answers
13 votes
TIFR CSE 2018 | Part B | Question: 7
Consider the recursive quicksort algorithm with "random pivoting". That is, in each recursive call, a pivot is chosen uniformly at random from the sub-array being sorted.When this ... }}\right)$\Theta\left(\dfrac{1}{n \log^{2} n}\right)$
User Avatar
1.1k
views
2 answers
0 votes
MadeEasy Test Series: Algorithms - Sorting
Which of the following sorting techniques have best time complexity, if complexity is measured in terms of number of comparison? A Insertion sortB Selection sortC Merge sortD QuickSort
User Avatar
1.2k
views
1 answers
3 votes
3-way quicksort
3-way partitioning is a modification of quicksort that partitioned the elements into groups smaller than,equal to and larger than pivot. Only the group of smaller and larger elements need to be ... A) O(nlogk)(B) O(klogn)(C) O(nk)(D) O(k^2)
User Avatar
556
views
1 answers
0 votes
#swaps in case of reversely sorted array using bubble and insertion
Consider this array [ 2,2,2,1,1,1,1,1,0,0,0 ].Find the min. no. of swaps needed for this array to be sorted in asc. order using:a) bubble sortb) insertion sort
User Avatar
809
views
1 answers
1 votes
algorithm
User Avatar
2.0k
views
1 answers
4 votes
MadeEasy Subject Test: Algorithms - Sorting
Consider the following statements:S1 : On any random input insertion sort is work more efficiently than bubble sort.S2 : Average number of comparison of insertion ... sort an array [input], then which of the above statement is correct?
User Avatar
777
views
0 answers
0 votes
Question on Inversion and sorting
The average number of inversions in an unsorted array of n elements is?(Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j)A.) n(n-1)/2B.) n(n-1)/4C.) n(n+1)/2D.) n!/2
User Avatar
4.7k
views
2 answers
7 votes
Question on sorted array and time complexity
Which of the following operations can be performed in O(log n) time or faster on a sorted array A? (n denotes the size of array)1) Search(A, x)2) ... themI chose option B but the book says option D is right. Please provide an explanation.
User Avatar
678
views
1 answers
2 votes
#TestBook
Suppose in an array A[] , we exchange elements A[i] and A[i+k] , which were originally out of orderA) at least 1 and at most 2k-1 inversions are ... at most 2k inversions are removedC)at least 0 and at most k inversions are removedD) none
User Avatar
1.0k
views
3 answers
2 votes
Sorting
Two unsorted arrays of size m and n are to be sorted into a single array, what is best case time complexity?
User Avatar
914
views
0 answers
1 votes
Merge sort and insertion sort
User Avatar
263
views
1 answers
2 votes
time complexity
Cosider n distinct integers , it is required to determine 3 smallest integers of this array by comparisons.The number of comparisons needed are1.n+ O(logn)2.n+O(1)3.O(n)4.O(log2n)
User Avatar
1.3k
views
1 answers
1 votes
test series
given an unsorted array with n distinct elements with a property that every element can be atmost k distance from its original position . what is the worst case time complexity to get the sorted array.ans O(n log k)how .....
User Avatar
477
views
1 answers
2 votes
TestBook Test Series
there is a sorted array which is of very large. every element is repeated more than once except one element. how much time will it take to find the element?
User Avatar
512
views
0 answers
1 votes
Combined Sorting
A cache aware sorting algorithm sorts an array of size $2^{k}$ with each key of size 4 Bytes. The size of cache memory 128 Bytes. and algorithm is a combination of merge sort and ... 2)$2^{k-5}\left [ 2^{5}+log_{2}2^{k-5} \right ]$
User Avatar
773
views
1 answers
2 votes
Sorting
The minimum number of comparisons required to sort 25 elements is ____
User Avatar
Page: