Re: [algogeeks] Quick Sort

2012-01-29 Thread Moheed Moheed Ahmad
A typical implementation of quick sort works on quick sorting subarray and comparison is done in a linear manner that is a[i] is compared with pivot and then a[i+1] and so on. Virtual memory systems employ some sort of caching. Caching works on the principle of spatial locality of reference. That s

[algogeeks] Quick Sort

2012-01-28 Thread karthikeya s
How QuickSort is good in Virtual Memory Enviroment ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googleg

[algogeeks] quick sort query

2011-07-27 Thread prateek gupta
void quicksort( T[] A, Integer left, Integer right) if ( left < right ) q = partition( A, left, right) ; quicksort ( A, left, q–1); quicksort ( A, q+1, right) ; Integer partition( T[] A, Integer left, Integer right) m = left + right / 2; swap( A[left], A[m]); pivot = A[left] ; lo =

Re: [algogeeks] quick sort

2011-01-06 Thread Wladimir Tavares
Another thing, you should consider if the sort method is adaptive or not. For instance, quicksort 2-way is not adpative but quicksort 3-way is. Wladimir Araujo Tavares *Federal University of Ceará * On Thu, Jan 6, 2011 at 10:19 AM, Wladimir Tavares wrote: > You can use some techniques to

Re: [algogeeks] quick sort

2011-01-06 Thread Wladimir Tavares
You can use some techniques to improve quicksort: - randomized pivot - use insertion sort for small vector ~10 - use non recursive approach - median of some element chosed randomized - when you have many duplicate keys, you can use 3-way partition

Re: [algogeeks] quick sort

2011-01-05 Thread Gene
This is correct. It ensures there can be no degenerate partitions and improves the worse case run time to be asymptotically equal to the average case. In practice you would want to use a simple pivot selection algorithm and only resort to SELECT when the simple algorithm fails to produce a p

Re: [algogeeks] quick sort

2011-01-05 Thread harshal ..close enough
If we modify the PARTITION to use SELECT algorithm given in clrs to find median and partition the array about it, then i think it will be O(nlogn) worst case, because the array will be perfectly divided into 2 equal size arrays each time. But is the practical implementation of SELECT that fast? --

Re: [algogeeks] quick sort

2011-01-05 Thread priya mehta
You can't make it deterministically run in O(nlogn). On Wed, Jan 5, 2011 at 1:25 PM, lee wrote: > how can we make quick sort to run in O(logn) time in worst case?? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this grou

[algogeeks] quick sort

2011-01-04 Thread lee
how can we make quick sort to run in O(logn) time in worst case?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubs