Sorting

Sorting

Bubble Sort

The bubble sort finds the greatest element in the array and places it to the extreme right hand side of the array. It then works on rest of the array and will place the greatest element in rest of the array on the right hand side and so on.

It gets the name bubble sort as the highest element bubbles it's way to the top.

Selection Sort

Similar to bubble sort the minimum element is placed on the left hand side. It does not rely on the swap operation.

Insertion Sort

This is similar to the procedure used when we sort cards. We pick a card in the second position and find a place for it on the left hand side. Now we have 2 cards that are sorted. We then start with the 3rd card and place it in the right position on the left hand side.

File: "sort.cpp"

#include <iostream>using namespace std; void printArray( int arr1[], int size ) { for( int i1=0 ; i1< size ; i1++) { cout << arr1[i1] << " , " ; } cout << endl ; } void bubbleSort1( int arr1[] , int size ) { bool exchangeHappened = true ; while ( exchangeHappened ) { exchangeHappened = false ; for ( int i1=0 ; i1< size-1 ; i1++ ) { if ( arr1[i1] > arr1[i1+1] ) { //Swap int temp = arr1[i1] ; arr1[i1] = arr1[i1+1] ; arr1[i1+1] = temp ; exchangeHappened = true ; } } //for } //while } void bubbleSort2( int arr1[] , int size ) { for ( int limit=size-1 ; limit > 0 ; limit-- ) { bool exchangeHappened = false ; for ( int i1=0 ; i1< limit ; i1++ ) { if ( arr1[i1] > arr1[i1+1] ) { //Swap int temp = arr1[i1] ; arr1[i1] = arr1[i1+1] ; arr1[i1+1] = temp ; exchangeHappened = true ; } } //for if ( exchangeHappened == false ) return ; } //while } void selectionSort( int arr1[] , int size ) { for ( int i1=0 ; i1 < size -1 ; i1++ ) { int min = arr1[i1] ; int minIndex = i1 ; for ( int j1=i1+1 ; j1 < size; j1++ ) { if (arr1[j1] < min ) { min = arr1[j1] ; minIndex = j1 ; } } //for arr1[ minIndex ] = arr1[i1] ; arr1[ i1 ] = min ; } //while } void insertionSort1( int arr1[] , int size ) { for ( int i1=1 ; i1 < size ; i1++ ) { for ( int j1=i1 ; j1 > 0 ; j1-- ) { if ( arr1[j1] < arr1[j1-1] ) { //Swap int temp = arr1[j1] ; arr1[j1] = arr1[ j1-1 ] ; arr1[j1-1] = temp ; } else break ; } //for } //while } void insertionSort2( int arr1[] , int size ) { for ( int i1=1 ; i1 < size ; i1++ ) { int currentElement = arr1[i1] ; int j1 ; for ( j1 = i1 ; j1 > 0 ; j1-- ) { if ( currentElement < arr1[j1-1] ) { //Shift arr1[j1] = arr1[ j1-1 ] ; } else break ; } //for arr1[j1] = currentElement ; } //while }int main(){ int arr1[] = { 4, 1 , 3 , 2 } ; int arr2[] = { 7, 4 , 3 , 2, 1 } ; int arr3[] = { 1, 2 , 3 , 4 } ; bubbleSort2( arr1 , 4 ) ; printArray( arr1 , 4 ) ; selectionSort( arr2 , 5 ) ; printArray( arr2 , 5 ) ; insertionSort1( arr3 , 4 ) ; printArray( arr3 , 4 ) ; return 0;}

Recursive Sorting

Merge Sort

