Bubble Sort

Bubble Sort 

Introduction

Bubble sort is a simple sorting algorithm that compares each pair of adjacent items and swaps them if they are in the wrong order.

The pass through the list is repeated until no swaps are required, which indicates that the list is sorted.

C code

#include <stdio.h>
void BubbleSort(int items[], int length);
void PrintArray(int items[],int length)
{
    printf("\n");
    for(int i=0; i < length; i++)
    {
        printf("%d ",items[i]);
    }
}
int main()
{
    int items[] = {1,4,5,-22,11,3};

    printf("Before sorting\n");
    PrintArray(items,6);
    printf("\n**********************\n");
    BubbleSort(items,6);
    printf("\n**********************\n");
    printf("after sorting\n");
    PrintArray(items,6);
 
    return 0;
}

void BubbleSort(int items[], int length)
{
    //iterate from first item (index 0) till 2nd last
   for(int i=0; i<length-1;i++)
   {
       //iterate from first item(index 0) till length-(i+1)
       for(int j=0; j<length-i-1;j++)
       {
           if(items[j] > items[j+1])
           {
               printf("\n swapping between %d and %d",j, j+1);
               items[j]= items[j] ^ items[j+1];
             
               items[j+1] = items[j] ^ items[j+1];
     
               items[j] = items[j] ^ items[j+1];
              PrintArray(items,6);
           }
       
       }
     
   }
 
}

 
 



http://onlinegdb.com/B1_F_nQsl

Complexity

Worst Case : О(n²)

Average Case : O(n²)

Best Case : O(n)  happens when the list is already sorted. But in this case insertion sort performs better than Bubble Sort.

Problem and Technical Approach

a. An array has N number of positive integers. All numbers occur even number of times exception one number which occurs odd number of times. Find the number.

void GetOddNumberInArray(int[] items)
        {
            var result = 0;
            foreach (var item in items)
            {
                result = result ^ item; //XOR

            }
            Console.WriteLine("Odd number in the list is {0}", result);
        }
b.  Check if 2 numbers are equal or not without equal operator.
   
     if(a XOR b)==0 then a & b are equal or Not.
