## Bubble Sort

Bubble Sort is a sorting algorithm which repeatedly swap the adjacent elements.

example

First Loop:

step 1: 9 0 2 1 8 5 -> 0 9 2 1 8 5

step 2: 0 9 2 1 8 5 -> 0 2 9 1 8 5

step 3: 0 2 9 1 8 5 -> 0 2 1 9 8 5

step 4: 0 2 1 9 8 5 -> 0 2 1 9 5 8

Second Loop:

step 1: 0 2 1 9 5 8 -> 0 2 1 9 5 8

step 2: 0 2 1 9 5 8 -> 0 1 2 9 5 8

step 3: 0 1 2 9 5 8 -> 0 1 2 5 9 8

step 4: 0 1 2 5 9 8 -> 0 1 2 5 8 9

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36``` ```package javacodepoint class BubbleSort { void bubbleSort(int arr[]) { int n = arr.length; for (int i = 0; i < n-1; i++) for (int j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) { // swap temp and arr[i] int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } /* Prints the array */ void printArray(int arr[]) { int n = arr.length; for (int i=0; i

Time complexity - O(n*n) worst average complexity

## Insertion sort

```Algorithm
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
a) Pick element arr[i] and insert it into sorted sequence arr[0?i-1]
```

example

9, 23, 34, 5,1

Let us loop for i = 1 (second element of the array) to 5 (Size of input array)

i = 1. Since 23 is greate than 9 ,so position is remain

9, 23, 34, 5,1

i = 2. 34 is greate than 23 ,so position is remain

p>9, 23, 34, 5,1

i = 3. 5 will move to the beginning and all other elements from 9 to 23 will move one position ahead of their current position.

p>9, 23, 34, 5,1

i = 4. 6 will move to position after 1, and elements from 5 to 34 will move one position ahead of their current position.

1,5,9, 23, 34

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45``` ```package javacodepoint class InsertionSort { /*Function to sort array using insertion sort*/ void sort(int arr[]) { int n = arr.length; for (int i=1; i=0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } /* A utility function to print array of size n*/ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i

Time Complexity: O(n*n)

## Merge Sort

Merge Sort

Merge sort is algorith which first divide the list of unsorted elements in two two parts. left half and right half.

Divide the left part elements in to sub lists until it become single element.

Divide right half of array or list of elements in to sub lists until it becomes one element in list

After dividing all elements in two parts in to single list.

Merge the elements into two by comparing minimum value element will be first. apply same at right half

Merge all the elements in the left part until it become single sorted list

Now we have two sorted parts.

Best case time complexity: O(n log (n))

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104``` ```package javacodepoint class MergeSort { // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] void merge(int arr[], int l, int m, int r) { // Find sizes of two subarrays to be merged int n1 = m - l + 1; int n2 = r - m; /* Create temp arrays */ int L[] = new int [n1]; int R[] = new int [n2]; /*Copy data to temp arrays*/ for (int i=0; i

## Quick Sort

Quick Sort

Create a array with some elements. Choose pivot element as middle element. we can choose first or last also.

After choosing pivot element arrange the elements like all elements which are less than pivot value comes left side and elements greater than equal to pivot come right side of pivot.

And then apply same to both sides. until it becomes one. then all elements in array will be sorted.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78``` ```package javacodepoint class QuickSort { /* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */ int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low-1); // index of smaller element for (int j=low; j Array to be sorted, low --> Starting index, high --> Ending index */ void sort(int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ int pi = partition(arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort(arr, pi+1, high); } } /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i

## Heap Sort

Heap Sort

Build a max heap from the input data.

At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.

Repeat above steps while size of heap is greater than 1.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25``` ```Input data: 2, 11, 5, 8, 1 2(0) / 11(1) 5(2) / 8(3) 1(4) The numbers in bracket represent the indices in the array representation of data. Applying heapify procedure to index 1: 2(0) / 10(1) 5(2) / 8(3) 1(4) Applying heapify procedure to index 0: 11(0) / 8(1) 3(2) / 4(3) 1(4) The heapify procedure calls itself recursively to build heap in top down manner. ```
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74``` ```package javacodepoint public class HeapSort { public void sort(int arr[]) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap void heapify(int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2*i + 1; // left = 2*i + 1 int r = 2*i + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } /* A utility function to print array of size n */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i