• Register
0 votes
171 views

Problem :

I have below doubts regarding sorting:

What is the smallest possible depth of a leaf in a decision tree for a comparison sort?           

Does it change depending on the algorithm?

Can anybody clear my doubts?

6 5 3
7,540 points

Please log in or register to answer this question.

2 Answers

0 votes

Solution :

The Best case happens when we just check the every element and see that the data is already sorted.

This results in n-1 comparisons and so the leaf will have a depth of n-1.

Practically speaking this happens for insertion sort.

Does it change depending on the algorithm?

It will change according to Algorithm. Here the best case of an algorithm is the good indicator - the shortest depth for one with O(n log n) the best case would be longer than the shortest depth for the one with O(n) best case.

To see this please consider the graph of n nodes, each node is representing A[i]. Draw the directed edge from i to j and if we compare A[i] with A[j] on the path from root to . Note that for k < n−1, this graph on {1, . . . , n} will not be connected. So we have two components C1 and C2 and so we know nothing about the relative order of the array elements indexed by the C1 against elements indexed by the C2. So there cannot be a single permutation π that sorts all the inputs passing these k tests - so π() is wrong for some arrays which lead to leaf

9 7 4
38,600 points
0 votes

The leaf of the decision tree always has depth n-1.

What is the smallest possible depth of a leaf in a decision tree for a sorting algorithm?

The shortest possible depth is n-1. To see this, observe that if we have a root leaf path with k comparisons, we cannot sure that the permutation at the leaf l is the correct one.

Proof:

To see this consider a graph of n nodes, each node representing A[i]. Draw an edge from I to j if we compare A[i] with A[j] on the path from the root to l.

Hence we have two components C1 and C2, and we know nothing about the relative order of array element indexed C1 and C2 against elements indexed by C2. Therefore there cannot be a single permutation that sorts all inputs passing these k tests.

Does it change depends on the algorithms?

It will change according to algorithms. Here is the best case of an algorithm and treated as a good indicator. The shortest depth for one with complexity O (n logn) with the best case would be larger than the shortest depth for the ones with the complexity O(n) of the best case.

Note:

The best case only happens when every element of the tree is already sorted.

11 5 2
3,890 points

Related questions

0 votes
2 answers 41 views
41 views
Problems I am new in programming, can anyone give the right solution? In linear​ programming, choices available to a decision maker are called A. objectives. B. choice variables. C. decision variables. D. constraints.
asked Feb 13, 2020 maddi86 5.4k points
0 votes
2 answers 225 views
225 views
Problems: Can anyone give the right solution The decision structure that has two possible paths of execution is known as _____? a. Single alternative b. Double alternative c. Dual alternative d. Two alternative
asked Feb 14, 2020 maddi86 5.4k points
0 votes
1 answer 13 views
13 views
Is there a standard algorithm or best practice on how to implement GetHashCode for my custom classes?
asked Aug 31, 2020 Sofi55 1.1k points
0 votes
1 answer 32 views
32 views
Problem: I am new and my logic is not so strong can any one give me right mathematical expression in linear programming? What is a mathematical expression in linear programming that maximizes or minimizes some quantity?
asked Feb 22, 2020 maddi86 5.4k points
0 votes
1 answer 33 views
33 views
I want to know how to sort an array in java without using sort method.
asked Sep 28, 2020 Daniel Anderson 4k points
0 votes
1 answer 63 views
0 votes
1 answer 23 views
23 views
Problem: I have fundamental knowledge of Java. I am trying to arrange the elements from an array and it is strictly based on the number of occurrences of that particular value in the ascending order in a java. This is what I have already tried: int a[]={0,0,0,1,3,3,2,1,3,5,6,0}; int b=a.length; for ... temp=a[i]; a[i]=a[j]; a[j]=temp; } } } for(int r=0;r<a.length;r++) { System.out.println(a[r]); }
asked Sep 5, 2020 Raphael Pacheco 4.9k points
0 votes
1 answer 26 views
26 views
C++ sort array of strings I'm trying to sort an array of strings, but it's not sorting.... what am I doing wrong? string namesS[MAX_NAMES]; int compare (const void * a, const void * b){      return (*(char*)a-*(char*)b ); } void sortNames(){      qsort(namesS, MAX_NAMES, sizeof(string), compare); }
asked Aug 29, 2020 sasha 5.3k points
0 votes
1 answer 27 views
27 views
Problem: Hello kodlogs, I have started learning python it been a month but I have a doubt that how can I be able to sort in python without using sort function and what are the possible ways to do this, though its been easy question, in c or c++ in college, we use to use sorting algorithm then it get sort is that same algorithm we can use in python too?
asked Jun 5, 2020 Gavin 15.3k points
3 votes
2 answers 3.8K views
3.8K views
Problem: I am struggling with a problem for a few hours back. I know how to sort an array by using methods. I was looking for another way (perhaps a loop) to do it more efficiently. Let me put my question this way, how to sort an array in java without using sort method? Could anybody here please help to make this happen? Thanks in advance
asked Mar 24, 2020 Gavin 15.3k points