Scribd Logo
Upload

Welcome to Scribd!

  • 0 views

    dsa codes

    Uploaded by

    bezawadayashwitha

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    dsa codes

    Uploaded by

    bezawadayashwitha
    0 views10 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    0 views10 pages

    dsa codes

    Uploaded by

    bezawadayashwitha

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 10

    #include <iostream>

    using namespace std;


    void swap(int *a,int *b){
    int temp = *a;
    *a=*b;\
    *b=temp;
    }
    int partition(int arr[],int left,int right){
    int pivot = arr[right];
    int i = left - 1;
    for(int j=left;j<right;j++){
    if(arr[j]<pivot){
    i++;
    swap(&arr[i],&arr[j]);
    }
    }
    swap(&arr[i+1],&arr[right]);
    return i+1;
    }
    void quick_sort(int arr[],int left,int right){
    if(left<right){
    int pivot = partition(arr,left,right);
    quick_sort(arr,left,pivot-1);
    quick_sort(arr,pivot+1,right);
    }
    }
    int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++){
    cin>>arr[i];
    }
    quick_sort(arr,0,n-1);
    for(int i=0;i<n;i++){
    cout<<arr[i];
    }
    return 0;
    }
    // MERGE SORT
    #include <iostream>
    using namespace std;

    void merge(int arr[], int left, int mid, int right) {


    int n1 = mid - left + 1;
    int n2 = right - mid;

    int a[n1], b[n2];

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


    a[i = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
    b[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
    if (a[i] <= b[j]) {
    arr[k++] = a[i++];
    } else {
    arr[k++] = b[j++];
    }
    }

    while (i < n1) {


    arr[k++] = a[i++];
    }

    while (j < n2) {


    arr[k++] = b[j++];
    }
    }

    void merge_sort(int arr[], int left, int right) {


    if (left < right) {
    int mid = left + (right - left) / 2;

    merge_sort(arr, left, mid);


    merge_sort(arr, mid + 1, right);
    merge(arr, left, mid, right);
    }
    }

    int main() {
    int n;
    cin >> n;
    int arr[n];
    cout << "Enter the elements:\n";
    for (int i = 0; i < n; i++) {
    cin >> arr[i];
    }
    merge_sort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
    }

    // BUBBLE SORT

    #include <iostream>
    using namespace std;

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


    for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
    if (arr[j] > arr[j + 1]) {
    swap(arr[j], arr[j + 1]);
    }
    }
    }
    }

    int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
    cin >> arr[i];
    }
    bubble_sort(arr, n);
    for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
    }

    // INSERTION SORT

    #include <iostream>
    using namespace std;

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


    for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j];
    j--;
    }
    arr[j + 1] = key;
    }
    }

    int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];

    cout << "Enter the elements:\n";


    for (int i = 0; i < n; i++) {
    cin >> arr[i];
    }

    insertion_sort(arr, n);
    cout << "Sorted array:\n";
    for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
    }

    // INSERTION SORT

    #include <iostream>
    using namespace std;

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


    for (int i = 0; i < n - 1; i++) {
    int min_idx = i;
    for (int j = i + 1; j < n; j++) {
    if (arr[j] < arr[min_idx]) {
    min_idx = j;
    }
    }
    swap(arr[i], arr[min_idx]);
    }
    }

    int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];

    cout << "Enter the elements:\n";


    for (int i = 0; i < n; i++) {
    cin >> arr[i];
    }

    selection_sort(arr, n);

    cout << "Sorted array:\n";


    for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
    }

    // LINEAR SEARCH

    #include <iostream>
    using namespace std;

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


    for (int i = 0; i < n; i++) {
    if (arr[i] == key) {
    return i; // Return the index if the key is found
    }
    }
    return -1; // Return -1 if the key is not found
    }

    int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];

    cout << "Enter the elements:\n";


    for (int i = 0; i < n; i++) {
    cin >> arr[i];
    }

    int key;
    cout << "Enter the element to search for: ";
    cin >> key;

    int result = linear_search(arr, n, key);


    if (result != -1) {
    cout << "Element found at index: " << result << endl;
    } else {
    cout << "Element not found." << endl;
    }

    return 0;
    }

    // BINARY SEARCH

    #include <iostream>
    using namespace std;

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


    int left = 0;
    int right = n - 1;

    while (left <= right) {


    int mid = left + (right - left) / 2; // To avoid overflow

    if (arr[mid] == key) {
    return mid; // Return the index if the key is found
    } else if (arr[mid] < key) {
    left = mid + 1; // Search in the right half
    } else {
    right = mid - 1; // Search in the left half
    }
    }
    return -1; // Return -1 if the key is not found
    }

    int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];

    cout << "Enter the elements (sorted):\n";


    for (int i = 0; i < n; i++) {
    cin >> arr[i];
    }
    int key;
    cout << "Enter the element to search for: ";
    cin >> key;

    int result = binary_search(arr, n, key);


    if (result != -1) {
    cout << "Element found at index: " << result << endl;
    } else {
    cout << "Element not found." << endl;
    }

    return 0;
    }

    // LINKED LIST

    Insertion and deletion in the front

    #include <iostream>
    using namespace std;
    class Node{
    public:
    int data;
    Node *next;
    };
    void insert_front(Node **head,int data ){
    Node *ptr = new Node();
    ptr->data = data;
    ptr->next = *head;
    *head = ptr;
    }
    void delete_front(Node*& head){
    if(head==nullptr){
    cout<<"linked list is empty"<<endl;
    return;
    }
    Node *temp = head;
    head = head->next;
    delete temp;
    }
    void display(Node *node){
    while(node!=nullptr){
    cout<<node->data<<endl;
    node = node->next;
    }
    cout<<endl;
    }
    int main(){
    Node *head = nullptr;
    insert_front(&head,10);
    insert_front(&head,20);
    display(head);
    delete_front(head);
    display(head);
    return 0;
    }

    // linked list insertion

    include <iostream>
    using namespace std;
    class Node{
    public:
    int data;
    Node *next;
    };
    void insert_front(Node **head,int data){
    Node *nextptr = new Node();
    nextptr->data = data;
    nextptr->next = *head;
    *head = nextptr;
    }
    void display(Node *node){
    while(node!=nullptr){
    cout<<node->data<<endl;
    node = node->next;
    }
    }
    int main(){
    Node *head = nullptr;
    insert_front(&head,10);
    insert_front(&head,20);
    display(head);
    return 0;
    }

    #include <iostream>
    using namespace std;
    class Node{
    public:
    int data;
    Node *next;
    };
    void insert_last(Node **head,int data){
    Node *nextptr = new Node();
    nextptr->data = data;
    nextptr->next = nullptr;
    if(*head==nullptr){
    *head = nextptr;
    }else{
    Node *temp = *head;
    while(temp->next!=nullptr){
    temp=temp->next;
    }
    temp->next = nextptr;
    }
    cout<<nextptr->data<<endl;
    }
    int main(){
    Node *head = nullptr;
    insert_last(&head,10);
    insert_last(&head,20);
    return 0;
    }

    You might also like