HeapSort

Heap sort is very easy to implement and its time complexity is O(n log(n)).

Sorting Max-heap:

1. Let array S is of size n. where  n is no of element to sort
2. top=n
3. Pop root from heap and put it at S[top]
4. top=top-1
5. heapify(A,1) //Heapify remaining heap again
6. Repeate step 3 to 5 untill heap is empty

Heap Basics Extension - Priority Queue

Priority Queue is very commonly used in operating system to schedule task, priority Queue can very easily and very effectively can implement in Heap.

Insert A new Key in Heap :

Start from end of heap and find appropriate position then insert.

---

Heap-Insert(A,key)

1. Heap-Size[A] <- Heap-Size[A]+1
2. i=Heap-Size[A]
3. while(i>1 and A[parant(i)]<key)
• A[i]<-A[Parant(i)]
• i=Parent(i)
4. A[i]=Key

---

Note: If We remove root node then to hepify again we just have to call heapify(A,1)

Heap Basics

Heap is also called Left Complete binary tree. i.e Binary tree with some of rightmost node removed.
It is very efficient for priority Queue implementation.

MaxHeap

Heap Type:

1. Minimum Key Heap: Root node is always minimum.
2. Maximum key Heap:  Root node is always maximum.

Factorial of a Large Number

Idea : - we are going to find factorial of a large number number.

Factorial of large number

• store num in array such that each element of array is a single digit.
• Decrease num by 1 and multiply num with each element of array and then for each element we store them as the rightmost digit remains at it's location while the remaining part is added to the next element and the last element is again stored as single digit and the remaining is stored on next till remaining part becomes 0.

Queue Implementation In One way Link list

Queue:

A queue is a linear list of element in which

è Deletion can take place at one end that is Front .

è Insertion take place at one end that is Rear ..

That's why Also known as FILO :-first in last out

Queue Implementation In Array in C

Queue:

A queue is a linear list of element in which

è Deletion can take place at one end that is Front .

è Insertion take place at one end that is Rear ..

That's why Also known as FILO :-first in last out

AMICABLE PAIRS

Two numbers form Amicable Pairs  if sum of proper divisors of  1st is equal to the 2nd and vice-versa.It is assumed that these two numbers should be distinct,

Example : Let two number 220 And 284 ,
      Sum of proper Divisor of 220 := 1+2+4+5+10+11+20+22+44+55+110 = 284
      Sum of Proper Divisor of 284 :=1+2+$+71+142=210 .
 That's Why 220 & 284 form amicable number pair .

Note : ( 220 , 284 ) smallest Amicable Number Pair . 

Related Post :  test your programming skill P-2

Related Post : How to host your website for FREE (google drive )

Related Post : How to get ip address of user in PHP

C Code to find Amicable Number in GIven Range : 

Multidimensional Array

•One-Dimensional Array

•Two-Dimensional Array

•Three-Dimensional Array

•Some programming Language allows as many as 7 dimension 

\

---

Two-Dimensional Array 

•A Two-Dimensional m x n array A is a collection of m . n data elements such that each element is specified by a pair of integer (such as J, K) called subscript with property that

  1 ≤ J ≤ m   and 1 ≤ K ≤ n

linear structure : Array

Linear  Arrays

•A linear array is a list of a finite number of n homogeneous data elements ( that is data elements of the same type) such that

–The elements are of the arrays are referenced respectively by an index set consisting of n consecutive numbers

–The elements of the arrays are stored respectively in successive memory locations .

•The number n of elements is called the length or size of the array. 

•The index set consists of the integer 1, 2, … n

•Length or the number of data elements of the array can be obtained from the index set by

  Length = UB – LB + 1 where UB is the largest index called the upper bound and LB is the smallest index called the lower bound of the arrays .

Data Structure vs Storage Structure

•Data Structure : The logical or mathematical model of a particular organization of data

•Storage Structure : Representation of a particular data structure in the memory of a computer

•There are many possible storage structure to a particular data structure

•Ex: there are a number of storage structure for a data structure such as array

–It is possible for two DS to represented by the same storage structure 

Search & Delete operation on Binary search tree {BST}

•Algorithm

  Perform search for value X

 If X is a leaf, delete X

    Else   // must delete internal node

     a) Replace with largest value Y on left subtree

                     OR smallest value Z on right subtree

     b) Delete replacement value (Y or Z) from subtree

