Bubble Sort

1) In bubble sort, we start from left to right and move the largest element to right.
2) In next round, we again start from left to right but stop at right - 1
3) In next round, , we again start from left to right but stop at right - 2
4) Ideally bubble sort is called bubble sort because when we so many bubbles in a jar, the biggest bubble reaches at the top.

public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>1; out--) // outer loop (backward)
for(in=0; in<out; in++) // inner loop (forward)
if( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort


Efficiency :- O(N2) as there are two loops

Selection sort

In this sort, we basically compare 1st element in an array with every other element and replace the 1st element with the smallest element found in the whole array. If there is no smaller element found, we leave the 1st element as it is and move on to the next element and again perform the same steps.

Selection Sort:-

In selection sort, we basically starts from left to right and keep a pointer on smallest element as the first element.
As we traverse from left to right, we compare every element with the pointer and swap the position if pointer element>current elemement.
In next round, we again start from left to right and starting point this time becomes leftmost element +1

public void selectionSort()
{
int out, in, min;
for(out=0; out<nElems-1; out++) // outer loop
{
min = out; // minimum
for(in=out+1; in<nElems; in++) // inner loop
if(a[in] < a[min] ) // if min greater,
min = in; // we have a new min
swap(out, min); // swap them
} // end for(out)
} // end selectionSort()

Efficiency :- O(N2) as there are two loops but unlike bubble sort, this is much fast as there are less swaps involved.

Invariant:- In the selectSort.java program, the data items with indices less than or equal to out
are always sorted.

Check if an integer is power of 2

Algo 1

public boolean checkpoweroftwo(int a) {

                    if (a <= 0) {

                        return false;

                    }

                    return (a & (a - 1)) == 0;

       }

Algo 2

public boolean checkpoweroftwo(int a) {

                    if (a <= 0) {

                        return false;

                    }

      return Integer.bitCount(n) == 1;

       }

Check if two Strings are Anagram

   public boolean isItAnagram(String one, String two){
   
  if(one.length()!=two.length())
  return false;

  char[] oneArray = one.toLowerCase().toCharArray();
  char[] twoArray = two.toLowerCase().toCharArray();

  Arrays.sort(oneArray);
  Arrays.sort(twoArray);

  if(Arrays.equals(oneArray, twoArray))
     return true;

  return false;
   }

How Bits and Bytes Work

http://computer.howstuffworks.com/bytes4.htm