Re: [algogeeks] Quick Sort

[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 said, once a
comparison begins, after a miss in the cache, cache is fetched for the
miss(a[i]) as well as for next few more memory cells (a[i+1], a[i+2], etc).
This ensures that next 'few'(typically 3-5) iteration of the loop will be a
cache hit, there by speeding up the algorithm.


-Moheed
"I am who I am, no matter where I am or who I am with."
*
*



On Sun, Jan 29, 2012 at 12:38 AM, karthikeya s wrote:

> 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...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
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...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Quick Sort

[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...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] quick sort query

[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 = left+1; hi = right;
while ( lo ≤ hi )
while ( A[hi] > pivot )
  hi = hi – 1;
while ( lo ≤ hi and A[lo] <
∼ pivot )
  lo = lo + 1;
if ( lo ≤ hi )
  swap( A[lo], A[hi]);
   lo = lo + 1;  hi = hi – 1;
swap( A[left], A[hi]);
return hi

plz tell me the case for (lo=hi) in while loop in partition.

-- 
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...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] quick sort

[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 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
>
> Wladimir Araujo Tavares
> *Federal University of Ceará
>
> *
>
>
>
>
>
> On Thu, Jan 6, 2011 at 12:52 AM, Gene  wrote:
>
>> 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 partition
>> within a fixed fraction of 50/50.
>>
>>
>>
>>
>>  --
>> 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+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
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+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] quick sort

[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

Wladimir Araujo Tavares
*Federal University of Ceará

*




On Thu, Jan 6, 2011 at 12:52 AM, Gene  wrote:

> 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 partition
> within a fixed fraction of 50/50.
>
>
>
>
>  --
> 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+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
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+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] quick sort

[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 partition 
within a fixed fraction of 50/50.




-- 
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+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] quick sort

[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?

-- 
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+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] quick sort

[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 group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
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+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] quick sort

[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+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.