// C++ program for Merge Sort#include <iostream>using namespace std;// Merges two subarrays of arr[].// First subarray is arr[l..m]// Second subarray is arr[m+1..r]void merge(int arr[], int left, int middle, int right){ int n1 = middle - left + 1; int n2 = right - middle ; // Create temp arrays int leftArr[n1], rightArr[n2]; cout << "Merge" << endl ; // Copy data to temp arrays L[] and R[] for (int i1 = 0; i1 < n1; i1++) leftArr[i1] = arr[ left + i1 ]; for (int j1 = 0; j1 < n2; j1++) rightArr[j1] = arr[ middle + 1 + j1]; // Merge the temp arrays back into arr[l..r] // Initial index of first subarray int i1 = 0; // Initial index of second subarray int j1 = 0; // Initial index of merged subarray int k1 = left; while (i1 < n1 && j1 < n2) { if (leftArr[i1] <= rightArr[j1]) { arr[k1] = leftArr[i1]; i1++; } else { arr[k1] = rightArr[j1]; j1++; } k1++; } // Copy the remaining elements of // L[], if there are any while (i1 < n1) { arr[k1] = leftArr[i1]; i1++; k1++; } // Copy the remaining elements of // R[], if there are any while (j1 < n2) { arr[k1] = rightArr[j1]; j1++; k1++; }}// l is for left index and r is// right index of the sub-array// of arr to be sorted */void mergeSort(int arr[],int left, int right ){ cout << "mergeSort" << " left:" << left << " right:"<< right << endl ; if( left >= right ) { return;//returns recursively } int middle = ( left + right - 1 ) / 2 ; mergeSort( arr, left, middle ) ; mergeSort(arr,middle+1, right); merge(arr, left , middle , right );}// UTILITY FUNCTIONS// Function to print an arrayvoid printArray(int arr1[], int size){ for (int i1 = 0; i1 < size; i1++) cout << arr1[i1] << " ";}// Driver codeint main(){ int arr[] = { 12, 11, 13, 5, 6, 7 }; int arr_size = sizeof(arr) / sizeof(arr[0]); cout << "Given array is \n" ; printArray(arr, arr_size) ; cout << "About to merge sort." << endl ; mergeSort(arr, 0, arr_size - 1); cout << "\nSorted array is \n"; printArray(arr, arr_size); return 0;}

QuickSort

File: "quick1.cpp"

/* C implementation QuickSort */#include<stdio.h>// A utility function to swap two elementsvoid swap(int* a, int* b){ int t = *a; *a = *b; *b = t;}/* This function takes last element as pivot, placesthe 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 rightof pivot */int partition (int arr[], int low, int high){ int pivot = arr[high]; // pivot int i1 = (low - 1); // Index of smaller element for (int j1 = low; j1 <= high- 1; j1++) { // If current element is smaller than or // equal to pivot if (arr[j1] <= pivot) { i1++; // increment index of smaller element swap(&arr[i1], &arr[j1]); } } swap(&arr[i1 + 1], &arr[high]); return (i1 + 1);}/* The main function that implements QuickSortarr[] --> Array to be sorted,low --> Starting index,high --> Ending index */void quickSort(int arr[], int low, int high){ if (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }}/* Function to print an array */void printArray(int arr[], int size){ int i; for (i=0; i < size; i++) printf("%d ", arr[i]); printf("\n");}// Driver program to test above functionsint main(){ int arr[] = {10, 7, 8, 9} ; //, 1, 5}; int n = sizeof(arr)/sizeof(arr[0]); quickSort(arr, 0, n-1); printf("Sorted array: \n"); printArray(arr, n); return 0;}

HeapSort

A tree is an abstract data structure that can represent a hierarchy with a root node and a node having children that in turn can have other children.

A binary tree is a tree that can have at most 2 nodes. The tree above is not a binary tree as the node 7 has 3 children 2, 10 and 6 .

The above is a binary tree. A complete binary tree is a tree that has all the levels filled except possibly the last level and the last level will have the nodes to the left as much as possible.

The above is a complete binary tree. If we are to add a new node ; say "M" then it will be added as the right child of F .

A binary heap tree is a complete binary tree with the property that a node will either have a value greater than the child nodes which are also heap trees ( max heap ) or a value less than the child nodes that are also heap trees ( min heap ) .

Every node in the above is bigger than it's child nodes that are themselves heaps. We can easily represent a heap using an array. The node at index i1 will have children at 2*i1+1 and 2*i1+2 .

File: "heap1.cpp"

#include <iostream>using namespace std;// To heapify a subtree rooted with node i which is// an index in arr[]. n is size of heapvoid heapify(int arr[], int n, int i1 ){ int largest = i1 ; // Initialize largest as root int l = 2 * i1 + 1; // left = 2*i + 1 int r = 2 * i1 + 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 != i1) { swap(arr[i1], arr[largest]); // Recursively heapify the affected sub-tree heapify(arr, n, largest); }}// main function to do heap sortvoid heapSort(int arr[], int n){ // Build heap (rearrange array) for (int i1 = n / 2 - 1; i1 >= 0; i1--) heapify(arr, n, i1 ); // One by one extract an element from heap for (int i1 = n - 1; i1 > 0; i1--) { // Move current root to end swap(arr[0], arr[i1]); // call max heapify on the reduced heap heapify(arr, i1, 0); }}/* A utility function to print array of size n */void printArray(int arr[], int n){ for (int i1 = 0; i1 < n; ++i1) cout << arr[i1] << " "; cout << "\n";}// Driver codeint main(){ int arr[] = { 12, 11, 13, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); heapSort(arr, n); cout << "Sorted array is \n"; printArray(arr, n);}