Algorithms

1-Apr-09 17:16

Steve,

Thank you for the reference. Turns out that StableSort is a merge sort. Of course it is stable. You are always comparing elements before you select one or the other to output. My contention, having read many of the Articles on quicksort and seen their algorithms, is that they attempt to be stable once the pivot and an element is compared, but totally ignore whatever has not been seen (between i and j) when swapping i and j elements to satisfy the sort conditions i < pivot, j >= pivot. Note that you have only compared i and pivot and j and pivot, (by the algorithm, i < j), but you know nothing about what lies between i and j. Swapping these two elements may cause an unstable sort as I demonstrated in my initial post.

My attempt is to build a stable quicksort which should be faster, and not require the additional mergesort memory (see The Knuth reference, last paragraph on page 161 (Volume 3, copyright 1973). I would quote it, but cannot due to copyright restriction.

Dave.

supercat93-Apr-09 6:22

supercat9

3-Apr-09 6:22

My attempt is to build a stable quicksort which should be faster, and not require the additional mergesort memory (see The Knuth reference, last paragraph on page 161 (Volume 3, copyright 1973). I would quote it, but cannot due to copyright restriction.

I'm unaware of any mathematical restriction on the ability to perform a stable sort without requiring either extra time or extra storage (insertion and selection sorts, e.g., require no extra storage, but a lot of extra time) but I am also unaware of any implementations that require neither extra time nor storage. That having been said, in many applications it is better to physically move around pointers than to move around data, and if one is shuffling pointers the extra storage isn't really a problem.

Incidentally, I've invented a sorting algorithm I've never seen elsewhere which performs slightly fewer than n*lg(n) comparisons (as does a good QuickSort implementation, btw) but yields the results in order (the first item will be made available after n-1 comparisons; the next item will be available after lg(n) comparisons, etc. The storage and time overhead for book-keeping (about 16 bytes/element on a 32-bit machine, and sub-logarithmic time but with a hefty constant) probably make the sort impractical, but having the sort yield the results in order is cute.

Member 41945934-Apr-09 5:58

Re: Stable Quicksort algorithm [modified]

4-Apr-09 5:58

supercat9,

Thank you for the reply. I am aware that it will take more time or storage to stablize the sort. The question is how much more. I am already running into conditions that have sometimes forced me to go to an external sort, not enough virtual memory available. Especially under full memory condition, you do not want to swap by exchanging pointers, you will be paged to death the entire time. At least by scanning up or down in memory for adjacent records, you will stay in a small number of pages (3 to 6) the records in their original positions may result in a page fetch for each record.

If you include a tie-breaker element in the keys, it takes that extra room in each record, space that always must be swapped during exchanges, and sometimes must compared when the rest of the key matches. If the original record has another field that can be used as a tie-breaker, then the extra space and the exchange time already exist, and it is only a matter of comparing the tie-breaker if the rest of the key matches, but, this requires having to specify the parameters of the tie-breaker so the compare can be done and the type of element may not be the same as the original key. All of this is doable, just a matter of what is the "best".

Dave.

bulg3-Apr-09 14:15

bulg

3-Apr-09 14:15

can someone tell me the O() of this:

struct pivot { 
  int l,r;
};

function partition( array, left, right ) {
  pivot.l = pivot.r = left

  for i = left to right 
  {
    if (array[i] >= pivot.l)
      pivot.r += 1
    else 
      swap(pivot,i)
  }
  return pivot.l
}

swap_r (range, index) {
  int t=range.r
  while(range.l<=t)
    swap_i(t--,index)
}

swap_i (index1, index2) { 
  /// straight swap
}

function quicksort(array) { 
  int p = partition(array,0,length-1)
  quicksort(array,0,p)
  quicksort(array,p+1,length-1)
}

It is psuedo-code, but you get the idea. I think it's O(n²Log(n)) but I'm not sure. If you could figure out how to put 1 element in front of x elements better, it'd be what you want.

modified on Friday, April 3, 2009 8:29 PM

P.s.

bulg3-Apr-09 14:28

bulg

3-Apr-09 14:28

What's up with the copyright mind-virus? from the copy right act of 1976:

In no case does copyright protection for an original work of authorship 
extend to any idea, procedure, process, system, method of operation, 
concept, principle, or discovery, regardless of the form in which 
it is described, explained, illustrated, or embodied in such work.

Member 41945934-Apr-09 6:36

4-Apr-09 6:36

bulg,

Thank you for the replies. I would respond to your second response (I got an email notification), but it appears that you deleted the post. Do you have an actual algorithm for the "lazy quick sort"? Seems interesting.

For your algorithm in this post, it seems a bit strange and incomplete or inaccurate. How can you swap an integer and a structure of two integers swap(pivot,i)?

As far as copyrights go , sure it is 25 years old, but has it been renewed? Is it still active? What constitutes "fair use"? This has been argued in the courts many times. I do not have deep pockets so I just refuse to quote an author. I did discuss the point he made about the requirement for the extra space required for the stable quicksort, a size equal to the original size of the piece being partitioned. Similar to a merge sort, but with the terrible disadvantage that merge sort put the elements in the correct sequence, stable quicksort only copies them in an unordered state to two buffers (less than and greater than the pivot) and requires that the two partitions still need to be sorted. What a waste.

Dave.

bulg9-Apr-09 11:42

bulg

9-Apr-09 11:42

Hey Dave,

I'm gonna answer the copyright question first: You are protected & free to write or say anything you want *about* Knuth's books, including the contents, as long as you don't do it for profit. If you use it authoritatively, you should also say, "as Knuth wrote in ...", aka, cite it. Otherwise, a million kids across the country turning in book reports with "at least 4 quotes from the book" would be copyright villains.

Here's my lazy quick sort again, this time with better annotation. Still pseudo-code, though:

struct pivot { 
  int l,r;
}; /* the "pivot" struct represents a range in an array */

function partition( array, left, right ) {
  pivot.l = pivot.r = left  /* pivot starts as a range of 1 variable,
                               array[left] */
  for i = left to right 
  {
    if (array[i] >= pivot.l)
      pivot.r += 1          /* increase the range of the pivot */
    else 
      swap_r(pivot,i)       /* swap the entire range with the 
                               next element, to stay stable */
  }
  return pivot.l            /* return the start of the pivot range */
}

swap_r (range, index) {     
/* swaps an index with a range, by going through 
   the entire range one at a time. Probably naive */

  int t=range.r
  while(range.l<=t)
    swap_i(t--,index)
}

swap_i (index1, index2) { 
  /// straight swap, requires a single 
  /// temporary element (or possibly just a pointer)
}

function quicksort(array) { 
  int p = partition(array,0,length-1)
  quicksort(array,0,p)
  quicksort(array,p+1,length-1)
}

This works on paper. I used the values

0 1 4 4 5 4 2 4 2 3 5 3 7 6 7 4

when I did it by hand.

If you wanted to make it like I envisioned lazy quick sort, then you could employ another range for swapping, instead of swapping at the first index that is < pivot.l. I am not convinced this would be faster... but I don't really have time to try it. If you do, please let me know!!

-Ryan

Member 41945939-Apr-09 16:51

Vector orientation Question.

9-Apr-09 16:51

Ryan,

Thank you for the reply. swap_r won't work. Here is how to fix it. Move the indexed value out of the way to a temporary location. Now instead of swapping each element in the range with the indexed value (this is what won't work, you overlay all of the prior values on top of each other), just move the range in reverse (as you have done by decrementing t), finally opening space at the front of the range into which you can put the saved original indexed value. Instead of picking up two values and saving two values (a swap), you are just picking up a single value and saving the single value to a new location (a move). Half of the work. Of course, you have to decrement both of the move indexes as you move the data (the fix for the overlay in your original version).

Just about done with my original quicksort. I have found a MASM 8 bug along the way. MASM 8 will not accept:
movd qword ptr [base+index],xmm0 or movd xmm0,qword ptr [base+index]. The AMD manual specifically says movd works for both XMM and MMX as long as you specify a mem64 location. Not really a great problem, I just used a movq instead. I got into this because I just compared two extended floating values via the FPU and needed to swap them and tried to use MMX registers, however, the execution did not work (assembled without error, executed with no exceptions, but the array was not sorted). Seems that MMX and FPU share the same registers and control flags, and I guess you must finit the FPU before trying to use MMX. This is too time expensive, so I was just using XMM which is an independent register set. The only problem is that the code now depends on XMM instead of only MMX (my code was using an alignment specification of 8 to flag MMX OK, and an alignment of 16 to flag XMM OK. I may have to implement one more parameter which will just be used to enable MMX and/or XMM independently of the data alignment.

Dave.

Maximilien31-Mar-09 4:59

Maximilien

31-Mar-09 4:59

(Let's just hope the description is good enough)

Let's say I have a cylinder, and a series of lines (spokes) that go trou it in circular fashion. lines are pointing from the cylinder surface to the axis of the cylinder.

In my case, the lines "direction" can be either going towards the center of the cylinder or outside.

Is there a way to know if the direction of the vector (IJK) is pointing towards the interior or the exterior ?

I could possibly construct 2 points with the vector and its reverse and see which point is closer to the center and use that direction.

Is there a better "math" solution ?

Thanks

This signature was proudly tested on animals.

Luc Pattyn31-Mar-09 5:06

Luc Pattyn

31-Mar-09 5:06

I don't see what the problem could be. If you have a cylinder with radius R and a point P, all it takes is to calculate the distance from P to the main axis of your cylinder; if that distance is less than R, then you are inside the cylinder (assuming its height is infinite).

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets

Maximilien31-Mar-09 5:34

Maximilien

31-Mar-09 5:34

The cylinder description was not a good idea to describe the problem. I don't have a radius.

(will edit the original post)

This signature was proudly tested on animals.

Re: whatever shape

Luc Pattyn31-Mar-09 5:38

Luc Pattyn

31-Mar-09 5:38

OK, if in three dimensional space you have a surface described by f(x,y,z)=0 then all points P(X,Y,Z) that make f(X,Y,Z)>0 will lie on one side, and those making f<0 will lie on the other side. So check one point to see what you choose to call the inside, and you will know for all points.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Re: whatever shape

Maximilien31-Mar-09 5:42

Maximilien

31-Mar-09 5:42

My description is not good enough, it's "too" specific for my particular "problem", With an actual cylinder, and vector, I can resolve it.

I will try to have a better description.

Thanks.

This signature was proudly tested on animals.

⁷³Zeppelin31-Mar-09 5:13

⁷³Zeppelin

31-Mar-09 5:13

Are you using cylindrical coordinates? In that case, rho should be your radial vector.

You can define rho to be positive if it points outward from the axis of the cylinder and negative if it points inwards.

Tim Craig31-Mar-09 8:26

Tim Craig

31-Mar-09 8:26

Since you simply have a direction and an axis, on one side it points toward the axis and on the other away from the axis.

[<--------O<-------]

The braces are the survace of the cylinder, the O is the axis, and well, you should get what the arrows are. Smile | :)

I think to do what you want, you need the vector describing the axis and a point in space to decide if the vector points toward the line or away.

"Republicans are the party that says government doesn't work and then they get elected and prove it." -- P.J. O'Rourke

I'm a proud denizen of the Real Soapbox[^]
ACCEPT NO SUBSTITUTES!!!