// QuickSort.java	クイックソート quicksort
//								2019.06.14
//								2002.05.30
//								2002.05.23
//								by M.Yanaka

import java.util.*;

public class QuickSort {
  public static final int N = 100;
  public static void main(String[] args) {
    int[] x = new int[N];	// N個の int の配列 x を宣言
    int n;			// データ数
    int w;			// データ交換のための作業用

    Scanner sc = new Scanner(System.in);
    System.out.print("デ−タ数を入力して下さい（ただし，100以下）: ");
    n = sc.nextInt();
    System.out.println("整数デ−タを，" + n + " 個だけ入力して下さい");
    for (int i = 0; i < n; ++i) {
	System.out.print("No." + (i + 1) + " = ");
	x[i] = sc.nextInt();
    }

    System.out.println("入力データ" + n);
    for (int i = 0; i < n; i++) {
      System.out.println(x[i]);
    }

    quick_sort(x, 0, n-1);	
    System.out.println("小さい順に並べ換えました");
    for (int i = 0; i < n; i++) {
      System.out.println(x[i]);
    }
  }

  public static void quick_sort(int x[], int left, int right) {	/* クイックソ−ト */
    int     p1 = left, p2 = right, w;
    int     y = x[(left + right) / 2];
    do {                            /* ル−プを作る繰返し文：do while 文 */
        while (x[p1] < y) p1++;
        while (x[p2] > y) p2--;
        if (p1 < p2) {                  /* 要素の入替え */
            w = x[p1];
            x[p1] = x[p2];
            x[p2] = w;
        }
        if (p1 <= p2) {
            p1++; p2--;
        }
    } while (p1 <= p2);             /* 条件が成立する限り do から繰返す */
    if (left < p2)                         /* 前半再帰呼出し */
        quick_sort(x, left, p2);
    if (p1 < right)                        /* 後半再帰呼出し */
        quick_sort(x, p1, right);
  }
}