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

  1. This blog provides excellent insights into the challenges students face while preparing academic essays. Every assignment has unique requirements, making personalized guidance very important. Students looking for custom essay writing help should choose experienced academic professionals who understand university standards and deliver original work. Your article offers practical advice that encourages better organization and stronger writing skills. Thank you for sharing such helpful information. I look forward to exploring more educational content on your blog in the future.

    ReplyDelete

Post a Comment

Popular posts from this blog

C++ Exception Handling and file handling

Basic DSA programs in c++