mojo666's Profile User Rating: -----

Reputation: 361 Architect
Group:
Expert
Active Posts:
796 (0.39 per day)
Joined:
27-June 09
Profile Views:
12,147
Last Active:
User is offline Yesterday, 10:54 PM
Currently:
Offline

Previous Fields

Country:
US
OS Preference:
Windows
Favorite Browser:
Mozilla
Favorite Processor:
Who Cares
Favorite Gaming Platform:
PC
Your Car:
Who Cares
Dream Kudos:
0
Expert In:
Computer Science

Latest Visitors

Icon   mojo666 has not set their status

Posts I've Made

  1. In Topic: Resolution Method - Propositional Calculus

    Posted 29 Jan 2015

    Can you provide the full example so we have a better idea of what you are talking about? What are the premises and what is the conclusion?
  2. In Topic: What Is the Bubblesort?

    Posted 28 Jan 2015

    Quote

    No, I've pointed out the earliest definitions. The curious nature of the algorithm is the number of definitions that have been applied. Apply one, and it's a bogo sort


    What definition has been applied to bubble sort that makes it a bogosort?

    Most of the samples you provide contradict your claim. The reason you see a lot of people using your version is because it is a valid version of bubble sort. This doesn't mean it is the only version.

    Quote

    Bubble sort is a sorting algorithm that works by repeatedly stepping through lists that need to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. This passing procedure is repeated until no swaps are required, indicating that the list is sorted.
    -- http://www.techopedi...757/bubble-sort

    For some reason you left out the next sentence: "Bubble sort gets its name because smaller elements bubble toward the top of the list." As I said, you can remove the check and the "bubbling" remains thus it is still a bubble sort. The name still applies.

    Quote

    I like this one, nice a clear:

    Quote

    Algorithm
    1. Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
    2. If at least one swap has been done, repeat step 1.
    -- http://www.algolist....ing/Bubble_sort


    And the first link under visualizers presents a version without a swap check, so this person does not believe the swap check is a defining feature.

    Quote

    Iverson, the guy most responsible for coining the name, says:

    Quote

    It is clear the v(x)-1 stages suffice, but it is advantageous to allow termination at the end of the first stage during which no transpositions occur.
    -- A Programming Language, Kenneth Iverson


    Maybe it's because I don't have the context of this quote in front of me, but it looks like Iverson is saying the check is not required. He seems to be treating it as a convenient add on and we can instead just loop n-1 times. Again, this is analogous to quicksort. If I wrote the first quicksort and while describing it said "It is sufficient to select the left most element as the pivot, but it is advantageous to choose the middle element." would that mean that people who chose the left most element are using a "faux" quicksort?

    The check has no relevance to the algorithm. Is it a neat feature? Sure. Is it advisable to include it in your bubble sort? Of course. Does its presence or absence define the algorithm? Absolutely not. This trick can be added to a lot of sorting algorithms. Go look at other sorting algorithms and add code to check if it is sorted before proceeding. Did you just create a new algorithm or did you just optimize an existing algorithm? If we are going to define algorithms by such strict criteria as to be tied to their implementations rather than their characteristic execution, then it becomes useless to even talk about algorithms as we will quickly be buried by a ton of unique names over a handful of not-so-unique concepts.
  3. In Topic: What Is the Bubblesort?

    Posted 26 Jan 2015

    Quote

    Agreed. That is why I find the double looped, no exchange checking things being called bubble sorts horribly confusing.


    At the very least you should be able to recognize that these "things" are more like a bubble sort than a selection sort. They have almost nothing in common with selection sorts, but almost everything in common with the "true" bubble sort. So long as the inner loop goes the same direction, all of these implementations will make the same swaps and the same relevant comparisons (comparisons that may lead to a swap). The only difference is that they will have varying irrelevant comparisons (comparisons that cannot lead to a swap). None of these implementations make the same swaps or comparisons as a selection sort apart from occasional coincidental inputs. Clearly, these implementations cannot be classified as selection sorts when bubble sort is a much better match.

    Quote

    If you wish do ignore this characteristic, that's your prerogative. There are many later sources do ignore this; I simply assert that they're wrong. That's why I wrong that entire bloody research paper linked to by the OP.


    Your assertion is based on nothing. All you've done is point to an early implementation and decreed that other implementations are incorrect. An algorithm's definition is independent of it's implementation. Early implementations of quick sort used the left most element as the pivot. If I use the middle element, is it no longer a quick sort? Changing how the pivot is selected does not change the characteristics of the algorithm's execution. The bubble sort is named after the swapping pattern performed by the algorithm. Removing the swap check has no effect on this behavior, thus the check is not a necessary characteristic. The "bubbling" persists without the check, thus "bubble sort" remains an appropriate name for the algorithm.
  4. In Topic: What Is the Bubblesort?

    Posted 26 Jan 2015

    I think you are focusing on the wrong part of the algorithm. The potential early termination is not the defining feature that makes it a bubble sort. Such a feature can also be added to the selection sort, but this doesn't turn it into a bubble sort. The repeated swapping of adjacent items is the defining feature. Objects are moved throughout the entire array towards their final positions. This creates an effect analogous to heavier objects sinking and lighter objects floating, hence the names. Sure, the algorithm naturally gives us optimization options that may not be present in other algorithms, but the presence or absence of these optimizations do not define the algorithm being used. A bubble sort performs as many as n^2 swaps. A selection sort finds the smallest remaining object and swaps it to the appropriate position. The objects are barely moved and the algorithm performs no more than n swaps. I do remember what it was like to be a beginner. Pointing to a bubble sort and calling it a selection sort would have been terribly confusing.
  5. In Topic: What Is the Bubblesort?

    Posted 25 Jan 2015

    I would say both of these are optimizations of the bubble sort algorithm. "A" halts early when it detects the list is sorted, "B" does not loop over the portion of the list sorted by previous iterations, thus avoiding redundant comparisons. I don't see why these should be considered entirely different algorithms. They both have the same characteristic execution. The only notable difference is that the optimization on "A" changes the best case runtime. But if this is sufficient to be an entirely different algorithm then would it be correct to describe the following as something different from a mergesort?

    if(array is not sorted)
    {
      mergesort(array)
    }
    


    Quote

    And I have been told - and I have not verified - that some quicksort implementations will use bubblesort as a "last-pass" sort when the groups get down to some small n. I remember n in single digits, but it was a while ago. Obviously, the time penalty at some small n is going to vanish, but what's the reasoning for the switch? I have an idea in my head that it would save some recursive steps - say, four layers of recursion if n is 16 - and that save some stack frames, but that logic seems weak now that I think about it. Maybe someone who knows will correct me, that would be cool.


    I suppose for every stack frame you save, you can potentially double the size of the data the machine can sort, but if the data is large enough to challenge the boundaries of the computer/compiler then an unlucky pivot selection is going to cause an overflow anyways.

    Here are some reasons I can think of that make optimized bubble sort preferable for small sets of data. The worst case scenario for an optimized bubblesort occurs when the largest element is at the front of the list. The worst cases for a naive quicksort occurs when the data is already sorted, reversed, or the elements are the same. As the size of the data gets smaller, the chances of data being sorted or the same increases. This is bad for quicksort but good for bubble sort. The chance of reverse order is still present, but this is equally bad for quick sort and bubble sort. Any optimizations added to the quicksort algorithm to avoid these cases become stupidly expensive for small data sets. No only do they add a lot of overhead, but in addition to making worst case unlikely, they also make best case equally unlikely. For small sets of data, small deviations from optimal execution greatly increases the run time of quicksort. There is also the constant factor that gets ignored in big O analysis. Quicksort (especially optimized) requires a lot more instructions per iteration. If we say it uses k times as much code as bubblesort, at some small value quicksort's best case k*n*log(n) is going to be greater than bubblesort's worst case n*n.

My Information

Member Title:
D.I.C Addict
Age:
30 years old
Birthday:
July 23, 1984
Gender:
Interests:
Chess, math, computers, AI
Years Programming:
6
Programming Languages:
C++, C#, VB.net, SQL, OCAML, LISP, MIPS

Contact Information

E-mail:
Private
Website URL:
Website URL  http://

Friends

Comments

mojo666 has no profile comments yet. Why not say hello?