Sorting DSA in c++

 

Bubble Sort

 

#include <iostream>

using namespace std;

 

void bubbleSort(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 arr[] = {64, 34, 25, 12, 22, 11, 90};

    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    cout << "Sorted array: ";

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

    return 0;

}

 

 

2. Selection Sort

Time Complexity: O(n²)
Stable: No

#include <iostream>

using namespace std;

 

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

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

        int minIdx = i;

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

            if (arr[j] < arr[minIdx])

                minIdx = j;

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

    }

}

 

int main() {

    int arr[] = {64, 25, 12, 22, 11};

    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    cout << "Sorted array: ";

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

    return 0;

}

3. Insertion Sort

Time Complexity: O(n²)
Stable: Yes

#include <iostream>

using namespace std;

 

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

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

        int key = arr[i], j = i - 1;

        while (j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            j--;

        }

        arr[j + 1] = key;

    }

}

 

int main() {

    int arr[] = {12, 11, 13, 5, 6};

    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    cout << "Sorted array: ";

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

    return 0;

}

4. Merge Sort

Time Complexity: O(n log n)
Stable: Yes

 

#include <iostream>

using namespace std;

 

// Function to merge two halves

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

    int n1 = mid - left + 1;

    int n2 = right - mid;

   

    int leftArr[n1], rightArr[n2];

 

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

        leftArr[i] = arr[left + i];

    for (int i = 0; i < n2; i++)

        rightArr[i] = arr[mid + 1 + i];

 

    int i = 0, j = 0, k = left;

   

    while (i < n1 && j < n2) {

        if (leftArr[i] <= rightArr[j]) {

            arr[k] = leftArr[i];

            i++;

        } else {

            arr[k] = rightArr[j];

            j++;

        }

        k++;

    }

 

    while (i < n1) {

        arr[k] = leftArr[i];

        i++;

        k++;

    }

 

    while (j < n2) {

        arr[k] = rightArr[j];

        j++;

        k++;

    }

}

 

// Function to perform merge sort

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

    if (left < right) {

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

       

        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);

       

        merge(arr, left, mid, right);

    }

}

 

// Function to print the array

void printArray(int arr[], int size) {

    for (int i = 0; i < size; i++)

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

    cout << endl;

}

 

int main() {

    int arr[] = {12, 11, 13, 5, 6, 7};

    int size = sizeof(arr) / sizeof(arr[0]);

 

    cout << "Original array: ";

    printArray(arr, size);

 

    mergeSort(arr, 0, size - 1);

 

    cout << "Sorted array: ";

    printArray(arr, size);

 

    return 0;

}

Explanation:

  1. Divide: The array is recursively divided into two halves until single-element arrays are left.
  2. Merge: The two sorted halves are merged in sorted order.
  3. Merge Function: It merges two sorted subarrays into a single sorted array.
  4. Time Complexity: O(nlog⁡n)O(n \log n)O(nlogn)

Let me know if you need further explanation! 🚀

4o

You said:

give me explanation also

ChatGPT said:

ChatGPT

Explanation of Merge Sort

Merge Sort is a divide and conquer algorithm that splits an array into smaller subarrays, sorts them, and then merges them back together.

Steps of Merge Sort

  1. Divide:
    • The array is recursively divided into two halves until each subarray contains only one element (a single element is always sorted).
  2. Conquer (Sort & Merge):
    • The sorted subarrays are merged back together in sorted order.

Code Breakdown

1. Merging Two Sorted Arrays (merge function)

cpp

CopyEdit

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

    int n1 = mid - left + 1; // Size of left subarray

    int n2 = right - mid;    // Size of right subarray

 

    int leftArr[n1], rightArr[n2]; // Temporary arrays

 

    // Copy data into temporary arrays

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

        leftArr[i] = arr[left + i];

    for (int i = 0; i < n2; i++)

        rightArr[i] = arr[mid + 1 + i];

 

    int i = 0, j = 0, k = left; // Indices for left, right, and merged array

   

    // Merge the two sorted subarrays

    while (i < n1 && j < n2) {

        if (leftArr[i] <= rightArr[j]) {

            arr[k] = leftArr[i];

            i++;

        } else {

            arr[k] = rightArr[j];

            j++;

        }

        k++;

    }

 

    // Copy remaining elements from left array (if any)

    while (i < n1) {

        arr[k] = leftArr[i];

        i++;

        k++;

    }

 

    // Copy remaining elements from right array (if any)

    while (j < n2) {

        arr[k] = rightArr[j];

        j++;

        k++;

    }

}