c. Number is multiple of 4 Or Not
  public static void ValidateMultipleof4(int n)
        {
            var result = 1;
            for(int i=2; i<=n;i++)
            {
                result = result ^ i;
            }
            if (result == n)
                Console.WriteLine("Multiple of 4");
            else Console.WriteLine("Not multiple of 4");

        OR  (n>>2) is equivalent of division by 4 && again n<<2 is multiplication by 4. So if doing this 2 bit shift operation twice produces same result will be good enough to validate it is multiple of 4.

d. two same array with one missing number. find out missing one
    Do the XOR starting with 0. missing will come out.
e. Odd Number validation, do the & with 1, if output is 0 number is even.

LinkedList DataStructure

Introduction: Linked List is a linear collection of data elements, called nodes, each pointing to next node. Each node has value (data) and reference to next node. The first head is called head.

Advantages

Unlike array it is dynamic in nature as it can grow by allocating more memory and can shrink or reduce by deallocating the memory while the application is running.

Insertion & deletion are easily implemented. Item can be added or removed from anywhere in the sequence.

Disadvantages

It consumes more memory compared to array. Sequential access of the nodes.

Types

Singly Linked List: It contains nodes which have a data field and a next field which points to the next node in line of nodes. Last node point to the null.

Doubly Linked List: Apart from data & next field, its node has one additional field which point to the previous node.

Circular Linked List: Last node, instead of pointing to null, points to first node.

using System;

namespace DataStructure

{

    public interface ILinkedList<T>

    {

        void AddLast(Node<T> element);

        void Print();

        void AddAfter(Node<T> element, T value);

        void Delete(T value);

        

    }

    public class Node<T>

    {

        public Node<T> Next;

        public T Value;

    }

    public class SinglyLinkedList<T> : ILinkedList<T>

    {

        private Node<T> _head;

        private Node<T> _current;

        

        /// <summary>

        /// Add the element at the last

        /// </summary>

        /// <param name="element"></param>

        public void AddLast(Node<T> element)

        {

            if (_head == null) //LinkedList is empty so made it head

            {

                _head = element;

            }

            else

            {

                _current.Next = element;

            }

            _current = element;

        }

        /// <summary>

        /// Display the linkedlist

        /// </summary>

        public void Print()

        {

           

            var tmpNode = _head;

            while (tmpNode != null)

            {

                Console.WriteLine("Value stored:{0}",tmpNode.Value);

                tmpNode = tmpNode.Next;

            }

        }

        /// <summary>

        /// Add the node after the given value

        /// </summary>

        /// <param name="element"></param>

        /// <param name="data"></param>

        public void AddAfter(Node<T> element, T data)

        {

            var tmpNode = _head;

            while (tmpNode != null)

            {

                if(data.Equals(tmpNode.Value)) break;

                tmpNode = tmpNode.Next;

            }

            if(tmpNode==null) throw new Exception("data does not exist in the Linked List");

            element.Next = tmpNode.Next;

            tmpNode.Next = element;

        }

        public void Delete(T data)

        {

            var tmpNode = _head;

            if (tmpNode.Value.Equals(data))

            {

                _head = _head.Next;

                return;

            }

            while (tmpNode.Next != null)

            {

                if (data.Equals(tmpNode.Next.Value)) break;

                tmpNode = tmpNode.Next;

            }

            if(tmpNode.Next != null && tmpNode.Next.Next != null)

            tmpNode.Next = tmpNode.Next.Next;

            else //Last Node updatae _current position

            {

                tmpNode.Next = null;

                _current = tmpNode;

            }

        }

    }

    public class Program

    {

        public static void Main(string[] args)

        {

            Console.WriteLine("XXXX------Creating Linked List------XXX");

          

            var linkedList = new SinglyLinkedList<int>();

            linkedList.AddLast(new Node<int>() { Next = null, Value = 100 });

            linkedList.AddLast(new Node<int>() { Next = null, Value = 101 });

            linkedList.AddLast(new Node<int>() { Next = null, Value = 102 });

            linkedList.Print();

            Console.WriteLine("XXXX------Adding at the end------XXX");

            linkedList.AddLast(new Node<int>() { Next = null, Value = 103 });

          

            linkedList.AddLast(new Node<int>() { Next = null, Value = 105 });

            linkedList.AddLast(new Node<int>() { Next = null, Value = 109});

            linkedList.Print();

            Console.WriteLine("XXXX------Add after------XXX");

            linkedList.AddAfter(new Node<int>() { Next = null, Value = 106 },105);

            linkedList.Print();

            Console.WriteLine("XXXX------Deleting First Node------XXX");

            linkedList.Delete(100);

            linkedList.Print();

            Console.WriteLine("XXXX------Deleting Middle Node------XXX");

            linkedList.Delete(103);

            linkedList.Print();

            Console.WriteLine("XXXX------Deleting Last Node------XXX");

            linkedList.Delete(109);

            linkedList.Print();

            Console.WriteLine("XXXX------Adding after 105------XXX");

            linkedList.AddAfter(new Node<int>() { Next = null, Value = 111 }, 105);

            linkedList.Print();

           Console.WriteLine("XXXX------Adding at the Last------XXX");

            linkedList.AddLast(new Node<int>() { Next = null, Value = 120 });

            linkedList.Print();

            Console.WriteLine("XXXX------Adding at the Last------XXX");

            linkedList.AddLast(new Node<int>() { Next = null, Value = 121 });

            linkedList.Print();

            Console.ReadKey();

        }

    }

}

Detailed Analysis Wikipedia

              

Stack DataStructure

Introduction:  Stack is an abstract data type. It serves as a collection of elements and follow LIFO(last in first out) pattern. So every new added item goes on the top of the stack, and only top item can be removed first.

 It has main 2 operations

 push: This operation adds an element to the collection at the top

 pop: It removes the most recently added element that was not yet removed.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Stack

{

    public interface IStack<T>

    {

       void Push(T element);

        T Pop();

        void Print();

    }

    public class Stack<T> : IStack<T>

    {

        private T[] _items = new T[10] ;

        private int _top = -1;

        public void Push(T element)

        {

            if (_top < 9)

            {

                _items[++_top] = element;

                

            }

            else

            {

                throw new Exception("Stack is full. Item can't be added.");

            }

        }

        public void Print()

        {

            for (int i = _top; i > -1; i--)

            {

                Console.WriteLine("index:{0} item:{1}",i,_items[i]);

            }

        }

        public T Pop()

        {

            if (_top == -1)

            {

                throw new Exception("Stack is empty.");

            }

            return _items[_top--];

        }

    }

    public class Program

    {

        public static void Main(string[] args)

        {

            var stack = new Stack<int>();

            stack.Push(110);

            stack.Push(101);

            stack.Push(111);

            stack.Print();

            var item = stack.Pop();

            Console.WriteLine("Poped item :: {0}",item);

            stack.Print();

            stack.Push(200);

            stack.Print();

            Console.ReadKey();

        }

    }  

}

Complexity Analysis

                                push,pop: O(1) & search: O(n)

   

Queue Data Structure

 Introduction: Queue is an abstract data type. It serves as a collection of elements and follow FIFO (First in first out) pattern. So first element added to the queue will be the first one to be removed.

 It has main 2 operations

 Enqueue: This operation adds an element to the queue 

 Dequeue: It removes the item from the beginning of the queue.

using System;

namespace DataStructure

{

    public interface IQueue<T>

    {

        void Enqueue(T item);

        T Dequeue();

        void Print();

    }

    public class Queue<T> : IQueue<T>

    {

        T[] _items = new T[10];

       int _rear=-1;

        int _front =-1;

       

        public void Enqueue(T item)

        {

            if (_rear == 9)

                Console.WriteLine("queue overflow.");

            else

            {

                if (_front == -1) _front++;

                _items[++_rear] = item;

            }

        }

        public T Dequeue()

        {

            if (_front == -1 || _front > _rear)

            {

                Console.WriteLine("Queue underflow.");

                throw new Exception("Queue underflow");

            }

            else

            {

                return _items[_front++];

            }

        }

        public void Print()

        {

           if(_front==-1)

                Console.WriteLine("queue is empty");

           else

           {

               for (int i = _front; i <= _rear; i++)

               {

                    Console.WriteLine("Item {0}",_items[i]);

               }

           }

        }

    }

    public class Program

    {

        public static void Main(string[] args)

        {

            var queue = new Queue<int>();

            queue.Enqueue(100);

            queue.Enqueue(101);

            queue.Enqueue(150);

            queue.Print();

           Console.WriteLine("item dequeue:{0}", queue.Dequeue());

            queue.Print();

            queue.Enqueue(200);

            queue.Print();

            Console.ReadKey();

        }

    }

}