Bubblesort is a **sorting** technique which arrange elements in the **increasing** order by moving across the array and swapping the **adjacent** elements that are out of order.The complexity of bubble sort is O(n^{2}).

The steps followed are :

- Move from
**first**to the**last**element of array. **Swap**the element if it is greater than adjacent element.- No need to
**swap**if adjacent element is greater.

**Program**

#include <stdio.h> void bubble(int [], int); int main() { int arr[50], n, a, b; //printf("Enter number of elements\n"); scanf("%d", &n); //printf("Enter elements of array \n"); printf("Unsorted list is :\t"); for (a = 0; a < n; a++) { scanf("%d", &arr[a]); printf("%d\t",arr[a]); } bubble(arr, n); printf("\nSorted list is:\t"); for ( a = 0 ; a < n ; a++ ) { printf("%d\t", arr[a]); } return 0; } void bubble(int array[], int n) { int a, b, temp; for (a = 0 ; a < ( n - 1 ); a++) { for (b = 0 ; b < n - a - 1; b++) { if (array[b] > array[b+1]) { temp = array[b]; array[b] = array[b+1]; array[b+1] = temp; } } } }

**Example** Consider an Â array with elements **3,7,2,10,1,35,15,5,30,4,8.**In order to sort elements,iterations are used.In the first iteration when i=1 sorting is done as given in Â Fig 1 and Fig 2.Refer to Fig 3 and 4 for second iteration i.e i=2,Fig 5 and 6 for i=3.Fig 7 and 8 for i=4,Fig 9 and 10 for i=5.Fig 11 and 12 for i =6 respectively.

**Sorting** is a technique to arrange the** sequence** of elements either in **ascending** or **descending** order. Quicksort is an efficient way to sort elements of array.The average running time of quicksort is O(nlogn).The steps followed in **quicksort** are :

- Choose the
**pivot**element(Say we choose the pivot element in the beginning of array). - Scan from
**right**to**left**and find**first**element in list which is**less**than the**pivot**element.**Stop**scanning as soon the element is f**ound**. **Swap**it with the**pivot**element.- Now scan from
**left**to**right**to find the**first**element which is**greater**than pivot element. **Swap**the element with**pivot**.- Continue the process till the list is
**sorted**or we get a list for which the above process fails to be followed up. **Divide/partition**the array with**pivot**in between into two**sub-arrays**.- Same
**process**is followed on both the**sub-arrays**separately and further partitioning and processing is done if necessary. - Combine all the
**sub-arrays**and their**pivot**elements to get a**sorted**array.

**Program**

#include<stdio.h> void swap (int arr[], int left, int right) { int temp; temp=arr[left]; arr[left]=arr[right]; arr[right]=temp; } void quicksort( int arr[], int low, int high ) { int pivot; if ( high > low ) { pivot = partition( arr, low, high ); quicksort( arr, low, pivot-1 ); quicksort( arr, pivot+1, high ); } } int partition( int arr[], int low, int high ) { int left, right; int item_pivot; int pivot = left = low; item_pivot = arr[low]; right = high; while ( left < right ) { while( arr[left] <= item_pivot ) left++; while( arr[right] > item_pivot) right--; if ( left < right ) swap(arr,left,right); } arr[low] = arr[right]; arr[right] = item_pivot; return right; } void printarray(int arr[], int); int main() { int arr[30], i, n; //printf("\nEnter no. of elements: "); scanf("%d", &n); //printf("\nEnter the elements: \n"); for (i=0; i<n; i++) scanf ("%d", &arr[i]); printf("\nUnsorted array: \n"); printarray(arr,n); quicksort(arr,0,n-1); printf("\nSorted array: \n"); printarray(arr,n); } void printarray(int arr[], int n) { int i; for (i=0; i<n; i++) printf(" %d ", arr[i]); printf("\n"); }

**Example**

