{"id":153,"date":"2023-03-02T00:48:20","date_gmt":"2023-03-02T00:48:20","guid":{"rendered":"https:\/\/alitousen.com\/?page_id=153"},"modified":"2025-03-14T14:37:06","modified_gmt":"2025-03-14T14:37:06","slug":"algorithms","status":"publish","type":"page","link":"https:\/\/alitousen.com\/?page_id=153","title":{"rendered":"Algorithms"},"content":{"rendered":"\n

In computer science, an algorithm is a set of steps or instructions that are designed to solve a specific problem or accomplish a particular task. It is essentially a well-defined procedure that can be followed to achieve a specific goal.<\/p>\n\n\n\n

Algorithms can be expressed in various forms, such as natural language, flowcharts, pseudocode, or programming languages. They can be used to perform a wide range of tasks, including sorting data, searching for information, calculating complex mathematical equations, and more.<\/p>\n\n\n\n

The efficiency of an algorithm is measured by its time complexity and space complexity. Time complexity refers to how long an algorithm takes to complete its task, while space complexity refers to how much memory an algorithm requires to execute.<\/p>\n\n\n\n

Algorithms are a crucial part of computer science and are used extensively in programming, software development, and other related fields. They help automate complex tasks and provide solutions to real-world problems, making them an essential tool for developers and computer scientists.<\/p>\n\n\n\n

Linear Search
Binary Search
Bubble Sort
Insertion Sort
Selection Sort
Quick Sort
Merge Sort
Heap Sort
Counting Sort
Radix Sort
Bucket Sort
Depth-First Search (DFS)
Breadth-First Search (BFS)
Dijkstra’s Algorithm
Bellman-Ford Algorithm
Floyd-Warshall Algorithm
Prim’s Algorithm
Kruskal’s Algorithm
Topological Sort
Dynamic Programming
Knapsack Problem
Traveling Salesman Problem (TSP)
Convex Hull
Maximum Flow
Minimum Spanning Tree<\/p>\n\n\n\n

Linear Sort<\/h2>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\nusing<\/span> namespace std;<\/span><\/span>\n<\/span>\nint <\/span>linearSearch<\/span>(int arr[], int n, int key) {<\/span><\/span>\n    <\/span>for<\/span> (int i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n        <\/span>if<\/span> (arr[i] <\/span>==<\/span> key) {<\/span><\/span>\n            <\/span>return<\/span> i;<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n    <\/span>return<\/span> <\/span>-<\/span>1<\/span>; <\/span>\/\/ Key not found<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint <\/span>main<\/span>() {<\/span><\/span>\n    int arr[] <\/span>=<\/span> {<\/span>10<\/span>, <\/span>20<\/span>, <\/span>30<\/span>, <\/span>40<\/span>, <\/span>50<\/span>};<\/span><\/span>\n    int n <\/span>=<\/span> <\/span>sizeof<\/span>(arr) <\/span>\/<\/span> <\/span>sizeof<\/span>(arr[<\/span>0<\/span>]);<\/span><\/span>\n    int key <\/span>=<\/span> <\/span>30<\/span>;<\/span><\/span>\n<\/span>\n    int index <\/span>=<\/span> <\/span>linearSearch<\/span>(arr, n, key);<\/span><\/span>\n<\/span>\n    <\/span>if<\/span> (index <\/span>!=<\/span> <\/span>-<\/span>1<\/span>) {<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>Element found at index <\/span>"<\/span> <\/span><<<\/span> index <\/span><<<\/span> endl;<\/span><\/span>\n    } <\/span>else<\/span> {<\/span><\/span>\n        cout <\/span><<<\/span> <\/span>"<\/span>Element not found<\/span>"<\/span> <\/span><<<\/span> endl;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Binary Search<\/h2>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
#include<\/span><<\/span>iostream<\/span>><\/span><\/span>\nusing<\/span> namespace std;<\/span><\/span>\n<\/span>\nint <\/span>binarySearch<\/span>(int arr[], int left, int right, int target) {<\/span><\/span>\n   <\/span>while<\/span> (left <\/span><=<\/span> right) {<\/span><\/span>\n      int mid <\/span>=<\/span> left <\/span>+<\/span> (right <\/span>-<\/span> left) <\/span>\/<\/span> <\/span>2<\/span>;<\/span><\/span>\n      <\/span><\/span>\n      <\/span>\/\/ If target is at the middle position, return mid<\/span><\/span>\n      <\/span>if<\/span> (arr[mid] <\/span>==<\/span> target)<\/span><\/span>\n         <\/span>return<\/span> mid;<\/span><\/span>\n      <\/span><\/span>\n      <\/span>\/\/ If target is greater, ignore left half<\/span><\/span>\n      <\/span>if<\/span> (arr[mid] <\/span><<\/span> target)<\/span><\/span>\n         left <\/span>=<\/span> mid <\/span>+<\/span> <\/span>1<\/span>;<\/span><\/span>\n      <\/span><\/span>\n      <\/span>\/\/ If target is smaller, ignore right half<\/span><\/span>\n      <\/span>else<\/span><\/span>\n         right <\/span>=<\/span> mid <\/span>-<\/span> <\/span>1<\/span>;<\/span><\/span>\n   }<\/span><\/span>\n   <\/span><\/span>\n   <\/span>\/\/ If the target is not found, return -1<\/span><\/span>\n   <\/span>return<\/span> <\/span>-<\/span>1<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint <\/span>main<\/span>() {<\/span><\/span>\n   int arr[] <\/span>=<\/span> {<\/span>2<\/span>, <\/span>5<\/span>, <\/span>8<\/span>, <\/span>12<\/span>, <\/span>16<\/span>, <\/span>23<\/span>, <\/span>38<\/span>, <\/span>56<\/span>, <\/span>72<\/span>, <\/span>91<\/span>};<\/span><\/span>\n   int target <\/span>=<\/span> <\/span>23<\/span>;<\/span><\/span>\n   int n <\/span>=<\/span> <\/span>sizeof<\/span>(arr) <\/span>\/<\/span> <\/span>sizeof<\/span>(arr[<\/span>0<\/span>]);<\/span><\/span>\n   int result <\/span>=<\/span> <\/span>binarySearch<\/span>(arr, <\/span>0<\/span>, n <\/span>-<\/span> <\/span>1<\/span>, target);<\/span><\/span>\n   <\/span><\/span>\n   <\/span>if<\/span> (result <\/span>==<\/span> <\/span>-<\/span>1<\/span>)<\/span><\/span>\n      cout <\/span><<<\/span> <\/span>"<\/span>Element not found!<\/span>"<\/span>;<\/span><\/span>\n   <\/span><\/span>\n   <\/span>else<\/span><\/span>\n      cout <\/span><<<\/span> <\/span>"<\/span>Element found at index <\/span>"<\/span> <\/span><<<\/span> result;<\/span><\/span>\n   <\/span><\/span>\n   <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Bubble Sort<\/h2>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\nusing<\/span> namespace std;<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>bubbleSort<\/span>(int array[], int size) {<\/span><\/span>\n  <\/span>for<\/span> (int i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> size <\/span>-<\/span> <\/span>1<\/span>; i<\/span>++<\/span>) {<\/span><\/span>\n    <\/span>for<\/span> (int j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> size <\/span>-<\/span> i <\/span>-<\/span> <\/span>1<\/span>; j<\/span>++<\/span>) {<\/span><\/span>\n      <\/span>if<\/span> (array[j] <\/span>><\/span> array[j <\/span>+<\/span> <\/span>1<\/span>]) {<\/span><\/span>\n        <\/span>\/\/ Swap elements at positions j and j+1<\/span><\/span>\n        int temp <\/span>=<\/span> array[j];<\/span><\/span>\n        array[j] <\/span>=<\/span> array[j <\/span>+<\/span> <\/span>1<\/span>];<\/span><\/span>\n        array[j <\/span>+<\/span> <\/span>1<\/span>] <\/span>=<\/span> temp;<\/span><\/span>\n      }<\/span><\/span>\n    }<\/span><\/span>\n  }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint <\/span>main<\/span>() {<\/span><\/span>\n  int array[] <\/span>=<\/span> {<\/span>64<\/span>, <\/span>34<\/span>, <\/span>25<\/span>, <\/span>12<\/span>, <\/span>22<\/span>, <\/span>11<\/span>, <\/span>90<\/span>};<\/span><\/span>\n  int size <\/span>=<\/span> <\/span>sizeof<\/span>(array) <\/span>\/<\/span> <\/span>sizeof<\/span>(array[<\/span>0<\/span>]);<\/span><\/span>\n<\/span>\n  cout <\/span><<<\/span> <\/span>"<\/span>Before sorting: <\/span>"<\/span>;<\/span><\/span>\n  <\/span>for<\/span> (int i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> size; i<\/span>++<\/span>) {<\/span><\/span>\n    cout <\/span><<<\/span> array[i] <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  <\/span>bubbleSort<\/span>(array, size);<\/span><\/span>\n<\/span>\n  cout <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>After sorting: <\/span>"<\/span>;<\/span><\/span>\n  <\/span>for<\/span> (int i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> size; i<\/span>++<\/span>) {<\/span><\/span>\n    cout <\/span><<<\/span> array[i] <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n  }<\/span><\/span>\n<\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Insertion Sort<\/h2>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\n#include <\/span><<\/span>vector<\/span>><\/span><\/span>\nusing<\/span> namespace std;<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>insertionSort<\/span>(std::vector<\/span><<\/span>int<\/span>>&<\/span> arr) {<\/span><\/span>\n    int n <\/span>=<\/span> arr.<\/span>size<\/span>();<\/span><\/span>\n    <\/span>for<\/span> (int i <\/span>=<\/span> <\/span>1<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>) {<\/span><\/span>\n        int key <\/span>=<\/span> arr[i];<\/span><\/span>\n        int j <\/span>=<\/span> i <\/span>-<\/span> <\/span>1<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position<\/span><\/span>\n        <\/span>while<\/span> (j <\/span>>=<\/span> <\/span>0<\/span> <\/span>&&<\/span> arr[j] <\/span>><\/span> key) {<\/span><\/span>\n            arr[j <\/span>+<\/span> <\/span>1<\/span>] <\/span>=<\/span> arr[j];<\/span><\/span>\n            j<\/span>--<\/span>;<\/span><\/span>\n        }<\/span><\/span>\n        arr[j <\/span>+<\/span> <\/span>1<\/span>] <\/span>=<\/span> key;<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>printArray<\/span>(const vector<\/span><<\/span>int<\/span>>&<\/span> arr) {<\/span><\/span>\n    int n <\/span>=<\/span> arr.<\/span>size<\/span>();<\/span><\/span>\n    <\/span>for<\/span> (int i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n; i<\/span>++<\/span>)<\/span><\/span>\n        cout <\/span><<<\/span> arr[i] <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n        cout <\/span><<<\/span> std::endl;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint <\/span>main<\/span>() {<\/span><\/span>\n    vector<\/span><<\/span>int<\/span>><\/span> arr <\/span>=<\/span> { <\/span>12<\/span>, <\/span>11<\/span>, <\/span>13<\/span>, <\/span>5<\/span>, <\/span>6<\/span> };<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Original array: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>printArray<\/span>(arr);<\/span><\/span>\n<\/span>\n    <\/span>insertionSort<\/span>(arr);<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Sorted array: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>printArray<\/span>(arr);<\/span><\/span>\n<\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Selection Sort<\/h2>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\n#include <\/span><<\/span>vector<\/span>><\/span><\/span>\n<\/span>\nusing<\/span> namespace std;<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>selectionSort<\/span>(vector<\/span><<\/span>int<\/span>><\/span> <\/span>&<\/span>arr) {<\/span><\/span>\n    int n <\/span>=<\/span> arr.<\/span>size<\/span>();<\/span><\/span>\n    <\/span>for<\/span> (int i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n <\/span>-<\/span> <\/span>1<\/span>; <\/span>++<\/span>i) {<\/span><\/span>\n        int minIndex <\/span>=<\/span> i;<\/span><\/span>\n        <\/span>for<\/span> (int j <\/span>=<\/span> i <\/span>+<\/span> <\/span>1<\/span>; j <\/span><<\/span> n; <\/span>++<\/span>j) {<\/span><\/span>\n            <\/span>if<\/span> (arr[j] <\/span><<\/span> arr[minIndex]) {<\/span><\/span>\n                minIndex <\/span>=<\/span> j;<\/span><\/span>\n            }<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>if<\/span> (minIndex <\/span>!=<\/span> i) {<\/span><\/span>\n            <\/span>swap<\/span>(arr[i], arr[minIndex]);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint <\/span>main<\/span>() {<\/span><\/span>\n    vector<\/span><<\/span>int<\/span>><\/span> arr <\/span>=<\/span> {<\/span>64<\/span>, <\/span>25<\/span>, <\/span>12<\/span>, <\/span>22<\/span>, <\/span>11<\/span>};<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Array before sorting: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (int num : arr) {<\/span><\/span>\n        cout <\/span><<<\/span> num <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n    <\/span>selectionSort<\/span>(arr);<\/span><\/span>\n<\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Array after sorting: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (int num : arr) {<\/span><\/span>\n        cout <\/span><<<\/span> num <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
Quick Sort<\/h2>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\n#include <\/span><<\/span>vector<\/span>><\/span><\/span>\n<\/span>\nusing<\/span> namespace std;<\/span><\/span>\n<\/span>\n\/\/ Function to partition the array and return the pivot index<\/span><\/span>\nint <\/span>partition<\/span>(vector<\/span><<\/span>int<\/span>><\/span> <\/span>&<\/span>arr, int low, int high) {<\/span><\/span>\n    int pivot <\/span>=<\/span> arr[high]; <\/span>\/\/ Select the rightmost element as pivot<\/span><\/span>\n    int i <\/span>=<\/span> low <\/span>-<\/span> <\/span>1<\/span>; <\/span>\/\/ Index of smaller element<\/span><\/span>\n<\/span>\n    <\/span>for<\/span> (int j <\/span>=<\/span> low; j <\/span><=<\/span> high <\/span>-<\/span> <\/span>1<\/span>; j<\/span>++<\/span>) {<\/span><\/span>\n        <\/span>\/\/ If current element is smaller than or equal to pivot<\/span><\/span>\n        <\/span>if<\/span> (arr[j] <\/span><=<\/span> pivot) {<\/span><\/span>\n            i<\/span>++<\/span>; <\/span>\/\/ Increment index of smaller element<\/span><\/span>\n            <\/span>swap<\/span>(arr[i], arr[j]);<\/span><\/span>\n        }<\/span><\/span>\n    }<\/span><\/span>\n    <\/span>swap<\/span>(arr[i <\/span>+<\/span> <\/span>1<\/span>], arr[high]);<\/span><\/span>\n    <\/span>return<\/span> i <\/span>+<\/span> <\/span>1<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Function to perform the quicksort<\/span><\/span>\nvoid<\/span> <\/span>quickSort<\/span>(vector<\/span><<\/span>int<\/span>><\/span> <\/span>&<\/span>arr, int low, int high) {<\/span><\/span>\n    <\/span>if<\/span> (low <\/span><<\/span> high) {<\/span><\/span>\n        <\/span>\/\/ Partitioning index<\/span><\/span>\n        int pi <\/span>=<\/span> <\/span>partition<\/span>(arr, low, high);<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Separate recursive calls for left and right partitions<\/span><\/span>\n        <\/span>quickSort<\/span>(arr, low, pi <\/span>-<\/span> <\/span>1<\/span>);<\/span><\/span>\n        <\/span>quickSort<\/span>(arr, pi <\/span>+<\/span> <\/span>1<\/span>, high);<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint <\/span>main<\/span>() {<\/span><\/span>\n    vector<\/span><<\/span>int<\/span>><\/span> arr <\/span>=<\/span> {<\/span>64<\/span>, <\/span>25<\/span>, <\/span>12<\/span>, <\/span>22<\/span>, <\/span>11<\/span>};<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Array before sorting: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (int num : arr) {<\/span><\/span>\n        cout <\/span><<<\/span> num <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n    int n <\/span>=<\/span> arr.<\/span>size<\/span>();<\/span><\/span>\n    <\/span>quickSort<\/span>(arr, <\/span>0<\/span>, n <\/span>-<\/span> <\/span>1<\/span>);<\/span><\/span>\n<\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Array after sorting: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (int num : arr) {<\/span><\/span>\n        cout <\/span><<<\/span> num <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n <\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Merge Sort<\/h2>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\n#include <\/span><<\/span>vector<\/span>><\/span><\/span>\n<\/span>\nusing<\/span> namespace std;<\/span><\/span>\n<\/span>\n\/\/ Function to merge two sorted subarrays into one sorted array<\/span><\/span>\nvoid<\/span> <\/span>merge<\/span>(vector<\/span><<\/span>int<\/span>><\/span> <\/span>&<\/span>arr, int left, int mid, int right) {<\/span><\/span>\n    int n1 <\/span>=<\/span> mid <\/span>-<\/span> left <\/span>+<\/span> <\/span>1<\/span>;<\/span><\/span>\n    int n2 <\/span>=<\/span> right <\/span>-<\/span> mid;<\/span><\/span>\n<\/span>\n    <\/span>\/\/ Create temporary arrays<\/span><\/span>\n    vector<\/span><<\/span>int<\/span>><\/span> <\/span>L<\/span>(n1), <\/span>R<\/span>(n2);<\/span><\/span>\n<\/span>\n    <\/span>\/\/ Copy data to temporary arrays L[] and R[]<\/span><\/span>\n    <\/span>for<\/span> (int i <\/span>=<\/span> <\/span>0<\/span>; i <\/span><<\/span> n1; <\/span>++<\/span>i)<\/span><\/span>\n        L[i] <\/span>=<\/span> arr[left <\/span>+<\/span> i];<\/span><\/span>\n    <\/span>for<\/span> (int j <\/span>=<\/span> <\/span>0<\/span>; j <\/span><<\/span> n2; <\/span>++<\/span>j)<\/span><\/span>\n        R[j] <\/span>=<\/span> arr[mid <\/span>+<\/span> <\/span>1<\/span> <\/span>+<\/span> j];<\/span><\/span>\n<\/span>\n    <\/span>\/\/ Merge the temporary arrays back into arr[left..right]<\/span><\/span>\n    int i <\/span>=<\/span> <\/span>0<\/span>, j <\/span>=<\/span> <\/span>0<\/span>, k <\/span>=<\/span> left;<\/span><\/span>\n    <\/span>while<\/span> (i <\/span><<\/span> n1 <\/span>&&<\/span> j <\/span><<\/span> n2) {<\/span><\/span>\n        <\/span>if<\/span> (L[i] <\/span><=<\/span> R[j]) {<\/span><\/span>\n            arr[k] <\/span>=<\/span> L[i];<\/span><\/span>\n            <\/span>++<\/span>i;<\/span><\/span>\n        } <\/span>else<\/span> {<\/span><\/span>\n            arr[k] <\/span>=<\/span> R[j];<\/span><\/span>\n            <\/span>++<\/span>j;<\/span><\/span>\n        }<\/span><\/span>\n        <\/span>++<\/span>k;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>\/\/ Copy the remaining elements of L[], if any<\/span><\/span>\n    <\/span>while<\/span> (i <\/span><<\/span> n1) {<\/span><\/span>\n        arr[k] <\/span>=<\/span> L[i];<\/span><\/span>\n        <\/span>++<\/span>i;<\/span><\/span>\n        <\/span>++<\/span>k;<\/span><\/span>\n    }<\/span><\/span>\n<\/span>\n    <\/span>\/\/ Copy the remaining elements of R[], if any<\/span><\/span>\n    <\/span>while<\/span> (j <\/span><<\/span> n2) {<\/span><\/span>\n        arr[k] <\/span>=<\/span> R[j];<\/span><\/span>\n        <\/span>++<\/span>j;<\/span><\/span>\n        <\/span>++<\/span>k;<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Function to implement merge sort<\/span><\/span>\nvoid<\/span> <\/span>mergeSort<\/span>(vector<\/span><<\/span>int<\/span>><\/span> <\/span>&<\/span>arr, int left, int right) {<\/span><\/span>\n    <\/span>if<\/span> (left <\/span><<\/span> right) {<\/span><\/span>\n        int mid <\/span>=<\/span> left <\/span>+<\/span> (right <\/span>-<\/span> left) <\/span>\/<\/span> <\/span>2<\/span>; <\/span>\/\/ Calculate the middle index<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Sort first and second halves<\/span><\/span>\n        <\/span>mergeSort<\/span>(arr, left, mid);<\/span><\/span>\n        <\/span>mergeSort<\/span>(arr, mid <\/span>+<\/span> <\/span>1<\/span>, right);<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Merge the sorted halves<\/span><\/span>\n        <\/span>merge<\/span>(arr, left, mid, right);<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint <\/span>main<\/span>() {<\/span><\/span>\n    vector<\/span><<\/span>int<\/span>><\/span> arr <\/span>=<\/span> {<\/span>64<\/span>, <\/span>25<\/span>, <\/span>12<\/span>, <\/span>22<\/span>, <\/span>11<\/span>};<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Array before sorting: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (int num : arr) {<\/span><\/span>\n        cout <\/span><<<\/span> num <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n    int n <\/span>=<\/span> arr.<\/span>size<\/span>();<\/span><\/span>\n    <\/span>mergeSort<\/span>(arr, <\/span>0<\/span>, n <\/span>-<\/span> <\/span>1<\/span>);<\/span><\/span>\n<\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Array after sorting: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (int num : arr) {<\/span><\/span>\n        cout <\/span><<<\/span> num <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n\n\n\n
Heap Sort<\/h2>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
#include <\/span><<\/span>iostream<\/span>><\/span><\/span>\n#include <\/span><<\/span>vector<\/span>><\/span><\/span>\n<\/span>\nusing<\/span> namespace std;<\/span><\/span>\n<\/span>\n\/\/ Function to heapify a subtree rooted at index 'root' in a vector 'arr' of size 'n'<\/span><\/span>\nvoid<\/span> <\/span>heapify<\/span>(vector<\/span><<\/span>int<\/span>><\/span> <\/span>&<\/span>arr, int n, int root) {<\/span><\/span>\n    int largest <\/span>=<\/span> root; <\/span>\/\/ Initialize largest as root<\/span><\/span>\n    int left <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> root <\/span>+<\/span> <\/span>1<\/span>; <\/span>\/\/ Left child<\/span><\/span>\n    int right <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> root <\/span>+<\/span> <\/span>2<\/span>; <\/span>\/\/ Right child<\/span><\/span>\n<\/span>\n    <\/span>\/\/ If left child is larger than root<\/span><\/span>\n    <\/span>if<\/span> (left <\/span><<\/span> n <\/span>&&<\/span> arr[left] <\/span>><\/span> arr[largest])<\/span><\/span>\n        largest <\/span>=<\/span> left;<\/span><\/span>\n<\/span>\n    <\/span>\/\/ If right child is larger than largest so far<\/span><\/span>\n    <\/span>if<\/span> (right <\/span><<\/span> n <\/span>&&<\/span> arr[right] <\/span>><\/span> arr[largest])<\/span><\/span>\n        largest <\/span>=<\/span> right;<\/span><\/span>\n<\/span>\n    <\/span>\/\/ If largest is not root<\/span><\/span>\n    <\/span>if<\/span> (largest <\/span>!=<\/span> root) {<\/span><\/span>\n        <\/span>swap<\/span>(arr[root], arr[largest]);<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Recursively heapify the affected sub-tree<\/span><\/span>\n        <\/span>heapify<\/span>(arr, n, largest);<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Function to perform heap sort<\/span><\/span>\nvoid<\/span> <\/span>heapSort<\/span>(vector<\/span><<\/span>int<\/span>><\/span> <\/span>&<\/span>arr) {<\/span><\/span>\n    int n <\/span>=<\/span> arr.<\/span>size<\/span>();<\/span><\/span>\n<\/span>\n    <\/span>\/\/ Build heap (rearrange array)<\/span><\/span>\n    <\/span>for<\/span> (int i <\/span>=<\/span> n <\/span>\/<\/span> <\/span>2<\/span> <\/span>-<\/span> <\/span>1<\/span>; i <\/span>>=<\/span> <\/span>0<\/span>; i<\/span>--<\/span>)<\/span><\/span>\n        <\/span>heapify<\/span>(arr, n, i);<\/span><\/span>\n<\/span>\n    <\/span>\/\/ One by one extract an element from heap<\/span><\/span>\n    <\/span>for<\/span> (int i <\/span>=<\/span> n <\/span>-<\/span> <\/span>1<\/span>; i <\/span>><\/span> <\/span>0<\/span>; i<\/span>--<\/span>) {<\/span><\/span>\n        <\/span>\/\/ Move current root to end<\/span><\/span>\n        <\/span>swap<\/span>(arr[<\/span>0<\/span>], arr[i]);<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Call max heapify on the reduced heap<\/span><\/span>\n        <\/span>heapify<\/span>(arr, i, <\/span>0<\/span>);<\/span><\/span>\n    }<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint <\/span>main<\/span>() {<\/span><\/span>\n    vector<\/span><<\/span>int<\/span>><\/span> arr <\/span>=<\/span> {<\/span>64<\/span>, <\/span>25<\/span>, <\/span>12<\/span>, <\/span>22<\/span>, <\/span>11<\/span>};<\/span><\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Array before sorting: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (int num : arr) {<\/span><\/span>\n        cout <\/span><<<\/span> num <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n    <\/span>heapSort<\/span>(arr);<\/span><\/span>\n<\/span>\n    cout <\/span><<<\/span> <\/span>"<\/span>Array after sorting: <\/span>"<\/span>;<\/span><\/span>\n    <\/span>for<\/span> (int num : arr) {<\/span><\/span>\n        cout <\/span><<<\/span> num <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n    }<\/span><\/span>\n    cout <\/span><<<\/span> endl;<\/span><\/span>\n<\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span><\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"
In computer science, an algorithm is a set of steps or instructions that are designed to solve a specific problem or accomplish a particular task. It is essentially a well-defined procedure that can be followed to achieve a specific goal. Algorithms can be expressed in various forms, such as natural language, flowcharts, pseudocode, or programming […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/alitousen.com\/index.php?rest_route=\/wp\/v2\/pages\/153"}],"collection":[{"href":"https:\/\/alitousen.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/alitousen.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/alitousen.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/alitousen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=153"}],"version-history":[{"count":9,"href":"https:\/\/alitousen.com\/index.php?rest_route=\/wp\/v2\/pages\/153\/revisions"}],"predecessor-version":[{"id":301,"href":"https:\/\/alitousen.com\/index.php?rest_route=\/wp\/v2\/pages\/153\/revisions\/301"}],"wp:attachment":[{"href":"https:\/\/alitousen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=153"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}