# #9.Journey to DSA in C++

"Hey, it's Joyshree! 🌟 Are you ready to set sail on an exciting journey into the world of DSA in C++?

Hey there, fellow coding enthusiasts! 👋 Welcome back to our exciting journey into the fascinating world of Data Structures and Algorithms (DSA) using C++. I hope you've been enjoying the ride so far because today's pit stop is going to be both enlightening and exhilarating. 🌟

## Sorting

Sorting is akin to computer science's unsung hero. It serves as the foundation for a vast array of digital operations, from compiling data into databases to finding things in your favorite apps. Merge Sort and Quick Sort stand out among the many sorting algorithms available for their beauty and effectiveness. We'll explain the theories and methods of these two sorting superheroes in this blog.

## **Merge Sort: Divide and Conquer 🌟**

### **The Concept 🧐**

Merge Sort is fundamentally a "divide and conquer" algorithm. It divides the unsorted list into smaller sub-lists repeatedly until each sub-list has just one element. The fully sorted list is the only sub-list that is left after combining these sub-lists to create fresh sorted sub-lists.

### **Key Techniques 🛠️**

1. **Divide**: Split the unsorted list into two halves.
    
2. **Conquer**: Recursively sort both halves.
    
3. **Merge**: Merge the two sorted halves back together to create a single sorted list.
    

Merge Sort is like sorting papers by dividing them into smaller piles, sorting each pile separately, and then carefully merging them back into one neat stack.

## **Quick Sort: The Swift Sorcerer ⚡**

Quick Sort is like a wizard who can sort items with incredible speed. It's known for its efficiency and adaptability.

### **The Concept 🧙**

The "divide & conquer" technique is also used by Quick Sort, however it takes a different approach. In order to divide the remaining components into two sub-arrays based on whether they are less than or greater than the pivot, it chooses one member from the array to serve as the "pivot" element. Recursively sorting is done after the sub-arrays. Till the full array is sorted, this procedure keeps on.

Principal Methods selecting a pivot Out of the array, pick a pivot point.

### **Key Techniques 🪄**

1. **Choose a Pivot**: Select a pivot element from the array (various strategies are available).
    
2. **Partitioning**: Rearrange the elements in the array so that all elements less than the pivot are on the left, and those greater are on the right.
    
3. **Recursion**: Recursively apply Quick Sort to the sub-arrays.
    

## Merge Sort 🌊

Imagine you have a deck of cards, and you want to arrange them in ascending order. What would you do? One way is to use **Merge Sort**, a remarkable algorithm that's both efficient and intuitive.

### Merge Sort: The Basics 🧐

Merge Sort is like organizing your cards by dividing them into smaller piles, sorting each pile, and then merging them back together. This divide-and-conquer approach makes it one of the most elegant sorting algorithms out there.

Here's how it works in a nutshell:

1. **Divide**: Break the array into two halves.
    
2. **Conquer**: Recursively sort each half.
    
3. **Merge**: Merge the sorted halves to create a fully sorted array.
    

```cpp
// C++ program to implement Merge Sort:
#include <iostream>
using namespace std;

void merge(int arr[], int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;

    int leftArr[n1], rightArr[n2];

    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArr[j] = arr[middle + 1 + j];
    }

    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++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;

        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);

        merge(arr, left, middle, right);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arrSize = sizeof(arr) / sizeof(arr[0]);

    cout << "Unsorted array: ";
    for (int i = 0; i < arrSize; i++) {
        cout << arr[i] << " ";
    }

    mergeSort(arr, 0, arrSize - 1);

    cout << "\nSorted array: ";
    for (int i = 0; i < arrSize; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}
```

Merge Sort's time complexity is a consistent O(n log n), making it an efficient choice for sorting large datasets. Plus, it's a fantastic example of the elegance of recursive algorithms.

## Now, Quick Sort: Swift and Efficient ⚡

Next on our agenda is **Quick Sort**, another brilliant sorting algorithm. Think of it as the speedster of the sorting world.

### Quick Sort: The Fast Track 🚀

Quick Sort works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Here's a quick overview:

1. **Choose a Pivot**: Select an element from the array as the pivot (can be done in various ways).
    
2. **Partitioning**: Rearrange the array so that all elements less than the pivot are on the left, and those greater are on the right.
    
3. **Recursion**: Recursively apply Quick Sort to the sub-arrays.
    

```cpp
// C++ program to implement Quick Sort
#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            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 arrSize = sizeof(arr) / sizeof(arr[0]);

    cout << "Unsorted array: ";
    for (int i = 0; i < arrSize; i++) {
        cout << arr[i] << " ";
    }

    quickSort(arr, 0, arrSize - 1);

    cout << "\nSorted array: ";
    for (int i = 0; i < arrSize; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}
```

Quick Sort's average-case time complexity is O(n log n), making it highly efficient. It's often preferred when a balance between simplicity and performance is needed.

## Why These Sorting Algorithms Matter 🤔

Knowing Efficiency: These methods offer important insights towards writing efficient code. When working with massive datasets, efficiency is crucial.

Your ability to solve problems will improve as a result of learning these concepts. By reducing big problems down into smaller, more manageable steps, you'll learn how to approach them.

Success in the Interview: Sorting algorithm-related interview questions are frequently asked in the computer industry. Your advantage will increase if you are familiar with these algorithms.

Versatility: These algorithms aren't only for sorting; they're fundamental methods utilized in everything from databases to artificial intelligence.

## **When to Use Merge Sort and Quick Sort 🤔**

* **Merge Sort**: This algorithm shines when stability (maintaining the order of equal elements) is a concern. It's a reliable choice for sorting linked lists. Merge Sort's consistent time complexity of O(n log n) makes it suitable for large datasets.
    
* **Quick Sort**: When you need a faster, in-place sorting algorithm, Quick Sort is your go-to. It has an average-case time complexity of O(n log n) and can outperform other algorithms in practice. However, it's not stable and may require additional memory.
    

## Keep the Flame of Curiosity Burning! 🔥

I want to encourage you to continue exploring these ideas as we come to the end of this section of our journey. Coding is a talent that is always changing and an experience. Every line of code you create advances your coding journey. 🚶‍♂️

The way you handle information will be revolutionized by the data structures we explore in our upcoming session as we go deeper into the most fascinating facets of DSA. Prepare for some data magic.

Happy programming until then!💻🌟