📌 What it does:

  • Copies elements into two temporary arrays.
  • Compares and merges them in sorted order.
  • If any elements remain, they are copied into the main array.

2. Recursive Sorting (mergeSort function)

cpp

CopyEdit

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

    if (left < right) {

        int mid = left + (right - left) / 2; // Find middle index

       

        mergeSort(arr, left, mid);    // Sort first half

        mergeSort(arr, mid + 1, right); // Sort second half

       

        merge(arr, left, mid, right); // Merge the sorted halves

    }

}

📌 What it does:

  • Base Case: If there's one element, it's already sorted.
  • Recursive Calls: Splits the array into halves.
  • Merge Step: Merges two sorted halves.

3. Printing the Array (printArray function)

cpp

CopyEdit

void printArray(int arr[], int size) {

    for (int i = 0; i < size; i++)

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

    cout << endl;

}

📌 What it does:

  • Simply prints the array elements.

4. Main Function (main)

cpp

CopyEdit

int main() {

    int arr[] = {12, 11, 13, 5, 6, 7};

    int size = sizeof(arr) / sizeof(arr[0]);

 

    cout << "Original array: ";

    printArray(arr, size);

 

    mergeSort(arr, 0, size - 1);

 

    cout << "Sorted array: ";

    printArray(arr, size);

 

    return 0;

}

5. Quick Sort

Time Complexity: O(n log n)
Stable: No

#include <iostream>

using namespace std;

 

int partition(int arr[], int low, int high) {

    int pivot = arr[high], i = low - 1;

    for (int j = low; j < high; j++) {

        if (arr[j] < pivot) swap(arr[++i], arr[j]);

    }

    swap(arr[i + 1], arr[high]);

    return i + 1;

}

 

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);

        quickSort(arr, pi + 1, high);

    }

}

 

int main() {

    int arr[] = {10, 7, 8, 9, 1, 5};

    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";

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

    return 0;

}

6. Heap Sort

Time Complexity: O(n log n)
Stable: No

#include <iostream>

using namespace std;

 

void heapify(int arr[], int n, int i) {

    int largest = i, left = 2 * i + 1, right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;

    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {

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

        heapify(arr, n, largest);

    }

}

 

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

    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {

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

        heapify(arr, i, 0);

    }

}

 

int main() {

    int arr[] = {12, 11, 13, 5, 6, 7};

    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array: ";

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

    return 0;

}

 

 

 

 

 

 

 

 

 

 

2. Selection Sort

Concept:

  • Finds the minimum element and swaps it with the first unsorted element.
  • Reduces the unsorted portion one step at a time.

Time Complexity:

  • Best/Worst/Average: O(n²)

C++ Code:

cpp

CopyEdit

#include <iostream>

using namespace std;

 

void selectionSort(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]); // Swap the minimum element with the first element

    }

}

 

int main() {

    int arr[] = {64, 25, 12, 22, 11};

    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

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

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

    return 0;

}

Sure! Let's break down the Selection Sort code step by step.

Understanding the Code

1. Header Files and Namespace

#include <iostream>

using namespace std;

  • #include <iostream>: Allows input/output operations (cout for printing).
  • using namespace std;: Avoids the need to write std::cout, std::endl, etc.

2. Selection Sort Function

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

  • This function sorts an array arr[] of size n using the Selection Sort algorithm.

Loop to Iterate Over Array

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

  • Outer loop: Runs n-1 times because after sorting n-1 elements, the last element will already be in place.

Finding the Minimum Element

int min_idx = i; // Assume the first unsorted element is the smallest

  • Assume the first element of the unsorted part is the smallest.

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

    if (arr[j] < arr[min_idx]) // Find the minimum element

        min_idx = j;

}

 