Say we have an array with elements **7,44,2,10,1,35,74,88,5,3,15**.Scanning from **right to left** is done to to find element **less** than pivot and from **left to right** is done to find element** greater** than pivot.

*Figure 1*

- The
**pivot**element is the first element i.e**7**. - Scan from right to left and find element less than
**7**.**3**is the first element so it is swapped with the pivot element. - Scan from left to right and find element greater than
**7**.**44**is the first element encountered so it swapped with**7**. - Scan from right to left.
**5**is less than pivot element i.e.**7**so they are swapped. - Scan from left to right.
**10 >7**,so it swapped with**7**. - Scan right-left.
**1 <7**so they are swapped. - Scan from left to right.There is
**no element**in the list before pivot which is greater than pivot itself.Thus list is divided into two sub-lists**S1**and**S2**such that elements in S1 are less than pivot and elements in S2 are greater than pivot.

*Figure 2*

- S1 has
**3,5,2,1**with pivot element**3**and S2 has**35 74 88 10 44 15**with pivot element**35**.(Fig 2) - Scan right to left in
**S1**and find element less than**3**.**1 <3**so they are exchanged. - Scan left-right in
**S1**and find element greater than**3**.**5>3**so they are swapped. - Scan right-left in
**S1**.**2<3**so they are swapped and sub-list S1 gets sorted.

*Figure 3*

- Scan right-left in
**S2**.**15<35**,so they are swapped - Left-right -
**74>35**so they are swapped. - Right-left-
**10<35**so they are swapped. - Left-Right –
**88 >35**so they are swapped.

*Figure 4*

- Partition the sub-list into two further sub-lists
**S3**and**S4**.**S3**has**15,10**and**S4**has**88,44,74**. - Scan right-left in
**S3**.**10<15**so they are swapped and scanning from left-right does not gives any result. - S3 becomes sorted.

* Figure 5*

- Scan right-left in
**S4**.Pivot is**88**.**74<88**so they are swapped. - Scanning left to right is a failed attempt.

*Figure 6*

- Partition S4 into
**S5 and S6**.S5 has**74,44**and S6 is**empty**. - Scan right-left in
**S5**.Pivot is**74**.**44<74**so they are swapped and list becomes sorted.

Combine sub-lists to obtain a sorted list.

**Decrease key** refers to **reducing** the key value of any node.If we want to decrease a key in Binomial heap,we will replace the key with reduced value and will repeatedly **exchange** the reduced key with the parent in order to restore **min-heap** property.The** running time** to perform this operation is **O(log n)**.

**Example**

Say we want to decrease **50 to 4** in binomial heap given in Fig 1.The steps further followed are given in Fig 2,3,4,5 respectively.

4 and 21 are swapped in Fig 3 and 4 and 8 are swapped in Fig 4** **in order to retain min-heap property.

In **Extract-Min **operation node with **minimum key** is **deleted** from the **binomial heap h**.The running time to extract minimum value is **O(log n)**.The steps followed are :

- Find the
**root (say x)**with**minimum key**. **Delete**the root.**Break**the binomial heap into**h**and**h’**.- Perform the
**union**operation to**h**and**h’**.

Given the binomial heap h in **Fig 1**.The first step is to find the **root** with **minimum key**.Node with value **1** is smallest so it is** deleted** and **h** is broken down into** h** and **h’**(Fig 2).

Perform the **union** operation on **h** and **h’.**

After the **union** operation on **h** and **h’** the structure seems like as given in Fig 4

Different cases are performed according to the situation.**x** points to **11**,**next-x** points to **2**,**sibling[next-x]** points to **3** as shown in Fig 5

**Case 1** is applied in Fig 6.**x** now points to **2**,**next-x** points to **3** and **sibling[next-x]** points to **7**.

**Case 3** is applied to Fig 7.Trees with **root 2** and **3** are of **same** order i.e.** 1** and **2** is less than **3** so **3** becomes the child of **2**.**next-x** will now point to** 7** and **sibling[next-x]** will point to **4**.

