|
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.
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
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) {
}
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(n2Log(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
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
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;
};
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_r(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) {
}
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
|
|
|
|
|
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.
|
|
|
|
|
(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.
|
|
|
|
|
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).
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
|
|
|
|
|
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.
|
|
|
|
|
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.
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
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
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.
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!!!
|
|
|
|
|
It's ugly, but you could calculate the slope and quadrant (octant?) of each spoke (assuming the axis is defined to be the origin, or using translation to make it so).
"A Journey of a Thousand Rest Stops Begins with a Single Movement"
|
|
|
|
|
Hi to all of you guys here…
May this thread fits on this section. A friend of mine gave me this enigma. It is written in Excel format. Since here I can’t attach .xls file, I don't know how to put the file, name Enigma.xls.
There are infinite amount of tables, with ten rows (row 0,1,2,….9) each. Inside of each tables, there are numbers from 1 to 92, 93 to 184, 185 to 276, and 277 to 284, which lie on their certain rows. Here I gave the example tables that have been filled in for 40 tables. By finding the patterns/ formulas, my friend asked me to extend the tables to fill in the blank tables 41,42,43,etc as given beneath of Table 40. Just like SUDOKU, in each tables there will be no same numbers vertically, horizontally and diagonally. If these tables are using permutations from an ideal table that you can see beneath Table 40 (supposed the ideal table was right), then how to find the formulas of its permutations?
Can somebody help me about this?
Thx.
Hope my English is good enough for explaining this.
modified on Tuesday, March 31, 2009 11:52 PM
|
|
|
|
|
Someone has made a program in Java like this:
import java.util.*;
public class Table {
static Scanner console = new Scanner(System.in);
public static void main (String[] args)
{
String list = "010509131741454953572125293337616569737702030406070810111214" +
"151618192022232426272830313234353638394042434446474850515254" +
"5556585960626364666768707172747576787980818283848586878889909192";
String number;
int counter = 0;
int randomNumber = 0;
int rowPlacement = 0;
Vector row_0 = new Vector();
Vector row_1 = new Vector();
Vector row_2 = new Vector();
Vector row_3 = new Vector();
Vector row_4 = new Vector();
Vector row_5 = new Vector();
Vector row_6 = new Vector();
Vector row_7 = new Vector();
Vector row_8 = new Vector();
Vector row_9 = new Vector();
for (counter=0; counter<184; counter = counter + 2)
{
number = list.substring(counter, counter + 2);
//-------------------------------------------------------------------
if (counter == 10 || counter == 20 || counter == 30 || counter >= 40)
{
rowPlacement = 0;
}
//-------------------------------------------------------------------
do
{
randomNumber = (int) ( 10 * Math.random() );
}
while (rowPlacement > randomNumber);
//-------------------------------------------------------------------
if (randomNumber == 0)
{
row_0.addElement(number);
rowPlacement = 0;
}
else if (randomNumber == 1)
{
row_1.addElement(number);
rowPlacement = 1;
}
else if (randomNumber == 2)
{
row_2.addElement(number);
rowPlacement = 2;
}
else if (randomNumber == 3)
{
row_3.addElement(number);
rowPlacement = 3;
}
else if (randomNumber == 4)
{
row_4.addElement(number);
rowPlacement = 4;
}
else if (randomNumber == 5)
{
row_5.addElement(number);
rowPlacement = 5;
}
else if (randomNumber == 6)
{
row_6.addElement(number);
rowPlacement = 6;
}
else if (randomNumber == 7)
{
row_7.addElement(number);
rowPlacement = 7;
}
else if (randomNumber == 8)
{
row_8.addElement(number);
rowPlacement = 8;
}
else if (randomNumber == 9)
{
row_9.addElement(number);
rowPlacement = 9;
}
}
System.out.println(row_0);
System.out.println(row_1);
System.out.println(row_2);
System.out.println(row_3);
System.out.println(row_4);
System.out.println(row_5);
System.out.println(row_6);
System.out.println(row_7);
System.out.println(row_8);
System.out.println(row_9);
}
}
But it didn't work correctly yet in order to result tables like I put at Mediafire.com (a file hosting service) name Enigma.xls:
http://www.mediafire.com/?sharekey=12a93ace84ea3ab56b21be4093fab7ace04e75f6e8ebb871
|
|
|
|
|
I am a c# newbie and I need a point in the right direction. I have a problem where I will have an array with an area and two nodes(upper and lower). The format for the data will be as follows:
-Upper node will always be smaller than lower node.
-Each Area only has two nodes.
-Nodes can be shared but this can be overlooked for now.
-It is like an upside down tree, however, I don't need to solve any data. I just need to find the flow of the data so that I can draw a flow chart from it. Is there an algo that would suit this task or should I just go at it myself(don't want to reinvent the wheel).
I have a jpeg that would clarify the problem if any wants me to email it to them. If this doesn't make sense let me know. Thanks.
-----
Here is the link for the image
http://i44.tinypic.com/actrma.jpg[^]
modified on Monday, March 30, 2009 4:22 PM
|
|
|
|
|
I don't really get it so I guess I need to see the picture.
But why don't you upload the jpeg to tinypic[^] and update the original post with the link and let some more people have a go at it.
Remember that most people (including me) are lazy by nature.
|
|
|
|
|
http://i44.tinypic.com/actrma.jpg[^]
Essentially, it is an upside down tree. I don't need to solve data, just develop the flow diagram given the numerical data(area, upper and lower nodes).
I was going to create an array and populate it like a grid and then call my graphics function to print the flowchart. I don't know if this is effective (I am a civil engineer and a c# newbie). There shouldn't be more than 40 areas given to solve for and there shouldn't be more than 4 branches.
The data i will have will look like this:
area---upper node---lower node
1----101----------102
2----102----------103
3----103----------104
.......
8----108----------111
etc...
Thanks for any guidance.
modified on Monday, March 30, 2009 4:40 PM
|
|
|
|
|
Is my question not valid or unworthy?
|
|
|
|
|
The question is fine - I'm not sure anyone has a solution...
|
|
|
|
|
who can help me to solve the problem about 30 exercise in chapter 11, Graph Theory [Reinhard Diestel, 2005] or 30 exercise in chapter 8, Graph Theory [Reinhard Diestel, 2005] ?thanks!!!!!!!!!
|
|
|
|
|
|