クイックソート

#include <bits/stdc++.h>
using namespace std;

int partition(int arr[], int beg, int end) {
  // Select the last element as pivot element
  int pivot = arr[end];
  int i = (beg - 1);
  // Move smaller elements to left side and larger on right side
  for (int j = beg; j < end; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1],
       arr[end]);  // Move pivot element to its right position in array
  return (i + 1);
}

void quickSort(int arr[], int beg, int end) {
  if (beg < end) {
    int pi = partition(arr, beg, end);
    quickSort(arr, beg,
              pi - 1);  // Recursive Sort element on left side of partition
    quickSort(arr, pi + 1,
              end);  // Recursive Sort element on right side of partition
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  quickSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

 T(n) = T(k) + T(n-k-1) + θ(n)

T(n) = T(n-1) + θ(n)

 T(n) = 2T(n/2) + θ(n)