**Case 3** is applied again in Fig 8.**2** is less than** 7** so **7** becomes the child of **2**.**next-x** will now point to **4**.

**Case 3** is applied in Fig 9 as **2<4** .So 4 becomes the child of 2.x now points to 2 and **next-x** points to **null**.Thus the process stops here.

The union of two heaps is the **merging** root lists by **root degree**.But if we simply merge two heaps then a **problem** can arise.There may be a chance that we get two or more trees of **same root degree**.This **violates** the property of binomial heap.To deal with this problem we have four cases and solution to these cases respectively. Referring to all figures we choose arbitrary names like :

**x**is the second node of merged heaps.**prev-x**points to previous node of x.**next-x**points to next node of x.**sibling[next-x]**points to next node of next-x.**B**_{k }and B_{1 }are**Binomial Heaps**of order**k**and**1**respectively**.**- We apply different cases according to the situation until next-x becomes nil.

**Case 1**

If we merge heaps and have a case like **x** points to binomial heap of **order k** and **next-x** points to binomial heap of **order 1** then ,then we need to shift our pointers towards right.**x** will now point to binomial heap with **order 1.next-k** will point to heap with root **node d** and **prev-x** will point to heap with root **node b** and **order k**.

**Case 2**

If in union operation the heaps with **root b,c,d** are of same **order k** and **x point**s to heap of **order k** and root **node b**,**next-x** points to next heap of** x** with **same order** and root **node c** and **sibling[next-x]** points to next heap of **next-x** again with **same order** and root **node d** then pointers shift by one.** x** now points to heap with root **node c,next-x** points heap with **root d** and **prev-x** points to heap with **root b**.

**Case 3**

After the union operation,if ** b,c** are of** same order** and** key[x]** is less than **key[next[x]]** then **c** becomes the **left child of b** and **x** remain on pointing to **b** but** next-z** now points to points to **d** which was earlier pointed by **sibling[next-x]**.

**Case 4**

The pointer points to same binomial heaps as in case 3 except the difference that** key of x** is greater than **key[next[x]]**.In this case,**b** becomes the **child of c**.**c** is pointed by **x** and** d** is pointed by **next-x**.

**Example**

Consider two heaps **h1** and **h2** as given in Fig 5.The union operation has to be performed on these two heaps**.h1** has binomial trees of order** 0,1** and **2**.h2 has binomial trees of order **0,1 and 3**.At the point of union operation both the heaps are combined together but the resultant structure does not follows **heap property** i.e the resultant structure has binomial trees of **same order**.In Fig 5,two trees with root 2 and 5 are of order 0 and two trees with roots **1** and **3** are of **order 1** violating the property of heaps.In order to make a structure satisfying heap properties we follow case according to the situation.The union of h1 and h2 is shown in Fig 6.

In Fig 7,**2** is less than **5** and both the trees are of same order i.e **0** so case** 3** is followed in which root pointed by **next-x(5)** becomes the child of** x(2)** and pointer **next-x** shifts to right i.e it shifts to** 1** and **sibling[next-x]** also shifts pointer to right i.e to **3**.

In Fig 8,all** three binomial trees** pointed by** x,next-x and sibling[next-x]** are of **same order** i.e **1** so** case 2** is followed in which all three pointers shift to right by one i.e **x** will point to** 1**,**next-x** will point to **3** and **sibling[next-x]** will point to **7**.

In Fig 9,**Case 3** is followed as **root 1** is less than **root 3** and their trees are of **same order**.Tree with **root 3** becomes child of tree with **root 1**.

In Fig 10,**Case 3** is followed again as **root 1** is less than **root 7** and their trees are of **same order** i.e. **2**.Tree with **root 1** becomes the **child** of tree with **root 7**.

In Fig 11,**Case 3** is followed as **1** is less than **4** and their trees are of **same order** i.e.**3**.Tree with **root 1** becomes the child of tree with **root 4**. The next-x becomes nil and so the process of applying cases stop here.We get two binomial trees of different orders.They are of order **1** and **4** respectively.Union of heaps is done satisfying all the properties of binomial heap.

