Author: Stan Eisenstat
Subject: Re: [Cs223] 2 * # of compares + N constraint in walk-through
Date: Tuesday, 17 Mar 2020, 17:16:49
> Message Posted By: Unknown > > According to the walkthrough, 2 * (# of compares) is equivalent to M where > M is the number of elements being partitioned in the call. This is incorrect, as follows from several earlier postings. The number of calls to addD() and push() should be at most 2 * (# of compares) + N, which can be achieved by calling addD() and pushD() at most 2*(M-1)+1 times (not including calls when quickSort calls itself recursively). See Note C, Point 5. ===== > When doing the partition step in a quicksort of a set of N items, doesn't > that take N-1 number of compares as we have to compare every element > besides the pivot to the pivot? Shouldn't 2 * (# of compares) actually be > 2 * (M-1) instead of simply M as stated in the walkthrough? It should be 2*M-1, which is equivalent to the 2*(M-1)+1 above. --Stan-PREV INDEX NEXT