Bubble Sort Algorithm - Printable Version

Bubble Sort Algorithm - Printable Version

+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: C, C++, & Obj-C (https://sinister.li/Forum-C-C-Obj-C)
+--- Thread: Bubble Sort Algorithm (/Thread-Bubble-Sort-Algorithm)

Pages: 1 2

Bubble Sort Algorithm - TheUninvited_mybb_import15721 - 03-14-2014

I felt like writing a sorting algorithm, so i present to you the bubble sort algorithm:

Code:
// Bubble Sort

    bool bDone = false; // this flag will be used to check whether we have to continue the algorithm

    printArray(array, size, "-"); // print the initial array

    while (!bDone)
    {
        bDone = true; // assume that the array is currently sorted

        for (int i = 0; i != size - 1; ++i) // for every element in the array  
        {
            if ( array[i] > array[i + 1] ) // compare the current element with the following one
            {
                // They are in the wrong order, swap them
                T tmp = array[i];
                array[i] = array[i+1];
                array[i+1] = tmp;

                bDone = false; // since we performed a swap, the array needs to be checked to see if it is sorted
                               // this is done in the next iteration of the while

                printArray(array, size, "-"); // print current array to show the steps done by the algorithm
            }
        }
    }

    printArray(array, size, "-"); // print final array

RE: Bubble Sort Algorithm - Psycho_Coder - 03-14-2014

Well there are many bubble sort code snippets on HC and so this post was a bit unnecessary but now that you have posted submit it here if you like :-

http://www.hackcommunity.com/Thread-Resource-Source-Code-of-Some-Well-Known-Algorithms

RE: Bubble Sort Algorithm - ArkPhaze - 03-15-2014

Not bad, I'd make a few minor changes though:

Code:
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int main()
{
  int arr[] = {1, 3, 9, 2, 5, 8, 7, 4, 6};
  size_t len = sizeof(arr) / sizeof(arr[0]);
  bool finished; size_t i;
  do {
    finished = true;
    for (i = 0; i < len; ++i) {
      if (arr[i] <= arr[i + 1]) continue;
      arr[i] ^= arr[i + 1];
      arr[i + 1] ^= arr[i];
      arr[i] ^= arr[i + 1];
      finished = false; break;
    }
  } while (!finished);

  for (size_t i = 0; i < len; ++i)
    printf("%d ", arr[i]);
}

The other optimal way to do this would be to use a function to immediately return from that nested part, or use a goto.

RE: Bubble Sort Algorithm - invisal - 03-17-2014

@ArkPhaze, why would you prefer XOR swap over using temporary variable?

I don't know why we have many "Bubble Sort" post. Bubble Sort performance
is bad except on a few special case and it isn't the simplest sort algorithm
to implement. Selection Sort averagely perform better and its performance
is consistence. Moreover, it is easier to implement than Bubble Sort.

@TheUninvited, I suggest you make a tutorial on a better general-purpose sort
algorithm such as "Insertion Sort", "Shell Sort", "QuickSort", "MergeSort",
"HeapSort" or "Radix Sort".

RE: Bubble Sort Algorithm - ArkPhaze - 03-17-2014

(03-17-2014, 01:30 PM)invisal Wrote: @ArkPhaze, why would you prefer XOR swap over using temporary variable?

I don't know why we have many "Bubble Sort" post. Bubble Sort performance
is bad except on a few special case and it isn't the simplest sort algorithm
to implement. Selection Sort averagely perform better and its performance
is consistence. Moreover, it is easier to implement than Bubble Sort.

@TheUninvited, I suggest you make a tutorial on a better general-purpose sort
algorithm such as "Insertion Sort", "Shell Sort", "QuickSort", "MergeSort",
"HeapSort" or "Radix Sort".

Because it's fast, easy and clean IMO.

It's still good to know various sort algorithms though. Only then can you understand the benefits of each because you can compare it to others that may not work as well in a particular case. At the expense of structuring an AVL tree, I personally like using that particular BST to sort in some cases, because of how versatile it is with what you can do.

RE: Bubble Sort Algorithm - invisal - 03-18-2014

@ArkPhaze

XOR is not easy and clean

Not everyone know XOR swap. Those who do not know it, will not
understand your code. Hence, it reduces the readability of your code.
XOR works only with Integer, if you try to swap other data type,
you need to use ugly work around.

Code:
float a = 2.5f; float b = 3.0f; *((int*)&a) ^= *((int*)&b); *((int*)&b) ^= *((int*)&a); *((int*)&a) ^= *((int*)&b); std::cout << a << std::endl; std::cout << b << std::endl;

XOR is not faster

On modern CPU architectures, the XOR technique is considerably slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute instructions in parallel via instruction pipelines. In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order. If efficiency is of tremendous concern, it is advised to test the speeds of both the XOR technique and temporary variable swapping on the target architecture. (Source)

RE: Bubble Sort Algorithm - ArkPhaze - 03-18-2014

Not everyone understands bitwise operations in general, but that's simply no reason to avoid them. If you want to be picky, then here:

Code:
inline void swap (int &x, int &y) { x ^= y; y ^= x; x ^= y; }

That problem is solved for readability. Integer or not, that's irrelevant here, why consider other datatypes here for a reason NOT to use XOR? That's invalid logic IMO, although the other points are true. For instance, you can't add strings in the traditional sense, like you can with C# in contrast with C/C++; you can't use + to concatenate without overloading it, but that's no reason to avoid using the + operator...

This also depends slightly on compiler optimization, but in addition to the above, in cases that may not apply here but are still valid for using XOR:

Code:
Reasons for use in practice

In most practical scenarios, the trivial swap algorithm using a temporary register is more efficient. Limited situations in which XOR swapping may be practical include:

    On a processor where the instruction set encoding permits the XOR swap to be encoded in a smaller number of bytes;
    In a region with high register pressure, it may allow the register allocator to avoid spilling a register.
    In microcontrollers where available RAM is very limited.

Because these situations are rare, most optimizing compilers do not generate XOR swap code.

And by clean, I meant not having a new variable created where a constructor is called and the destructor to destroy it after it becomes useless. This depends on the scope you're performing such a calculation in however as to when the convenience of such occurs. Such micro optimization is not necessary for comparison IMO, given the small tradeoff's of using XOR. I never said it was "faster" either.

RE: Bubble Sort Algorithm - invisal - 03-18-2014

@ArkPhaze

Quote:Integer or not, that's irrelevant here, why consider other datatypes here for a
reason NOT to use XOR? That's invalid logic IMO

It is if you want to be generic. A generic XOR swap function
does not work with anything except Integer.

Code:
template<typename T>
inline void Swap(T& a, T& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

Quote:And by clean, I meant not having a new variable created where a
constructor is called and the destructor to destroy it after it
becomes useless.

You can create function and it solve the problem. Although
temporary variable is still there, but it does not visible to you
when you use the swap. So it is clean.

Code:
template<typename T>
inline void Swap(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

Quote:For instance, you can't add strings in the traditional sense, like you can
with C# in contrast with C/C++; you can't use + to concatenate without
overloading it, but that's no reason to avoid using the + operator...

I find it is irrelevant.

RE: Bubble Sort Algorithm - ArkPhaze - 03-18-2014

The semantics of hiding the implementation is based on the function, so thus there's no real difference in terms of readability when you utilize a function to encapsulate what you're doing.

Quote:I find it is irrelevant.

It's completely relevant. Generics aren't all the greatest thing either, so to limit a method and point out that it doesn't work in a generic scenario with templates is not the greatest standpoint. We don't have generic operators, we have the ability to overload it if we want, that doesn't mean an overload for *everything* has to exist for something to be good.

RE: Bubble Sort Algorithm - Deque - 03-18-2014

Quote:I don't know why we have many "Bubble Sort" post. Bubble Sort performance
is bad except on a few special case and it isn't the simplest sort algorithm
to implement. Selection Sort averagely perform better and its performance
is consistence. Moreover, it is easier to implement than Bubble Sort.

Selection sort is not stable. Bubblesort is.
Bubblesort performs much better on nearly sorted data than selection sort. So you might prefer it if you know that your data will be nearly sorted.
Bubblesort can be easier implemented with e.g. linked lists as you just operate with your pointer on two consecutive nodes.
So it has its applications. No need to disregard it.