**Binomial Heaps** are similar to **binary heaps** with additional feature of implementing binomial series as sequence of trees.The heap(Fig 1) is represented using **left child right sibling** pointers.It has three links per node **(parent,left,right)** and the roots of tree are connected using single linked list.The degrees of tree decrease from **left to right.**

- Each Binomial tree in the heap obey
**min-heap**property. - There can be only
**0 or 1 binomial trees**for each**order**.

The** root value** of every** binomial tree** is smaller than its children and there will be at most** log n +1** binomial trees of binomial heap with** n nodes.**

Each **binomial tree** corresponds to** one digit** in** binary representation** of a number n.For e.g.the binary representation of** 13**(Fig 2) is **1101**(2^{3}+2^{2}+2^{0}=8+4+1).The binomial heap will have **13 nodes** with binomial trees of order **3,2 and 0** respectively.The orders came from the powers of 2. Either there will be no tree or there will one tree of each order i.e we cannot have any two trees of same order in the binomial heap.Similarly for a number like 15,the binary representation is **1111**(2^{3}+2^{2 }+2^{1 }+2^{0} =8+4+2+1).The binomial heap will have **15 nodes**(Fig 4)with binomial trees of order **3,2,1,0** respectively.

The nodes in the binomial heap can be represented by a structure with parent,key,degree,child and sibling attributes ( Fig 5).

**Example**

Consider the binomial heap as given in Fig 6.Say we want to represent 9(Say) then the structure would be like as given in Fig 7 or if we want represent 31 the structure would be like as given in Fig 8

The various operations that can be performed on Binomial heaps are:

- Union
- Delete Min
- Decrease Key
- Delete
- Insert

Binomial Trees are one of the type of trees that are defined **recursively**.A Binomial tree of order 0 is a single node and a binomial tree of order n has a root node whose children are roots of binomial trees of order n-1,n-2,n-3,n-4,……3,2,1,0.

- There are
**2**^{n }nodes in a binomial tree of order**n**where n is the order and degree of tree(Fig 1). - Deleting roots yield binomial trees
**B**_{n-1},B_{n-2},….0. - B
_{n }has**nodes**at depth d.

When height =0 then **single** node will be present in Binomial tree(Fig 2).

When n=1 then 2^{1 }=**2 **nodes will be present in the tree(Fig 3).

When n=2 then 2^{2 }=** 4 nodes **will be present in the tree.The subtree is **binomially ** attached to the root node(Fig 4).

If order of tree is 3,then 2^{3 }nodes are present in the Binomial tree.**The root is connected to subtrees of order 0**(green color)**,1**(red)** and 2**(black)** **(Fig 5)**.**

If we have a binomial tree of order n,then we can trace the number of nodes at any depth by .For e.g the no of nodes of binomial tree of order 4 at depth 2 will be** 6**.(Fig 6).In fig 7,number of nodes at level 2 is 6 and is shown by red highlighted area.

