[Deadbyte]

Algorithm Series - 1 | Bubble Sort

Intro
Competition programming is a field that generally involves the host presenting a set of logical or mathematical problems to the contestants , a field that I'm good at. I've participated in many high school and college contest like the International Olympiad of Informatics and won some medals. So I decided to contribute some of my knowledge to HF and I wasn't sure where to start the series Coding and Programming or C/C++/Obj-C Programming. Since I will be implementing the algorithms in C++ I will start it in this section. Notice I have some limitations because of my low post count.

Bubble Sort
A simple sorting algorithm.The bubble sort algorithm compares every two items which are next to each other, and swaps them if they are in the wrong order. An array of n elements can be sorted within n-1 passes. For example, in this array of 4 items:

First pass:
(4, 3, 1, 2) → (3, 4, 1, 2)
(3, 4, 1, 2) → (3, 1, 4, 2)
(3, 1, 4, 2) → (3, 1, 2, 4)

Second pass:
(3, 1, 2, 4) → (1, 3, 2, 4)
(1, 3, 2, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)

Third pass:
(1, 2, 3, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)

Implementation in C++

PHP Code


<?php 
//Algorithm Series 1 - Bubble Sort 
//Deadbyte
#include<iostream>
using namespace std;

int main()
{
    int n;
    cout << "Enter the number of elements of the array: ";
    cin >> n;
    int ar[n];
    cout << "Enter the elements of the array: ";
    for(int i=0;i<n;i++)
    {
            cin >> ar[i];
    }
    int tmp;
    for(int i=0;i<n;i++)
      for(int j=i+1;j<n;j++)
      {
              if(ar[i]>ar[j])
              {
              tmp=ar[i];
              ar[i]=ar[j];
              ar[j]=tmp;
              }
      }
    cout << "The sorted array is: " << endl;
    for(int i=0;i<n;i++)
    {
            cout << ar[i] << "  ";
    }
    system("pause");
    return 0;
} 


Code analysis

PHP Code


<?php 
// Declaration and input
    int n;
    cout << "Enter the number of elements of the array: ";
    cin >> n;
    int ar[n];
    cout << "Enter the elements of the array: ";
    for(int i=0;i<n;i++)
    {
            cin >> ar[i];
    } 


We declare the variable n which marks the number of elements we will have in the array.
We declare the variable ar which is the array.
With a loop we enter the elements of the array , a loop that iterates n times.

PHP Code


<?php 
//Swapping the elements
    int tmp;
    for(int i=0;i<n;i++)
      for(int j=i+1;j<n;j++)
      {
              if(ar[i]>ar[j])
              {
              tmp=ar[i];
              ar[i]=ar[j];
              ar[j]=tmp;
              }
      } 


We create a nested loop that compares the "i" and the "i+1" element. If "i" is bigger than "i+1" we replace their places with the help of a third temporary variable that we declared tmp.

PHP Code


<?php 
//Output
  cout << "The sorted array is: " << endl;
    for(int i=0;i<n;i++)
    { 


We output the sorted array.


Thank you for reading. I hope the series will help the beginners in competition programming.

[Deadbyte]

So these are "Problems" you had to make a solution for in Competitive programming ?
I'll be doing this in C# just to get the feel for it XD thanks for sharing.

Bubble Sort is used in various problems to sort the elements in an array so think it as an important segment that occurs in many problems.

[Platypusؚ]

The explanation is a little confusing when you demonstrate the passes. Perhaps highlight (bold) the numbers you are swapping at the time? Overall, if you are doing "competitive" programming, you wouldn't use bubble sort. Bubble sort is one of the worst sorting algorithms you can use. Nice little tutorial, but you should mention its complexity and why you should avoid it.

More info here: http://bigocheatsheet.com/

[Deadbyte]

Well normally in a competition you would not use any handwritten sorting algorithm just #include<algorithm> and use sort(array,array+size) but yea I got your point I will modify it soon. 😁

[Platypusؚ]

Well normally in a competition you would not use any handwritten sorting algorithm just #include<algorithm> and use sort(array,array+size) but yea I got your point I will modify it soon. 😁

I'm saying if you are going to be teaching new or less-experienced programmers about sorting algorithms, you should stress that they need the right tool for the right job. It's naive to see a problem that requires number sorting, and automatically think: "Bubble-Sort!". Much like it is naive to be given a programming problem and automatically assume your data structure will consist of a linked list.

[Deadbyte]

I'm saying if you are going to be teaching new or less-experienced programmers about sorting algorithms, you should stress that they need the right tool for the right job. It's naive to see a problem that requires number sorting, and automatically think: "Bubble-Sort!". Much like it is naive to be given a programming problem and automatically assume your data structure will consist of a linked list.

I agree, I was thinking on doing Sieve of Eratosthenes next. I'll give more info next time. Thanks for the advice.

[asmy]

Lessons wonderful
I hope that you will continue

[0xDEAD10CC]

Bubble sort is pretty much all but useless and very inefficient.

[Deadbyte]

Bubble sort is pretty much all but useless and very inefficient.

I agree but I wanted to start with the simplest ones. 😁

[csrk]

You should mention that this sorting algorithm is only effective for small collections. If you have a very large collection it can take a really long time to sort it using this algorithm.

[Deadbyte]

You should mention that this sorting algorithm is only effective for small collections. If you have a very large collection it can take a really long time to sort it using this algorithm.

Thank you for the reply and will modify it soon.