Algorithms in C++

Bubble Sort

Bubble Sort is a simple, comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. While easy to understand and implement, Bubble Sort is inefficient for large lists, with a worst-case and average-case time complexity of O(n^2). #include <iostream> #include <array> using namespace std; // This function will carry out the operations in the algorithm of Bubble Sort Method int bubbleSort(int array[], int size){ for (int i = size - 1; i > 0; i--){ for (int j = 0; j < i; j++){ if (array[j] > array[j+1]){ int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } } int main(){ int myArray[] = {6, 4, 3, 6, 7, 8, 1, 4, 5, 3}; int size = sizeof(myArray) / sizeof(myArray[0]); // This is the method for calculating the length of an array bubbleSort(myArray, size); for (auto value: myArray){ cout << value << endl; } } // Operational Complexity for Bubble Sort is O(n^2)

Insertion Sort

Insertion Sort is a simple, comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by repeatedly picking the next element from the unsorted portion and inserting it into the correct position within the sorted portion, effectively shifting elements as necessary to make space. This algorithm is efficient for small data sets or nearly sorted arrays but has a quadratic time complexity of O(n^2) for larger, unordered lists.

Merge Sort

Merge Sort is a stable, comparison-based sorting algorithm that uses the divide-and-conquer strategy. It works by recursively dividing the array into halves until each sub-array contains a single element, then merges the sub-arrays back together in sorted order. This algorithm is efficient with a consistent time complexity of O(nlogn) and is particularly useful for sorting linked lists and large datasets. # include <iostream> using namespace std; void merge(int array[], int leftIndex, int midIndex, int rightIndex){ // Calculating size of the two arrays that are derived from splitting the array int leftArraySize = midIndex - leftIndex + 1; int rightArraySize = rightIndex - midIndex; // Declaring new arrays where these splitted arrays are going to be defined int leftArray[leftArraySize]; int rightArray[rightArraySize]; // Loading new arrays with right and left elements of the array for (int i = 0; i < leftArraySize; i++){ leftArray[i] = array[leftIndex + i]; } for (int j = 0; j < rightArraySize; j++){ rightArray[j] = array[midIndex + 1 + j]; } // initializing variables int index = leftIndex; int i = 0; int j = 0; // Arranging the main array with elements in order of small to large size from the leftArray and rightArray while (i < leftArraySize && j < rightArraySize){ if (leftArray[i] <= rightArray[j]){ array[index] = leftArray[i]; index++; i++; } else{ array[index] = rightArray[j]; index++; j++; } } // If leftArray elements are left over, add them at the end of the main array while (i < leftArraySize){ array[index] = leftArray[i]; index++; i++; } // If rightArray elements are left over, add them at the end of the main array while (j < rightArraySize){ array[index] = rightArray[j]; index++; j++; } } void mergeSort(int array[], int leftIndex, int rightIndex){ if (leftIndex >= rightIndex) return; int midIndex = leftIndex + (rightIndex - leftIndex) / 2; mergeSort(array, leftIndex, midIndex); mergeSort(array, midIndex + 1, rightIndex); merge(array, leftIndex, midIndex, rightIndex); } int main(){ int myArray[] = {3, 1, 4, 2}; int size = sizeof(myArray) / sizeof(myArray[0]); int leftIndex = 0; int rightIndex = size - 1; mergeSort(myArray, leftIndex, rightIndex); for(auto value : myArray){ cout << value << " "; } }

Quick Sort

Quick Sort is a highly efficient, comparison-based sorting algorithm that uses the divide-and-conquer strategy to sort elements. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Quick Sort has an average-case time complexity of O(nlogn) and is generally faster in practice compared to other O(nlogn) algorithms like Merge Sort, though its worst-case complexity is O(n^2).

Selection Sort

Selection Sort is a simple, comparison-based sorting algorithm that sorts an array by repeatedly finding the minimum element from the unsorted portion and swapping it with the first unsorted element. This process continues moving the boundary of the sorted and unsorted subarrays. While easy to understand and implement, Selection Sort is inefficient for large datasets, with a time complexity of O(n^2). # include <iostream> # include <array> using namespace std; // This function will carry out the operations in the algorithm of Selection Sort Method int selectionSort(int array[], int size){ for (int i = 0; i < size; i++){ int minIndex = i; for (int j = i + 1; j < size; j++){ if (array[j] < array[minIndex]){ minIndex = j; } } if (i !

