Cod sursa(job #2443581)

Utilizator gicugAndrei gicug Data 28 iulie 2019 17:05:57
Problema Sortare prin comparare Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <memory>
#include <cstdint>
#include <utility>

using Array = std::unique_ptr<uint32_t[]>;
using index_t = int;

void swap(const Array& a, index_t p1, index_t p2) {
  uint32_t aux = a[p1];
  a[p1] = a[p2];
  a[p2] = aux;
}

index_t partition(const Array& a, index_t lo, index_t hi) {
  const uint32_t pivot = a[hi];
  index_t i = lo;


  for (index_t j = lo; j < hi; ++j) {
    if (a[j] < pivot) {
      swap(a, i, j);
      i++;
    }
  }

  swap(a, i, hi);
  return i;
}

void quicksort(const Array& a, index_t lo, index_t hi) {
  if (lo > hi) {
    return;
  }
  index_t p = partition(a, lo, hi);
  quicksort(a, lo, p - 1);
  quicksort(a, p + 1, hi);
}

std::pair<Array, index_t> read() {
  std::ifstream fin("algsort.in");
  index_t n;
  fin >> n;
  Array a = std::make_unique(size_t(n));
  for (index_t i; i < n; ++i) {
    fin >> a[i];
  }
  return std::make_pair(std::move(a), n);
}

void print(const Array& a, index_t n) {
  std::ofstream fout("algsort.out");
  for (index_t i = 0; i < n; ++i) {
    fout << a[i] << " ";
  }
  fout << std::endl;
}

int main() {
  auto a = read();
  quicksort(a.first, 0, a.second - 1);
  print(a.first, a.second);
  return 0;
}