Re: Sorting


"Malcolm McLean" <regniztar@xxxxxxxxxxxxxx> ha scritto nel messaggio
news:eLmdnR7M5KYws67bnZ2dnUVZ8vWdnZ2d@xxxxxxxxx

"Army1987" <please.ask@xxxxxx> wrote in message
news:f0v338$32j$1@xxxxxxxxxxxxxxx

"Malcolm McLean" <regniztar@xxxxxxxxxxxxxx> ha scritto nel messaggio
news:77OdnWahTNmt5a_bRVnyvwA@xxxxxxxxx
There are lots of ways of sorting.
The easiest, probably, is to go through the array. Compare the number
you are on with the number above it. If they are in the wrong order,
swap them. Then go back to the start of the array and do it again, until
you make a clean sweep without swapping. Set a flag when you swap, and
clear it each time you restart.
This algorithm is called bubblesort.

What the hell? "Easiest"? I would have never thought of anything
similar, and when I was taught about it, I wandered why did anybody
bother to think and implement such a horrid algorithm. The answer
"it's a didactic toy" is the one which convices me best. It is even
less efficient than selection sort or insertion sort, which are
more human-comprehensible. (Which do you use to physically sort a deck of
playing cards? I don't believe you use bubblesort.)

The algorithm isn't conceptually the simplest. But there is no memory
management to speak of, so it is generally easier to implement.

Easier than what? What memory management is below?

size_t find_max(int array[], size_t length);
void selection_sort(int array[], size_t length)
{
size_t m;
for( ; length > 0; length--, array++) {
m = find_max(array, length);
if (m != 0) {
int tmp = array[0];
array[0] = array[m];
array[m] = tmp;
}
}
return;
}

size_t find_max(int array[], size_t length)
{
size_t i, result = 0;
for (i=1; i<length; i++)
if (array[i] > array[result])
result = i;
return result;
}


.

Relevant Pages

  • Re: Okay to move an "object" will-nilly?
    ... I wrote a funky kind of algorithm for sorting an array (whether ... the objects in the array must be move safe. ... the array was already sorted so no swaps were performed by the sort. ...
    (comp.lang.c)
  • Re: Fastcode poll - Should Sort include worst case situations
    ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
    (borland.public.delphi.language.basm)
  • Re: Hash table in C++? STL?
    ... The Oalgorithm is when you scan all ... > Assume array a and b both have N elements, ... > Will a binary search beat a hash lookup? ... Running time O) for the sort if using ...
    (comp.lang.cpp)
  • Re: Sorting
    ... Then go back to the start of the array and do it again, until you make a clean sweep without swapping. ... This algorithm is called bubblesort. ... less efficient than selection sort or insertion sort, ...
    (comp.lang.c)
  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
Loading