Re: problem in solving this.

Ron Shepard <ron-shepard@xxxxxxxxxxxxxxxxxx> wrote:
In article
<6d126afa-6244-4cdd-a2db-66aa4e39cd12@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
e p chandler <epc8@xxxxxxxx> wrote:

A very simple form of the algorithm is

repeat
set flag to false
for i = first index to next to last index
if x(i) > x(i+1) then
swap x(i) and x(i+1)
set flag to true
next i
until flag is false
(snip)

To my eye, this looks more like a selection sort than an insertion
(bubble) sort. The tell is that in the first pass, the largest
element is selected and placed at the end of the array.

It looks like bubble sort to me. The distinguishing
feature is that bubble sort always exchanges adjacent
elements in the array. Larger elements bubble up
toward the top. Selection sort is slightly different,
in that you go through the array and select the largest
element, then exchange that with the last element.
One swap per pass. Insertion sort is also one swap
per pass through the array.

On the
second pass, the second largest element is selected and placed in
the N-1 position in the array. But the inner for loop always goes
over the full range. However, it has the feature that for correctly
sorted input, there are only N comparisons with no interchanges,
followed by termination. This is also the way bubble sort behaves.

As you say, there are small changes that can be made. For bubble
sort, you remember on each pass where the last exchange was done,
such that the following pass doesn't need to go up to that point.

-- glen



.

Relevant Pages

  • Re: [C++] Binary Search Confusion
    ... > all the information (bubble sort) once all the information is entered. ... then the array which stores those numbers is bubble sorted (in ... way we have the exact same program with the exact same numbers as you have. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Whats the best language to learn...
    ... Aren't you confusing insertion sort with merge sort here? ... The basic bubble sort *always* requires n-1 passes through the array ...
    (comp.programming)
  • Re: Trying Something New To Experiment with
    ... array, so that I have two identical integer arrays. ... I want to sort the first array with an un-optimized bubble ... Optimized bubble sort? ...
    (comp.lang.c)
  • Re: User Defined type()
    ... Swap indices when sorting, not element values. ... keep a separate array of indices and swap them around as you sort ...
    (microsoft.public.vb.general.discussion)
  • Re: quick sort
    ... The following is the quick sort function which i have seen in my note ... choice of which elements to swap. ... toward the beginning of the array. ... using a bubblesort, which has fewer overheads. ...
    (comp.lang.c)