Sort Array - C++ Solution

1. Introduction

This blog post focuses on a fundamental problem in array manipulation: sorting an integer array in-place without using any inbuilt functions. This problem is pivotal in understanding sorting algorithms, specifically Quick Sort in C++.

Problem

Given an integer array, the task is to sort it in ascending order. The sorting should be done in-place and without using any built-in sorting functions.

Examples:

- Input: [6, 3, 4, 8, 2, 9]

Output: [2, 3, 4, 6, 8, 9]

- Input: [9, -3, 5, -2, -8, -6]

Output: [-8, -6, -3, -2, 5, 9]

2. Solution Steps

1. Implement the Quick Sort algorithm:

a. Choose a pivot element from the array.

b. Partition the array into two parts such that elements less than the pivot are on the left, and elements greater are on the right.

c. Recursively apply the same logic to the left and right subarrays.

2. Apply Quick Sort to the entire array.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to swap elements
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// Partition function for Quick Sort
int partition(vector<int>& nums, int low, int high) {
    int pivot = nums[high]; // Choose the last element as pivot
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        // If current element is smaller than the pivot
        if (nums[j] < pivot) {
            i++; // Increment index of smaller element
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i + 1], nums[high]);
    return (i + 1);
}

// Quick Sort function
void quickSort(vector<int>& nums, int low, int high) {
    if (low < high) {
        int pi = partition(nums, low, high);

        quickSort(nums, low, pi - 1);  // Before pi
        quickSort(nums, pi + 1, high); // After pi
    }
}

int main() {
    vector<int> nums = {6, 3, 4, 8, 2, 9};
    quickSort(nums, 0, nums.size() - 1);

    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

Output:

2 3 4 6 8 9

Explanation:

The quickSort function sorts an array using the Quick Sort algorithm. It selects a pivot element and partitions the array around the pivot, then recursively sorts the subarrays. This function, along with the partition function, sorts the entire array in-place. As demonstrated in the output, the input arrays are sorted in ascending order, showcasing the effective implementation of Quick Sort without using any in-built sort functions.