• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Quicksort Problem

 
Ranch Hand
Posts: 66
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I really need help tracing a quicksort. Can someone help? The numbers are:
20, 80, 40, 25, 60, 10, 15

Thanks!
 
Steven Alvarez
Ranch Hand
Posts: 66
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I assume the pivot can be 15 or 20. But how to trace it after that is very confusing. Can someone trace this for me? Thanks!!
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
To "trace a quicksort", you'd have to have a specific implementation to trace. There are a number of little implementation-dependent bits that mean the precise steps taken would differ depending on the code. You can't really trace the algorithm itself.

So is there a particular implementation you can show us that you're interested in understanding?
 
Steven Alvarez
Ranch Hand
Posts: 66
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The method where you choose a pivot and there are two sections. The first section where the values or less than the pivot, and the second section where the values are the same or greater than the pivot.
 
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Choosing a pivot and recursively applying the QuickSort procedure on left and right arrays is kind of how all QuickSort implementations work. I think the problem here is that you need to be more precise about some things that could vary across implementations. For example

1) How do you choose the pivot? Some ideas of how the pivot could be chosen are:

a) Pick the first element always
b) Randomly select an element from the array
c) Get the median and pick that as pivot

The choice determines the order of growth, the constants, and of course it determines how the array will be subdivided.

2) Once you have a pivot, how do you then move all the elements smaller than the pivot to the left of the pivot, and the largers to the right? This can also vary according to the implementation, even if any good one will be
O(n).

I think the best idea for the sake of clarity would be to just disclose the full pseudocode so that you can be guided step by step.


[ April 07, 2008: Message edited by: Alberto Caraz ]
 
reply
    Bookmark Topic Watch Topic
  • New Topic