In Selection Sort, we’re looking for the smallest element in the unsorted part of the array and then swapping it into its correct position.

Here’s the key:

  • i represents the current index we’re placing in the correct position.
  • j starts from i + 1 because:
    • We assume that the smallest element in the remaining unsorted portion is at index i.
    • So, there’s no need to compare it with itself — we start looking from the next element.
    • If j started at i, it would always compare the element with itself first, which is unnecessary.

 

  • Inner loop: Scans the remaining unsorted part of the array to find the smallest element.
  • If we find a smaller element, we update min_idx.

Swapping the Minimum Element

swap(arr[i], arr[min_idx]); // Swap the found minimum element with the first unsorted element

  • After finding the smallest element, we swap it with the first unsorted element.

3. Main Function

cpp

CopyEdit

int main() {

    int arr[] = {64, 25, 12, 22, 11};

    int n = sizeof(arr) / sizeof(arr[0]); // Calculate array size

  • sizeof(arr) / sizeof(arr[0]): Finds the number of elements in the array.

cpp

CopyEdit

selectionSort(arr, n); // Call the sorting function

  • Calls the selectionSort() function to sort the array.

cpp

CopyEdit

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

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

  • Prints the sorted array.

cpp

CopyEdit

return 0;

  • Ends the program.

Dry Run (Step-by-Step Execution)

Input Array

arr[] = {64, 25, 12, 22, 11}

Iteration 1 (i = 0)

  • Find the smallest in {64, 25, 12, 22, 11} → Smallest = 11 at index 4.
  • Swap 64 ↔ 11
  • Array after swap: [11, 25, 12, 22, 64]

Iteration 2 (i = 1)

  • Find the smallest in {25, 12, 22, 64} → Smallest = 12 at index 2.
  • Swap 25 ↔ 12
  • Array after swap: [11, 12, 25, 22, 64]

Iteration 3 (i = 2)

  • Find the smallest in {25, 22, 64} → Smallest = 22 at index 3.
  • Swap 25 ↔ 22
  • Array after swap: [11, 12, 22, 25, 64]

Iteration 4 (i = 3)

  • Find the smallest in {25, 64} → Smallest = 25 (already at correct position).
  • No swap needed.

Final Sorted Array

[11, 12, 22, 25, 64] ✅

 

Comments

Post a Comment

Popular posts from this blog

programs of oops in c++

  Inheritance   Single level inheritance:   #include <iostream>   using namespace std;     class Account {      public:      int a=8;    int b=56;     };     class Programmer: public Account {               public:               void display(){             cout<<a+b;    }   };        int main() {       Programmer p1;       p1.display();     return 0;   }       #include <iostream>   using namespace std;   class A   {       int a = 4;       int b = 5;     ...
Read more

Basic DSA programs in c++

1. Linear Search #include <iostream> using namespace std;   int linearSearch(int arr[], int size, int key) {     for (int i = 0; i < size; i++) {         if (arr[i] == key)             return i; // Return index if found     }     return -1; // Return -1 if not found }   int main() {     int arr[] = {10, 20, 30, 40, 50};     int size = sizeof(arr) / sizeof(arr[0]);     int key;       cout << "Enter the element to search: ";     cin >> key;       int result = linearSearch(arr, size, key);     if (result != -1)         cout << "Element found at index " << result << endl;     else   ...
Read more

C++ Exception Handling and file handling

  C++ Exceptions When executing C++ code, different errors can occur: coding errors made by the programmer, errors due to wrong input, or other unforeseeable things.   When an error occurs, C++ will normally stop and generate an error message. The technical term for this is: C++ will throw an exception (throw an error).   C++ try and catch Exception handling in C++ consist of three keywords: try, throw and catch:   The try statement allows you to define a block of code to be tested for errors while it is being executed.   The throw keyword throws an exception when a problem is detected, which lets us create a custom error.   The catch statement allows you to define a block of code to be executed, if an error occurs in the try block.   The try and catch keywords come in pairs:     try {   // Block of code to try   throw exception; // Throw an exception when a problem arise } catch () { ...
Read more