What is the name of the following sorting method?
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (a[i]>a[j])
swap(&a[i], &a[j]);
It seems to be the opposite of bubble sort, with lighter elements going
in their proper positions first. However, this one does not compare
a[j] with a[j+1], as the normal bubble sort does.
Looks very simple, and I wonder why I couldn't find it anywhere on the
net! 11 2155
Registered User wrote:
What is the name of the following sorting method?
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (a[i]>a[j])
swap(&a[i], &a[j]);
It seems to be the opposite of bubble sort, with lighter elements going
in their proper positions first. However, this one does not compare
a[j] with a[j+1], as the normal bubble sort does.
Looks very simple, and I wonder why I couldn't find it anywhere on the
net!
I doubt this has a name, but most people would call it something like
"the naive O(n^2) sorting algorithm". In otherwords, it's a lousy
sorting algorithm. It IS simple, because it just does it by brute
force. It's extremely slow. If you used this to sort a million
elements, it would take order of a trillion steps, whereas the fancier
sorting algorithms would take order of 10 million steps.
Also this is off topic at comp.lang.c since the algorithm has nothing
to do with C (in fact it even uses a weird "swap" thing that is
defined somewhere in your file, not in the C language. In my analysis
I *assumed* this was a straightforward swap function, but really it
could be anything at all for all we know...)
"Registered User" <in*******************@gmail.comwrites:
What is the name of the following sorting method?
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (a[i]>a[j])
swap(&a[i], &a[j]);
It seems to be the opposite of bubble sort, with lighter elements going
in their proper positions first. However, this one does not compare
a[j] with a[j+1], as the normal bubble sort does.
Looks very simple, and I wonder why I couldn't find it anywhere on the
net!
It's a bad variant of the selection sort. http://en.wikipedia.org/wiki/Selection_sort
It's very complex: Θ(Ν²) comparaisons, and O(N²) swaps.
--
__Pascal Bourguignon__ http://www.informatimago.com/
HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.
This program is very very very bad, no technology, very simple mind,
very simple algorithm, and no locality!!!! Please forgive me, and
forget this code, after several years, it will be your nightmare!
Registered User wrote:
What is the name of the following sorting method?
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (a[i]>a[j])
swap(&a[i], &a[j]);
It seems to be the opposite of bubble sort, with lighter elements going
in their proper positions first. However, this one does not compare
a[j] with a[j+1], as the normal bubble sort does.
Looks very simple, and I wonder why I couldn't find it anywhere on the
net!
I think it is closer to a standard bubble sort than to a selection
sort. Here is a selection sort:
#include <stdlib.h /* for size_t */
/* flavor to taste */
typedef double e_type;
void selection_sort(e_type * array, size_t n)
{
size_t i,
j;
e_type tmp;
if (n < 2)
return;
for (i = 0; i < n - 1; i++) {
int smallest_index = i;
e_type smallest_value = array[i];
for (j = i + 1; j < n; j++)
if (array[j] < smallest_value) {
smallest_value = array[j];
smallest_index = j;
}
tmp = array[i];
array[i] = array[smallest_index];
array[smallest_index] = tmp;
}
}
/*
P.S.
Selection sort is unbelievably lame. It is better than some others
when you have huge objects because it reduces exchanges to a small
value. However, if you make it a pointer based sort, then that small
advantage vanishes.
In short, it's lame. Not as lame as the OP's sort, but lame
nonetheless.
P.P.S.
Lame, lame, lame, lame, lame. And did I mention lame?
P.P.P.S.
IMO-YMMV
*/
Snis Pilbor wrote:
Registered User wrote:
>What is the name of the following sorting method?
for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (a[i]>a[j]) swap(&a[i], &a[j]);
It seems to be the opposite of bubble sort, with lighter elements going in their proper positions first. However, this one does not compare a[j] with a[j+1], as the normal bubble sort does.
Looks very simple, and I wonder why I couldn't find it anywhere on the net!
I doubt this has a name, but most people would call it something like
"the naive O(n^2) sorting algorithm". In otherwords, it's a lousy
sorting algorithm. It IS simple, because it just does it by brute
force. It's extremely slow.
It's not all that much worse than any other O(n^2) algorithm.
In particular, although it looks much worse than a select sort, it is
actually only slightly worse. For any given run of the inner loop,
the probability of the condition being true on each individual
iteration decreases as you go through that loop, because a[i] gets
smaller and smaller every time you swap.
So actually, this algorithm, except in perhaps a few degenerate cases,
is not much worse than select sort at all. Granted, select sort is
not that great in the first place.
By the way, I am sure I am not the only one to have come up with it,
but I was quite proud of myself when I came up with this exact sort
in high school. I liked it because (I believe) it's more efficient
than bubble sort in practice and it's extremely easy to remember and
key in quickly. So if you are on a system with no built-in sort
function (admittedly less common a situation these days than when I
was in high school 20 years ago...), and if you're only sorting 10
elements, it could be useful.
- Logan
Logan Shaw <ls**********@austin.rr.comwrites:
Snis Pilbor wrote:
>Registered User wrote:
>>What is the name of the following sorting method?
for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (a[i]>a[j]) swap(&a[i], &a[j]);
It seems to be the opposite of bubble sort, with lighter elements going in their proper positions first. However, this one does not compare a[j] with a[j+1], as the normal bubble sort does.
Looks very simple, and I wonder why I couldn't find it anywhere on the net!
I doubt this has a name, but most people would call it something like "the naive O(n^2) sorting algorithm". In otherwords, it's a lousy sorting algorithm. It IS simple, because it just does it by brute force. It's extremely slow.
It's not all that much worse than any other O(n^2) algorithm.
Yes it is.
Because most of the other O(n²) algorithms are Ω(n).
Only the selection sort is both O(n²) and Ω(n²) and that's why I'm
saying this is some kind of selection sort.
By the way, I am sure I am not the only one to have come up with it,
but I was quite proud of myself when I came up with this exact sort
in high school. I liked it because (I believe) it's more efficient
than bubble sort in practice and it's extremely easy to remember and
key in quickly. So if you are on a system with no built-in sort
function (admittedly less common a situation these days than when I
was in high school 20 years ago...), and if you're only sorting 10
elements, it could be useful.
Bubble sort is Ω(n). We cannot do much better...
When you need to sort data that is already mostly sorted, bubble sort
is a good choice.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.
On Fri, 6 Oct 2006, Pascal Bourguignon wrote:
Logan Shaw <ls**********@austin.rr.comwrites:
>>Registered User wrote:
for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (a[i]>a[j]) swap(&a[i], &a[j]);
It's not all that much worse than any other O(n^2) algorithm.
Yes it is.
Because most of the other O(n²) algorithms are Ω(n).
/All/ comparison-based sorting algorithms are Omega(n), for obvious
reasons. (BTW, don't use crazy character sets on Usenet. They interfere
with some newsreaders' displays.)
Only the selection sort is both O(n²) and Ω(n²)
Don't be silly. Plenty of algorithms are both O(n^2) and Omega(n^2)
(i.e., an asymptotically tight bound, or Theta(n^2)).
and that's why I'm saying this is some kind of selection sort.
I agree with Logan that it doesn't need a name.
-Arthur
Logan Shaw wrote:
Snis Pilbor wrote:
Registered User wrote:
What is the name of the following sorting method?
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (a[i]>a[j])
swap(&a[i], &a[j]);
(snip)
By the way, I am sure I am not the only one to have come up with it,
but I was quite proud of myself when I came up with this exact sort
in high school. I liked it because (I believe) it's more efficient
than bubble sort in practice and it's extremely easy to remember and
key in quickly. So if you are on a system with no built-in sort
function (admittedly less common a situation these days than when I
was in high school 20 years ago...), and if you're only sorting 10
elements, it could be useful.
Not to belittle you or anything, but what is to be proud of? This is
about as straightforward as it gets- I have trouble thinking of a MORE
straightforward, brainless way of doing the sort, short of maybe
specifically finding the lowest entry and putting it at the bottom of a
new array, then the 2nd lowest, etc., then copying the new array onto
the original. I mean, in terms of ingenuity involved, the OP's sort
algorithm is about one or two steps above "Hello, world!"
Snis Pilbor wrote:
Logan Shaw wrote:
>>Snis Pilbor wrote:
>>>Registered User wrote:
What is the name of the following sorting method?
for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (a[i]>a[j]) swap(&a[i], &a[j]); (snip)
By the way, I am sure I am not the only one to have come up with it, but I was quite proud of myself when I came up with this exact sort in high school. I liked it because (I believe) it's more efficient than bubble sort in practice and it's extremely easy to remember and key in quickly. So if you are on a system with no built-in sort function (admittedly less common a situation these days than when I was in high school 20 years ago...), and if you're only sorting 10 elements, it could be useful.
Not to belittle you or anything, but what is to be proud of? This is
about as straightforward as it gets- I have trouble thinking of a MORE
straightforward, brainless way of doing the sort, short of maybe
specifically finding the lowest entry and putting it at the bottom of a
new array, then the 2nd lowest, etc., then copying the new array onto
the original. I mean, in terms of ingenuity involved, the OP's sort
algorithm is about one or two steps above "Hello, world!"
_QBasic Programming for Dummies_ (my first programming book) actually
claims this one is not too bad. What could they be comparing it
against? (IIRC, Knuth gives an O(n^3) algorithm as the one with the
shortest MIX program.)
--
Simon Richard Clarkstone: s.************@durham.ac.uk/s?m?n.cl?rkst?n?@
hotmail.com ### "I have a spelling chequer / it came with my PC /
it plainly marks for my revue / Mistake's I cannot sea" ...
by: John Brophy (at: http://www.cfwf.ca/farmj/fjjun96/)
Simon Richard Clarkstone <s.************@durham.ac.ukwrote:
>>Registered User wrote:
What is the name of the following sorting method?
for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (a[i]>a[j]) swap(&a[i], &a[j]);
_QBasic Programming for Dummies_ (my first programming book) actually
claims this one is not too bad. What could they be comparing it
against?
Belgian Sort?
Richard
"Richard Bos" <rl*@hoekstra-uitgeverij.nlwrote in message
news:45****************@news.xs4all.nl...
Simon Richard Clarkstone <s.************@durham.ac.ukwrote:
>>>Registered User wrote:
What is the name of the following sorting method?
for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (a[i]>a[j]) swap(&a[i], &a[j]);
>_QBasic Programming for Dummies_ (my first programming book) actually claims this one is not too bad. What could they be comparing it against?
Belgian Sort?
Richard
If it looks greek to a london cabbie then in cockney rhyming slang that
would be bubble* sort
*bubble and squeak = greek
hopefully that clears up the nationality of this sort This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: mike |
last post by:
If I had a date in the format "01-Jan-05" it does not sort properly
with my sort routine:
function compareDate(a,b)
{
var date_a = new Date(a);
var date_b = new Date(b);
if (date_a < date_b)...
|
by: Petterson Mikael |
last post by:
Hi,
I have the following package names ( in an xml) that I will transform to
html. I need to sort them.
<package name="se.company.product.subproduct.boam.fpx.testsignals">
<package...
|
by: Xah Lee |
last post by:
Sort a List
Xah Lee, 200510
In this page, we show how to sort a list in Python & Perl and also
discuss some math of sort.
To sort a list in Python, use the “sort” method. For example:
...
|
by: Prasad Karunakaran |
last post by:
I am using the C# DirectoryEntry class to retrieve the Properties of
an user object in the Active Directory. I need to get the First Name
and Last Name as properties. I know it is not supported...
|
by: Pete Davis |
last post by:
A different question this time. I have a DataGrid bound to a collection. Is
there any way for me to allow sorting? The DataGrid.AllowSorting=true
doesn't work, but that's probably because it can't...
|
by: Jeoryos |
last post by:
Well here is some code that will help explain the situation:
I first make a struct that actually will be used to save some server
informations:
struct Server {
public String IP;
public int...
|
by: ami |
last post by:
Hi everyone,
I have a question about dynamically adding columns to a gridview.
Based on user input (after a button click), some columns are being
added to my gridview.
What I do:
...
|
by: abracadabra |
last post by:
I am reading an old book - Programming Pearls 2nd edition recently. It
says, "Even though the general C++ program uses 50 times the memory
and CPU time of the specialized C program, it requires...
|
by: KevinADC |
last post by:
Introduction
In part one we discussed the default sort function. In part two we will discuss more advanced techniques you can use to sort data. Some of the techniques might introduce unfamiliar...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: jfyes |
last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
|
by: ArrayDB |
last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
by: af34tf |
last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
| |