Data-Structures-and-Algorithms-Essentials

DSA PDF NOTES 

Click Here to get PDF

01_input_output_update.cpp

#include <iostream>

using namespace std;

int main(){

    // update ; set all elements to zero

    int n, arr[100]={0};

    cout<<"Enter no of elements \n";

    cin>>n;

    // input 

    for(int i=0; i<n; i++){

        cin>>arr[i];

    }

    // output 

    for(int i=0; i<n; i++){

        cout<<arr[i]<<" ";

    }

    return 0;

}

02_pass_array_to_function.cpp

#include <iostream>

using namespace std;

// pass by refernce

void printArray(int * arr, int n){

    for(int i=0; i<n; i++){

        cout<<arr[i]<<endl;

    }

}

int main(){

    int arr[] = {1,2,3,4,5,6};

    int n = sizeof(arr)/sizeof(int);

    printArray(arr,n);

    return 0;

}

03_linear_search.cpp

#include <iostream>

using namespace std;

// brute force technique

int linearSearch(int arr[], int n, int key){

    for(int i=0; i<n; i++){

        if(arr[i]==key) return i;

    }

    return -1;

}

int main(){

    int arr[] = {1,2,3,4,5,6};

    int n = sizeof(arr)/sizeof(int);

    

    int key;

    cin>>key;

    int index = linearSearch(arr,n,key);

    if(index!=-1)   cout<<"Present at index "<< index << endl;

    else   cout<<"Not found"<<endl;

    return 0;

}

05_reverse_array.cpp

#include <iostream>

using namespace std;

void reverseArray(int arr[], int n){

    int low = 0, high = n - 1;

    while(low < high){

        swap(arr[low++],arr[high--]);

    }

}

int main(){

    int arr[] = {1,2,3,4,5,6};

    int n = sizeof(arr)/sizeof(int);

    reverseArray(arr,n);

    // print array

    for(int i=0; i<n; i++){

        cout<<arr[i]<< " ";

    }

    cout<<endl;

    return 0;

}

06_printing_pairs.cpp

#include <iostream>

using namespace std;

void printPairs(int arr[], int n){

    for(int i=0; i<n; i++){

        int x = arr[i];

        for(int j=i+1; j<n; j++){

            int y = arr[j];

            cout<<"("<<x<<","<<y<<")"<<endl;

        }

        cout<<endl;

    }

}

int main(){

    int arr[] = {1,2,3,4,5,6};

    int n = sizeof(arr)/sizeof(int);

    // print array 

    for(int x: arr){

        cout<<x<<endl;

    }

    cout<<endl<<"Pairs : "<<endl;

    printPairs(arr,n);

    return 0;

}

07_printing_subarrays.cpp

#include <iostream>

using namespace std;

void printSubarrays(int arr[], int n){

    for(int i=0; i<n; i++){

        for(int j=i; j<n; j++){

            for(int k=i; k<=j; k++){

                cout<<arr[k]<<",";

            }

            cout<<endl;

        }

        cout<<endl;

    }

}

int main(){

    int arr[] = {1,2,3,4,5,6};

    int n = sizeof(arr)/sizeof(int);

    // print array 

    for(int x: arr){

        cout<<x<<endl;

    }

    cout<<endl<<"Subarrays : "<<endl;

    printSubarrays(arr,n);

    return 0;

}

bubble_sort.cpp

#include<bits/stdc++.h>

using namespace std;

vector<int> optimizedBubbleSort(vector<int> v){

    int n = v.size();

    bool swapped;

    for(int times=0; times<n-1; times++){

        swapped = false;

        for(int i=0; i<n-times-1; i++){

            if(v[i]>v[i+1]){

                swap(v[i],v[i+1]);

                swapped = true;

            }

        }

        if(swapped==false)  break;

    }

   return v; 

}

int main(){

    vector<int> arr = {32,85,12,67,13,56,45,90,1,52};

    vector<int> res = optimizedBubbleSort(arr);

    cout<<"Bubble Sort Result :"<<endl;

    for(auto x: res){

        cout<<x<<endl;

    }

    return 0;

}

insertion_sort.cpp

#include<bits/stdc++.h>

using namespace std;

vector<int> insertionSort(vector<int> arr){

    int n = arr.size();

    // loop through array 1 to n-1

    for(int i=1; i<n; i++){

        int current = arr[i];

        int prev = i-1;

        while(prev>=0 and arr[prev]>current){

            arr[prev+1] = arr[prev];

            prev -= 1;

        }

        arr[prev+1] = current;

    }

    return arr;

}

int main(){

    vector<int> arr = {32,85,12,67,13,56,45,90,1,52};

    vector<int> res = insertionSort(arr);

    cout<<"Insertion Sort Result :"<<endl;

    for(auto x: res){

        cout<<x<<endl;

    }

    return 0;

}

selection_sort.cpp

#include<bits/stdc++.h>

using namespace std;

vector<int> insertionSort(vector<int> arr){

    int n = arr.size();

    // loop through array 0 to n-1

    for(int i=0; i<=n-2; i++){

        int min_pos = i;

        for(int j=i; j<=n-1; j++){

            if(arr[j]<arr[min_pos]){

                min_pos = j;

            }

        }

        // swap outside loop

        swap(arr[min_pos],arr[i]);

    }

    

    return arr;

}

int main(){

    vector<int> arr = {32,85,12,67,13,56,45,90,1,52};

    vector<int> res = insertionSort(arr);

    cout<<"Selection Sort Result :"<<endl;

    for(auto x: res){

        cout<<x<<endl;

    }

    return 0;

}