Sorting algorithm.
Author
Basically, this is a non-inplace sorting algorithm designed to replace quicksort on some datasets. (not sure about what its good at yet.)
First, take N records from the data that your sorting, and sort them. (using bubble/insertion sort).
From those, use binary search to figure out where the first element goes in the second array.
Now, get the last element from the array, and use binary search (using the first element as min), to figure out where it goes.
Now, for every other element, use min and max values, which get shifted inwards every time one record finished.
Once thats done, you get another N records and start again.
Now, how does this fare?
As an egsample, take the values
1
2
5
10
15
4
13
41
23
24
12
0
Now, were going 5 elements at a time.
First 5 are:
1
2
5
10
15
There sorted in order.
We then insert them in order making the secondary list
1
2
5
10
15
The next 5 are
4
13
41
23
24
Which, when sorted makes it
4
13
23
24
41
Which are then inserted into the second list as
1
2
4
5
10
13
15
23
24
41
The last two values are
12
0
Which sorted are 0, 12 and when there inserted into the list, they make
0
1
2
4
5
10
12
13
15
23
24
41
Which is the origional list, sorted.
Now, for the min/max bit.
Say your inserting
4
13
23
24
41
into
1
2
4
5
10
15
You go for the fist one.
value 4, check 3, too big, check 2, too small, insert at location 3.
Now, you add the last element which is 41 to the dataset.
You set min to 3, max to 6, so you test #5. its too big for #5, and $6, so you insert it in #7.
1
2
4
5
10
15
41
So now, you have bounds. (which gets smaller every time.)
You then insert 13 then 23 then 24, that thats it.
The next one needs to be further down still.
Ect.
How would this compare to other algos?
From,
Nice coder
Well, making a gross analysis I get the following for sorting a list of N items in chunks of M items.
- do N/M times
- sort M items
- traverse a list of say N/2 items
- insert M items
As for the sorting, you suggested something like insertion sort (funny, a sorting algorithm using another sorting algorithm). The time complexity of insertion sort is O(n^2) worst case. The list traversal is linear, say O(N/2). And assuming insertion is constant time O(1), which it is probably not in vectors or lists, which is why other sorting algorithms use swapping, the complexity lies in the sub-sorting algorithm.
Hence it comes down to O(N/M * M^2) or basically O(NM). Since quicksort has an expected complexity of O(N log N) it generally beats your algorithm. Worst case, however, quicksort still does O(N^2) in which case you might be faster. However, that would require a more precise analysis which may turn out to prove something different, as this was something I thought up quickly. Moreover, the insertion and the all over implementational complexity as well as the not-in-placeness of your algorithm make it improbable for most uses, I think.
Greetz,
Ill.
- do N/M times
- sort M items
- traverse a list of say N/2 items
- insert M items
As for the sorting, you suggested something like insertion sort (funny, a sorting algorithm using another sorting algorithm). The time complexity of insertion sort is O(n^2) worst case. The list traversal is linear, say O(N/2). And assuming insertion is constant time O(1), which it is probably not in vectors or lists, which is why other sorting algorithms use swapping, the complexity lies in the sub-sorting algorithm.
Hence it comes down to O(N/M * M^2) or basically O(NM). Since quicksort has an expected complexity of O(N log N) it generally beats your algorithm. Worst case, however, quicksort still does O(N^2) in which case you might be faster. However, that would require a more precise analysis which may turn out to prove something different, as this was something I thought up quickly. Moreover, the insertion and the all over implementational complexity as well as the not-in-placeness of your algorithm make it improbable for most uses, I think.
Greetz,
Ill.
Yep, what definitely kills your performance is the fact that insertions into the middle of a vector are a linear-time operation. Even if the insertions were constant-time, the whole algorithm would still be average-case O(n²), because for each iteration, most of the resulting vector has to be traversed to find a place for each new element. Finding the min/max bounds won't help much on average case, it just decreases the hidden constant factor a bit (with some inputs it might even increase the factor!).
The regular quicksort is a very good choice for sorting smallish inputs. It has a low constant factor, and the worst-case quadratic behaviour doesn't matter much when inputs are small.
The regular quicksort is a very good choice for sorting smallish inputs. It has a low constant factor, and the worst-case quadratic behaviour doesn't matter much when inputs are small.
Yeah, this looks to me like an attempt at a non-recursive mergesort implementation, building things from the bottom-up. It's definitely doable and may even be a good idea...
What you're trying to describe bares some sililiarity to MergeSort, JSort, and StrandSort.
Probably JSort is the closest.
Also, example is spelt with an "x", not a "gs". I've been meaning to tell you that [smile].
Probably JSort is the closest.
Also, example is spelt with an "x", not a "gs". I've been meaning to tell you that [smile].
Author
Ok. I thought that insertions are going to be the downside of this.
:(
ow well.
Another idea (o log2 n Fast Constant time) algorithm:
Its currently recursive, but that shouldn't be a problem should it?
From,
Nice coder
:(
ow well.
Another idea (o log2 n Fast Constant time) algorithm:
Start at the bottom of the array.Set the bottom element as the working element.Set the upper and lower second bounds to the bounds of the array.If the two bounds are close together then: Sort using bubblesort, insertionsort, or similar returnend ifWhile (the second bounds of the array do not cross) {if the working element has the current bit set then Swap the working element, for the element at the upper second bound. Lower the upper second bound by one.else Increment the lower second bound by one. Set the working element to be the element at the lower second bound.end if}Divide the current bit (as an int), by two.If this bit is 0, then return.Else:Call this function again, with the bounds being from the origional lower bound(low bound) to the current lower bound (heigh bound)Call this function again, with the bounds being the current heigher bound(as the lower bound), and the origional heigher bound as the heigh bound.Return Its currently recursive, but that shouldn't be a problem should it?
From,
Nice coder
Author
Quote:Original post by iMalc
What you're trying to describe bares some sililiarity to MergeSort, JSort, and StrandSort.
Probably JSort is the closest.
Also, example is spelt with an "x", not a "gs". I've been meaning to tell you that [smile].
Nice links.
I'm still in the habbit of using egsample. It just seems more natural to use eg. (considering that the contraction is e.g.)
For egsample, for eg. for example, for eg? (australian spelling, remember. We use colour instead of color.)
From,
Nice coer
Quote:Original post by Nice Coder
I'm still in the habbit of using egsample. It just seems more natural to use eg. (considering that the contraction is e.g.)
It's latin: "Exempli Gratia", meaning "for example".
i.e. = "id est", "that is"
et al. = "et alia", "and others (people)"
etc. = "et caetera", "and others (things)"
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