In order to **delete** elements from **B-Tree** we need to ensure that their properties(Refer : http://letslearncs.com/b-trees/ does not get violated.It should remain a binary search tree and number of pointers must be according to the order and keys should be one less than the order in each and every node.

**Example**

Consider a B-tree of Fig 1.Say we want to delete **2,21,10,3 and 4** step by step from the tree.

**Delete 2**

- 2 is present in
**node b**.Deletion of 2 do not violate any property of B-tree,so we delete**2 directly**from node**b**.(Fig 2)

**Delete 21**

- Deletion of 21 cannot be done directly.It causes node e to
**underflow**so elements are**redistributed**among**c,g and e**(Fig 3).**10**remains in**c**.**12**is stored in**g**and**13**is stored in**e**.

**Delete 10**

- Deletion of 10 again cannot be done directly.It causes
**node c**to**underflow**which further causes parent node**g**to combine with**f and a**and tree shrinks by one level.**3,7 and 9**are stored in**a**,**1 in b**,**4 and 5**in**d,8**in**h****,12 and 13**in**e**(Fig 4).

**Delete 3**

- Deletion of
**3**causes**4**to move in**a**(Fig 5).

**Delete 4**

- Deletion of
**4**needs redistribution of the keys in the**subtrees of 4**; however, nodes**b and d**do not have**enough**keys to redistribute without causing an underflow. Thus, nodes**b and d**are combined together(Fig 6).

The B-tree is a generalization of a** binary search tree ** in which a node can have more than two children .The B-tree is optimized for systems that read and write large blocks of data.It has following properties

- The
**data items**are stored at**leaves**. - Every
**node**has between**M/2**and**M**children where**M**is a positive integer greater than**1**. **M**is the**order**as well as**height**of tree.- The non leaf nodes store up to
**M-1**keys. - The root is either a leaf or has between two and M children.
- All leaves are at the
**same depth**and have between**[L/2]**and**L**children.

The insertion in b-tree is done such that they satisfy all the properties listed above.

**Example**

Consider a B-Tree of** order 4** and we need to insert **5,3,21,9,1,13,2,7,10,12,4,8**.Each node can have **at most 4 pointers** and **3 keys (M-1) **or ** at least 2 pointers** and **1 key**.Since it is a binary search tree the keys of left subtree will be less than the root value and keys of right subtree will be greater than root value.

- Create a node
**a**and insert**5**.(Fig 1) - Insert
**3**to the left of**5 (3<5)**. - Insert
**21**to the right of**5(21 >5).** - In order to insert 9 split node
**a**into**b and c**as 9 cannot be accommodated in node a(**Max keys =3**).The**left pointer**of**9**points to**3**and**5****((3 ,5) <9)**and the**right pointer points**to**21(21 >9**),

- Insert
**1**in node**b (1<3)**(Fig 2). - Insert
**13**in node**c(13>9 and 13 <21).** **2**cannot be directly inserted in node**b**- In order to insert 2 split
**b**into**b and d**. **3**gets**stored**in node**a**.- Store
**1 and 2**in node**b**. - Store
**5**in node**d**.

- In order to insert 2 split

- Insert
**7**in node**d**Â .**(7 >5 and 7<9)**(Fig 3) - Insert
**10**in node**c**(**10 >9 and 10 <13**). - Now
**12**cannot be directly inserted in node**c**.- Split
**c**into**c and e**. **12**is then inserted in node Â**c**.**21**is stored in**e**.

- Split

- Insert
**4**in node**d**(**4 >3 and 4 <5**).(Fig 4) **8**cannot be inserted in**d**directly.- Split
**d**into**f and g** - Split
**f**into**f and h**. **8**is inserted in**h**.

- Split

The **Maxheap** sorts the elements in **increasing** order whereas **Minheap** sorts the element in **decreasing order**.To sort the heap three steps have to be followed

**Heapify**-The process picks the**largest child key**and compare it to the**parent key**. If parent key is larger than key then heapify**quit**s, otherwise it swaps the parent key with the largest child key. So that the parent now becomes larger than its children.**Build Heap**– Use the procedure ‘Heapify’ in a bottom-up fashion to convert an array into a**hea**p. The process starts from last nodes and not the leaves.**Heap Sort**– Sorting is done by removing the**max element**and storing in array .The storage starts from last position and goes till first index of array.

- Build Heap Algorithm will run in
**O(n)**time - There are n-1 calls to Heapify each call requires
**O(log n)**time - Heap sort program combine Build Heap program and Heapify, therefore it has the running time of
**O(n log n)**time - Total time complexity:
**O(n log n)**

**Example**

Given an array in Fig 1 .We need to convert it to Maxheap and sort it.

Array is converted to heap in **Fig 2**

The further steps are illustrated through following figures