473,324 Members | 2,196 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

Name of sorting method

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!

Oct 6 '06 #1
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...)

Oct 6 '06 #2
"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.
Oct 6 '06 #3
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!
Oct 6 '06 #4
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
*/

Oct 6 '06 #5
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
Oct 6 '06 #6
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.
Oct 6 '06 #7

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
Oct 6 '06 #8

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!"

Oct 6 '06 #9
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/)
Oct 10 '06 #10
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
Oct 12 '06 #11

"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
Oct 12 '06 #12

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

22
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)...
3
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...
20
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: ...
1
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...
7
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...
4
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...
0
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: ...
7
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...
1
KevinADC
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...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
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...
0
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...
0
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...
1
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...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
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
0
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...
0
isladogs
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...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.