Cod sursa(job #2238833)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 septembrie 2018 21:07:06
Problema Sortare prin comparare Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.18 kb
import static java.lang.Character.isDigit;
import static java.util.Arrays.copyOf;
import static java.util.Arrays.copyOfRange;
import static java.util.Objects.requireNonNull;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.DataInputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Scanner;
import java.util.StringTokenizer;

public final class Main {
  public static final String IN_FILE = "algsort.in";
  public static final String OUT_FILE = "algsort.out";

  public final static class FastScanner implements AutoCloseable {
    private static final int BUFFER_SIZE = 1 << 16;

    private final DataInputStream stream;
    private final byte[] buffer = new byte[BUFFER_SIZE];
    private int bufferPointer = 0;
    private int bytesRead = 0;

    public FastScanner(final String fileName) throws IOException {
      stream = new DataInputStream(new FileInputStream(fileName));
    }

    public int nextInt() throws IOException {
      byte c;
      do {
        c = read();
      } while (c != '-' && !isDigit(c));
      final boolean isNegative = c == '-';
      if (isNegative) {
        c = read();
      }
      int value = 0;
      do {
        value = value * 10 + (c - '0');
        c = read();
      } while (isDigit(c));
      return isNegative ? -value : value;
    }

    private byte read() throws IOException {
      final byte c = read();
      if (c == -1) {
        throw new IOException("Reached end of stream!");
      }
      return c;
    }

    private byte tryRead() throws IOException {
      if (bufferPointer == bytesRead) {
        bufferPointer = 0;
        bytesRead = stream.read(buffer, 0, BUFFER_SIZE);
        if (bytesRead == -1) {
          bytesRead = 0;
          return -1;
        }
      }
      return buffer[bufferPointer++];
    }

    @Override
    public void close() throws IOException {
      stream.close();
    }
  }

  private static int[] merge(final int[] left, final int[] right) {
    final int m = left.length;
    final int n = right.length;
    final int[] result = new int[m + n];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < m || j < n) {
      if (i < m && (j == n || left[i] <= right[j])) {
        result[k++] = left[i++];
      } else {
        result[k++] = right[j++];
      }
    }
    return result;
  }

  private static final Random randomGen = new Random();

  private static int random(final int lower, final int upper) {
    return lower + randomGen.nextInt(upper - lower + 1);
  }

  private static void swap(final int[] values, final int i, final int j) {
    final int aux = values[i];
    values[i] = values[j];
    values[j] = aux;
  }

  private static int partition(
      final int[] values, final int from, final int to) {
    final int pivot = values[random(from, to)];
    int i = from - 1;
    int j = to + 1;
    while (true) {
      for (i++; values[i] < pivot; i++);
      for (j--; values[j] > pivot; j--);
      if (i >= j) {
        return j;
      }
      swap(values, i, j);
    }
  }

  private static void quickSort(
      final int[] values, final int from, final int to) {
    if (from >= to) {
      return;
    }
    final int split = partition(values, from, to);
    quickSort(values, from, split);
    quickSort(values, split + 1, to);
  }

  public static void quickSort(final int[] values) {
    quickSort(values, 0, values.length - 1);

  }

  public static int[] readValues(final FastScanner scanner) throws IOException {
    final int n = scanner.nextInt();
    final int[] values = new int[n];
    for (int i = 0; i < n; i++) {
      values[i] = scanner.nextInt();
    }
    return values;
  }

  public static void writeValues(final PrintWriter writer, final int[] values) {
    for (int i = 0; i < values.length; i++) {
      writer.print(values[i]);
      writer.print(i + 1 < values.length ? ' ' : '\n');
    }
  }

  public static void main(final String[] args) throws IOException {
    try (final FastScanner scanner = new FastScanner(IN_FILE);
        final PrintWriter writer = new PrintWriter(OUT_FILE)) {
      final int[] values = readValues(scanner);
      quickSort(values);
      writeValues(writer, values);
    }
  }
}