Sort First Half in Ascending Order and Second Half in Descending

Understanding Sorting Strategy

This task involves sorting the first half of an array in ascending order and the second half in descending order.

We will explore three different methods to achieve this in C++.

Method 1: Using Built-in Sorting

This method splits the array and sorts each part separately.

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

void sortHalf(int arr[], int n) {
    int mid = n / 2;
    sort(arr, arr + mid);
    sort(arr + mid, arr + n, greater());
}

int main() {
    int arr[] = {7, 2, 5, 3, 9, 8, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    sortHalf(arr, n);
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
            

Method 2: Using Bubble Sort

This method implements sorting manually using bubble sort.

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int start, int end, bool ascending) {
    for (int i = start; i < end - 1; i++) {
        for (int j = start; j < end - 1 - (i - start); j++) {
            if ((ascending && arr[j] > arr[j + 1]) || (!ascending && arr[j] < arr[j + 1])) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

void sortHalf(int arr[], int n) {
    int mid = n / 2;
    bubbleSort(arr, 0, mid, true);
    bubbleSort(arr, mid, n, false);
}

int main() {
    int arr[] = {7, 2, 5, 3, 9, 8, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    sortHalf(arr, n);
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}
            

Method 3: Using Insertion Sort

This method sorts both halves separately using insertion sort.

#include <iostream>
using namespace std;

void insertionSort(int arr[], int start, int end, bool ascending) {
    for (int i = start + 1; i < end; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= start && ((ascending && arr[j] > key) || (!ascending && arr[j] < key))) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void sortHalf(int arr[], int n) {
    int mid = n / 2;
    insertionSort(arr, 0, mid, true);
    insertionSort(arr, mid, n, false);
}

int main() {
    int arr[] = {7, 2, 5, 3, 9, 8, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    sortHalf(arr, n);
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}