Observation

–O( log(n) ) operation for balanced tree

–Deletions may unbalance tree

Example Deletion (Leaf)

•Delete ( 25 )

Binary Search Tree (BST)

Suppose T is a binary tree

Then T is called binary search tree if each node N of T  has the following property

The value at N is greater than every value in the left sub-tree of N and is less than every value in the right sub-tree of N 

Sparse Matrix in C

If a matrix contains lots of ZEROS , then to save time & space,we use a special type of matrix ,known as SPARSE MATRIX.....

It stores only the NON-ZERO Elements only....
It can be created by two ways
1)Using array
2)Using Linklist

Simple e.g-

---

Let's write a c programe to get the sparse matrix of a given matix [In array]

Quick sort Recursive Approch

There are many way to sort a list using quick sort concept .i.e recursive way & iterative way.

quick sort 

Recursive Approach

1. choose a no in the list a pivote
2. now sort list such that no less then pivote no. come on left of it & other on right
3. In above steps list break in two part . let left list as brand new list and repeat all steps(1,2,3).
4. do similar operation on right list as on left.

Now how to do Steps 2. there are many ways I did mention few of them..

Selection Sort (concept & algorithm)

Suppose an array A with N elements is in memory. Selection sort works as follows

First find the smallest element in the list and put it in the first position. Then, find the second smallest element in the list and put it in the second position  and so on.

Pass 1: Find the location LOC  of the smallest element in the list A[1], A[2], … A[N]. Then interchange A[LOC] and A[1]. Then: A[1] is sorted

Pass 2: Find the location LOC  of the smallest element in the sublist A[2], A[3], … A[N]. Then interchange A[LOC] and A[2]. Then: A[1],A[2]  is sorted since A[1] <= A[2].

Pass 3: Find the location LOC  of the smallest element in the sublist A[3], A[4], … A[N]. Then interchange A[LOC] and A[3]. Then: A[1], A[2],A[3]  is sorted, since A[2] <= A[3]. 

Insertion Sort (concept & algorithm)

insertion like cards

An array A with N elements A[1], A[2] … A[N] is in memory

Insertion Sort scan A from A[1] to A[N] inserting each elements A[k] into its proper position in the previously sorted subarray A[1], A[2], …. A[K-1]

Pass 1: A[1] by itself is trivially sorted

Pass 2: A[2] is inserted either before or after A[1] so that A[1], A[2] is sorted

Pass 3: A[3] is inserted in its proper place in A[1], A[2], that is before A[1], between A[1] and A[2] or after A[2] so that A[1], A[2], A[3] is sorted

Pass 4: A[4] is inserted in its proper place in A[1], A[2], A[3] so that A[1], A[2], A[3], A[4]  is sorted. 

Quick Sort (concept & algorithm )

Quick sort is an algorithm of the divide-and-conquer type

The problem of sorting a set  is reduced to the problem of sorting two smaller sets.

---

Quick Sort Approach :

Bubble Sort ( concept & algorithm )

The oldest and simplest sort in use.

Unfortunately, also the slowest.

Works by comparing each item in the list with the item next to it, and swapping them if required.

---

The algorithm repeats this process until it makes a pass all the way through the list without swapping any items.

This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.

Sorting

Sorting refers to the operation of arranging data in some order such as increasing or decreasing with numerical data or alphabetically with character data

Complexity of Sorting Algorithm

The complexity of a sorting algorithm measures the running time as a function of the number on n of items to be sorted .

Each sorting algorithm S will be made up of the following operations, where A1, A2 , ……, An  contain the items to be sorted and B is an auxiliary location:

(a) Comparisons : which test whether Ai < Aj  or test Ai < B

(b) Interchange, which switch the content of Ai and  Aj  or of Ai  and B

(c) Assignments, which set B := Ai  and then set Aj  := B or Set Aj   := Ai

Search & Deletion in Binary search Tree ( BST )

In previous discussion we discus about Binary search tree Now we have to do some basic operation on binary search tree.

Searching a element : it is not a tough job in BST .follow simple algorithm

>> compare root node data with require data if equal search complete otherwise if less that root node move to left else move to right child.

follow this steps for all nodes until NULL encounter it is condition for unsuccessful search.