Binary Search:
Steps:
1) Compare x with the middle element.
2) If x matches with middle element, we return the mid index.
3) Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4) Else (x is smaller) recur for the left half.
A recursive binary search function.
//call as binarySearch(arr, 0, n-1, x)
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x) return mid;
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
A iterative binary search function.
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;
if (arr[m] == x) return m; // Check if x is present at mid
if (arr[m] < x) l = m + 1; // If x greater, ignore left half
else r = m - 1; // If x is smaller, ignore right half
}
return -1; // if we reach here, then element was not present
}
Selection Sort:
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
{
min_idx = i; // Find the minimum element in unsorted array
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]); // Swap the found minimum element with the first element
}
}
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
The same process continues for three passes
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++) //Last i elements are already in place
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
An optimized version of Bubble Sort:
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = true;
}
}
if (swapped == false) // IF no two elements were swapped by inner loop, then break
break;
}
}
Insertion sort:
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
Example:
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 5 (Size of input array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
Merge Sort:
MergeSort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves: middle m = (l+r)/2
2. Call mergeSort for first half: Call mergeSort(arr, l, m)
3. Call mergeSort for second half: Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2]; /* create temp arrays */
for(i = 0; i < n1; i++) /* Copy data to temp arrays L[] and R[] */
L[i] = arr[l + i];
for(j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0; /* Merge the temp arrays back into arr[l..r]*/
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) /* Copy the remaining elements of L[], if there are any */
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2) /* Copy the remaining elements of R[], if there are any */
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) /* l is for left index and r is right index of the sub-array
{
if (l < r)
{
int m = l+(r-l)/2; //Same as (l+r)/2, but avoids overflow for large l and h
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
Quick sort:
Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
1) Always pick first element as pivot.
2) Always pick last element as pivot (implemented below)
3) Pick a random element as pivot.
4) Pick median as pivot.
Partition Algorithm
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 l, int h)
{
int x = arr[h]; // pivot
int i = (l - 1); // Index of smaller element
for (int j = l; j <= h- 1; j++)
{
if (arr[j] <= x) // If current element is smaller than or equal to pivot
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]); // Swap current element with index
}
}
swap(&arr[i + 1], &arr[h]);
return (i + 1);
}
/* arr[] --> Array to be sorted, l --> Starting index, h --> Ending index */
void quickSort(int arr[], int l, int h)
{
if (l < h)
{
int p = partition(arr, l, h); /* Partitioning index */
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, h);
}
}
Bucket Sort:
Bucket sort is mainly useful when input is uniformly distributed over a range.
bucketSort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.
Function to sort arr[] of size n using bucket sort
void bucketSort(float arr[], int n)
{
vector<float> b[n]; // 1) Create n empty buckets
for (int i=0; i<n; i++) // 2) Put array elements in different buckets
{
int bi = n*arr[i]; // Index in bucket
b[bi].push_back(arr[i]);
}
for (int i=0; i<n; i++) // 3) Sort individual buckets
sort(b[i].begin(), b[i].end());
int index = 0; // 4) Concatenate all buckets into arr[]
for (int i = 0; i < n; i++)
for (int j = 0; j < b[i].size(); j++)
arr[index++] = b[i][j];
}
Shell Sort:
In shellSort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted. It is a variation of Insertion sort
int shellSort(int arr[], int n)
{
for (int gap = n/2; gap > 0; gap /= 2) // Start with a big gap, then reduce the gap
{
// Do a gapped insertion sort for this gap size.
for (int i = gap; i < n; i += 1)
{
/* add a[i] to the elements that have been gap sorted save a[i] in temp and make a hole at position i*/
int temp = arr[i];
// shift earlier gap-sorted elements up until the correct location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp; // put temp (the original a[i]) in its correct location
}
}
return 0;
}
Heap Sort:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap
Heap Sort Algorithm for sorting in increasing order:
1. Build a max heap from the input data.
2. 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.
3. Repeat above steps until size of heap is greater than 1.
Heapify procedure can be applied to a node only if its children nodes are heapified. So the heapification must be performed in the bottom up order.
C implementation of Heap Sort
#include <stdio.h>
#include <stdlib.h>
struct MaxHeap
{
int size;
int* array;
};
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
void maxHeapify(struct MaxHeap* maxHeap, int idx)
{
int largest = idx; // Initialize largest as root
int left = (idx << 1) + 1; // left = 2*idx + 1
int right = (idx + 1) << 1; // right = 2*idx + 2
// See if left child of root exists and is greater than root
if (left < maxHeap->size && maxHeap->array[left] > maxHeap->array[largest])
largest = left;
// See if right child of root exists and is greater than the largest so far
if (right < maxHeap->size && maxHeap->array[right] > maxHeap->array[largest])
largest = right;
if (largest != idx) // Change root, if needed
{
swap(&maxHeap->array[largest], &maxHeap->array[idx]);
maxHeapify(maxHeap, largest);
}
}
struct MaxHeap* createAndBuildHeap(int *array, int size)
{
int i;
struct MaxHeap* maxHeap = (struct MaxHeap*) malloc(sizeof(struct MaxHeap));
maxHeap->size = size; // initialize size of heap
maxHeap->array = array; // Assign address of first element of array
/*Start from bottommost and rightmost internal mode and heapify all internal modes in bottom up way*/
for (i = (maxHeap->size - 2) / 2; i >= 0; --i)
maxHeapify(maxHeap, i);
return maxHeap;
}
void heapSort(int* array, int size)
{
struct MaxHeap* maxHeap = createAndBuildHeap(array, size);
/* Repeat following steps while heap size is greater than 1. The last element in max heap will be the minimum element*/
while (maxHeap->size > 1)
{
/* The largest item in Heap is stored at the root. Replace it with the last item of the heap followed by reducing the size of heap by 1.*/
swap(&maxHeap->array[0], &maxHeap->array[maxHeap->size - 1]);
--maxHeap->size; // Reduce heap size
maxHeapify(maxHeap, 0); // Finally, heapify the root of tree.
}
}
void printArray(int* arr, int size)
{
int i;
for (i = 0; i < size; ++i)
printf("%d ", arr[i]);
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, size);
heapSort(arr, size);
printf("\nSorted array is \n");
printArray(arr, size);
return 0;
}
Steps:
1) Compare x with the middle element.
2) If x matches with middle element, we return the mid index.
3) Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
4) Else (x is smaller) recur for the left half.
A recursive binary search function.
//call as binarySearch(arr, 0, n-1, x)
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x) return mid;
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
A iterative binary search function.
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;
if (arr[m] == x) return m; // Check if x is present at mid
if (arr[m] < x) l = m + 1; // If x greater, ignore left half
else r = m - 1; // If x is smaller, ignore right half
}
return -1; // if we reach here, then element was not present
}
Selection Sort:
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
{
min_idx = i; // Find the minimum element in unsorted array
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]); // Swap the found minimum element with the first element
}
}
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
The same process continues for three passes
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++) //Last i elements are already in place
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
An optimized version of Bubble Sort:
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = true;
}
}
if (swapped == false) // IF no two elements were swapped by inner loop, then break
break;
}
}
Insertion sort:
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.
Example:
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 5 (Size of input array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
Merge Sort:
MergeSort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves: middle m = (l+r)/2
2. Call mergeSort for first half: Call mergeSort(arr, l, m)
3. Call mergeSort for second half: Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2]; /* create temp arrays */
for(i = 0; i < n1; i++) /* Copy data to temp arrays L[] and R[] */
L[i] = arr[l + i];
for(j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0; /* Merge the temp arrays back into arr[l..r]*/
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) /* Copy the remaining elements of L[], if there are any */
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2) /* Copy the remaining elements of R[], if there are any */
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) /* l is for left index and r is right index of the sub-array
{
if (l < r)
{
int m = l+(r-l)/2; //Same as (l+r)/2, but avoids overflow for large l and h
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
Quick sort:
Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
1) Always pick first element as pivot.
2) Always pick last element as pivot (implemented below)
3) Pick a random element as pivot.
4) Pick median as pivot.
Partition Algorithm
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 l, int h)
{
int x = arr[h]; // pivot
int i = (l - 1); // Index of smaller element
for (int j = l; j <= h- 1; j++)
{
if (arr[j] <= x) // If current element is smaller than or equal to pivot
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]); // Swap current element with index
}
}
swap(&arr[i + 1], &arr[h]);
return (i + 1);
}
/* arr[] --> Array to be sorted, l --> Starting index, h --> Ending index */
void quickSort(int arr[], int l, int h)
{
if (l < h)
{
int p = partition(arr, l, h); /* Partitioning index */
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, h);
}
}
Bucket Sort:
Bucket sort is mainly useful when input is uniformly distributed over a range.
bucketSort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.
Function to sort arr[] of size n using bucket sort
void bucketSort(float arr[], int n)
{
vector<float> b[n]; // 1) Create n empty buckets
for (int i=0; i<n; i++) // 2) Put array elements in different buckets
{
int bi = n*arr[i]; // Index in bucket
b[bi].push_back(arr[i]);
}
for (int i=0; i<n; i++) // 3) Sort individual buckets
sort(b[i].begin(), b[i].end());
int index = 0; // 4) Concatenate all buckets into arr[]
for (int i = 0; i < n; i++)
for (int j = 0; j < b[i].size(); j++)
arr[index++] = b[i][j];
}
Shell Sort:
In shellSort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted. It is a variation of Insertion sort
int shellSort(int arr[], int n)
{
for (int gap = n/2; gap > 0; gap /= 2) // Start with a big gap, then reduce the gap
{
// Do a gapped insertion sort for this gap size.
for (int i = gap; i < n; i += 1)
{
/* add a[i] to the elements that have been gap sorted save a[i] in temp and make a hole at position i*/
int temp = arr[i];
// shift earlier gap-sorted elements up until the correct location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp; // put temp (the original a[i]) in its correct location
}
}
return 0;
}
Heap Sort:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap
Heap Sort Algorithm for sorting in increasing order:
1. Build a max heap from the input data.
2. 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.
3. Repeat above steps until size of heap is greater than 1.
Heapify procedure can be applied to a node only if its children nodes are heapified. So the heapification must be performed in the bottom up order.
C implementation of Heap Sort
#include <stdio.h>
#include <stdlib.h>
struct MaxHeap
{
int size;
int* array;
};
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
void maxHeapify(struct MaxHeap* maxHeap, int idx)
{
int largest = idx; // Initialize largest as root
int left = (idx << 1) + 1; // left = 2*idx + 1
int right = (idx + 1) << 1; // right = 2*idx + 2
// See if left child of root exists and is greater than root
if (left < maxHeap->size && maxHeap->array[left] > maxHeap->array[largest])
largest = left;
// See if right child of root exists and is greater than the largest so far
if (right < maxHeap->size && maxHeap->array[right] > maxHeap->array[largest])
largest = right;
if (largest != idx) // Change root, if needed
{
swap(&maxHeap->array[largest], &maxHeap->array[idx]);
maxHeapify(maxHeap, largest);
}
}
struct MaxHeap* createAndBuildHeap(int *array, int size)
{
int i;
struct MaxHeap* maxHeap = (struct MaxHeap*) malloc(sizeof(struct MaxHeap));
maxHeap->size = size; // initialize size of heap
maxHeap->array = array; // Assign address of first element of array
/*Start from bottommost and rightmost internal mode and heapify all internal modes in bottom up way*/
for (i = (maxHeap->size - 2) / 2; i >= 0; --i)
maxHeapify(maxHeap, i);
return maxHeap;
}
void heapSort(int* array, int size)
{
struct MaxHeap* maxHeap = createAndBuildHeap(array, size);
/* Repeat following steps while heap size is greater than 1. The last element in max heap will be the minimum element*/
while (maxHeap->size > 1)
{
/* The largest item in Heap is stored at the root. Replace it with the last item of the heap followed by reducing the size of heap by 1.*/
swap(&maxHeap->array[0], &maxHeap->array[maxHeap->size - 1]);
--maxHeap->size; // Reduce heap size
maxHeapify(maxHeap, 0); // Finally, heapify the root of tree.
}
}
void printArray(int* arr, int size)
{
int i;
for (i = 0; i < size; ++i)
printf("%d ", arr[i]);
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, size);
heapSort(arr, size);
printf("\nSorted array is \n");
printArray(arr, size);
return 0;
}
No comments:
Post a Comment