Skip to main content

Posts

Showing posts from December, 2016

Bubble sort Algorithm

Bubble sort is the most simple sorting technique used to sort arrays , linked list etc. It is an algorithm that keeps traversing the list until the list is completly sorted. Bubble sort has been occasionally referred to as a "sinking sort". The idea being that the larger elements are heavier hence they sink to the bottom of the list and smaller elements being light bubble to the top of the list.

Algorithm

In bubble we keep comparing 2 adjacent elements and swap their places is they are not in correct order.

Performance

Bubble sort being a simple algorithm works fine when the size of the data is small but its performance decreases as the size of the data increases, hence Bubble is used only when number of elements is small or only some elements are out of order.

To know more about bubble sort, its performance, complexity and comparisons to other sorting methods click Here.





C ProgramC++ ProgramJava programPython Program C Program C++ Program Java Program Python Program Sample input …

Stack implementation using Linked List

Stack is a data structure it serves as a collection of elements. It has 2 principle operation push and pop.Stack works on the principle of  Last In First Out or LIFO i.e the element that is entered last is removed first. To do this is has 2 methods  push() :  push operation pushes the element on the top.pop() :  pop operation removes the element on the top. This can be seen in  the below image.



Linked list is a simple linear data structure formed by collection of data elements called nodes. Each node consists of a data element and link field.The data field consists of element and link field consists of address of next element.

To know more about Stack Data Structure click here
To know more about Linked List click here
To view Simple Linked List implementation click here 
Now inorder to implement Stack using linked list we need to implement push and pop operation in Linked List. Push and pop can be implemented by using other already implemented functions of Linked List like addToStart, …

Queue implementation using Linked List

Queue is a data structure that serves as a collection of elements. It follows the policy of FIFO i.e first in first out. To follow this it has 2 principle functions

Enqueue  function is used to add an element to the rear of the queueDequeue function is used to remove an element from the queue


Linked list is a simple linear data structure formed by collection of data elements called nodes. Each node consists of a data element and link field.The data field consists of element and link field consists of address of next element.

To know more about Queue Data Structure click here
To know more about Linked List click here
To view Simple Linked List implementation click here 
Now inorder to implement Queue using linked list we need to implement enqueue and dequeue operation in Linked List. Enqueue and dequeue can be implemented by using other already implemented functions of Linked List like addToEnd and remove functions.

Here is the Complete code for the implementation
C++ ProgramPython Progr…

Check if a number is Fibonacci number

Fibonacci numbers are numbers such that each number is the result of adding two preceding numbers. A sequence of such numbers is called as fibonacci numbers.
Fibonacci sequence start with 1, 1 as the first 2 terms. Fibonacci sequence is 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , ....
If we want to check if a number is a fibonacci number or not we only need to check if  5*number*number - 4  or 5*number*number + 4 is a perfect square or not.
To see the derivation of the above formula click here.
C++ ProgramJava programPython Program C++ Program Java Program Python Program Sample input and output to check the program
You might also be interested in

Finding Factorial of a number
Finding the next smallest Palindrome
Implement Binary Search Tree
Implement Linked List
Implement Doubly Linked List

Simple Doubly Linked List

Doubly Linked list is a simple linear data structure formed by collection of data elements called nodes. Each node consists of a data element and 2 link fields. The Left Link gives the address of the previous node and right link gives the address of next node.


Each Linked List starts with a head node that points the first node of the List. Unlike arrays Doubly linked lists are not stored in contagious memory locations rather the are stored at any empty place in memory and the address of the next node is stored in the link field. Also you don't need to declare the size of the linked list at the time of initialization you can dynamically keep adding elements to the linked list.




Click for complete information on Doubly Linked List 
The following implementation of the linked list has the following methods implemented :
Method to add element at the start of the ListMethod to add element at the end of the ListMethod to display the Linked List.

Python Program Python Program

This is a Simp…

Lowest Common Ancestor of nodes in BST

This post is about finding the lowest common ancestor of 2 nodes in a binary search tree.

Lowest Common Ancestor of 2 nodes x and y is the node that has both x and y as its desendents. The below image is might help you to understand the above statement.


If you want to know more about Lowest Common Ancestor click here.
To see more programs about BST and other Data Structures click here

C++ ProgramPython Program C++ Program Python Program Sample input and output to check the program


You might also be interested in

Binary Search Tree in Python
Binary Search Tree in C++
Height of Binary Search Tree
Insert ,Search and Display Binary Search Tree
Leaf Nodes of Binary Search Tree
Minimum and Maximum Elements in BST

Minimum and Maximum element in Binary Search Tree

Minimum and Maximum elements of a Binary Search Tree can be found very easily.
If we see the insertion method of a Binary Search Tree we see that if the new element is greater than the current node data then we move to its right subtree ,Similarly if the new Element is less than the current node data we move to its left subtree.

Hence we can easily infer that the smallest element of the Binary Search Tree must be the leftmost node of the tree.
Similarly we can say also infer that largest element should be the rightmost node of the tree.

The following image makes the above statement more clear.




In the above figure we see that 1 is the smallest element of the tree which is also the leftmost node of the tree and 14 is the largest element of the tree is rightmost node of the binary tree.

To know more about binary search tree click here.

To see more operations of binary search tree Visit the following Links

Binary Search tree in C++
Binary Search tree in Python


C++ ProgramPython Program C++ …