Tree Traversal - Breath First Search

Breadth-First Search is a tree traversal algorithm that explores nodes level by level. Starting from the root, it visits all nodes at the current level before moving on to the nodes at the next level. BFS uses a queue to keep track of the nodes to be explored, ensuring that nodes are processed in the order they are discovered. This method is effective for finding the shortest path in unweighted graphs and has a time complexity of O(V+E), where V is the number of vertices and E is the number of edges.

Tree Traversal - Depth First Search - In Order Search

In-Order Traversal is a type of depth-first search used primarily with binary trees. It visits nodes in a left-root-right sequence: it first recursively visits the left subtree, then processes the current node, and finally recursively visits the right subtree. This traversal method is particularly useful for binary search trees (BSTs) because it visits nodes in ascending order, producing a sorted sequence of values from the tree. The time complexity is O(n), where n is the number of nodes in the tree.

Tree Traversal - Depth First Search - Post Order

Post-Order Traversal is a type of depth-first search that visits nodes in a left-right-root sequence: it first recursively visits the left subtree, then the right subtree, and finally processes the current node. This traversal is useful for operations where a node must be processed only after all its children have been processed, such as deleting nodes in a tree or evaluating expressions in a syntax tree. The time complexity is O(n), where n is the number of nodes in the tree.

Tree Traversal - Depth First Search - Pre Order

Pre-Order Traversal is a type of depth-first search that visits nodes in a root-left-right sequence: it processes the current node first, then recursively visits the left subtree, followed by the right subtree. This traversal is useful for creating a copy of the tree, prefix expression evaluations, and hierarchical structures where the root node is processed before its subtrees. The time complexity is O(n), where n is the number of nodes in the tree.

Tree Traversal - Depth First Search - In Order Search

In-Order Traversal is a type of depth-first search used primarily with binary trees. It visits nodes in a left-root-right sequence: it first recursively visits the left subtree, then processes the current node, and finally recursively visits the right subtree. This traversal method is particularly useful for binary search trees (BSTs) because it visits nodes in ascending order, producing a sorted sequence of values from the tree. The time complexity is O(n), where n is the number of nodes in the tree.

#include <iostream>
#include <queue>

using namespace std;

class Node{
	public:
		int value;
		Node* right;
		Node* left;

		Node(int value){
			this->value = value;
			right = nullptr;
			left = nullptr;
		}
};

class BinarySearchTree{
	public:
		Node* root;

	public:
		BinarySearchTree(){
			root = nullptr;
		}

		bool insert(int value){
			Node* newNode = new Node(value);
			if (root == nullptr){
				root = newNode;
				return true;
			}
			Node* temp = root;
			while (true){
				if (newNode->value == temp->value) return false;
				if (newNode->value < temp->value){
					if (temp->left == nullptr){
						temp->left = newNode;
						return true;
					}
					temp = temp->left;
				}
				else{
					if (temp->right == nullptr){
						temp->right = newNode;
						return true;
					}
					temp = temp->right;
				}
			}
		}

		bool contains(int value){
			Node* temp = root;
			while (temp){
				if (value < temp->value){
					temp = temp->left;
				}
				else if (value > temp->value){
					temp = temp->right;
				}
				else{
					return true;
				}
			}
			return false;
		}

		void DFSInOrder(Node* currentNode){
			if (currentNode->left){
				DFSInOrder(currentNode->left);
			}
			cout << currentNode->value << " ";
			if (currentNode->right){
				DFSInOrder(currentNode->right);
			}
		}	

		// Function overloading 
		void DFSInOrder() {
			DFSInOrder(root);
		}	
};

int main(){
    BinarySearchTree* myBST = new BinarySearchTree;
    
    myBST->insert(12);
    myBST->insert(4);
    myBST->insert(23);
    myBST->insert(45);
    myBST->insert(21);
    myBST->insert(76);
    myBST->insert(44);
    myBST->insert(54);
    
    myBST->DFSInOrder();
}