import java.io.File;
import java.io.FileWriter;
import java.util.Scanner;

public class QuickSort {

    public static void swap(int[] nums, int index1, int index2)
    {
        int aux = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = aux;
    }
    public static int partition(int[] nums, int left, int right) {

        int pivot = nums[right];
        int correct_pivot_index = left;

        for(int j = left; j <= right - 1; j++) {
            if (nums[j] < pivot) {
                correct_pivot_index++;
                swap(nums, correct_pivot_index-1, j);
            }
        }
        swap(nums, correct_pivot_index, right);
        return correct_pivot_index;
    }
    public static void quickSort(int[] nums, int left, int right)
    {
        if(left < right) {
            int pivot_index = partition(nums, left, right);

            quickSort(nums, left, pivot_index - 1);
            quickSort(nums, pivot_index + 1, right);
        }
    }
    public static void main(String[] args) {
        try {
            File file = new File("src\\algsort.in");
            Scanner sc = new Scanner(file);
            int len = sc.nextInt();
            int[] nums = new int[len];
            for (int i = 0; i < len; i++)
            {
                nums[i] = sc.nextInt();
               System.out.print(nums[i] + " ");
            }
            System.out.println();

            quickSort(nums, 0, len-1);

            for (int i = 0; i < len; i++)
            {
                System.out.print(nums[i] + " ");
            }
            System.out.println();

            try
            {
                FileWriter fileWriter = new FileWriter("src\\algsort.out");
                for(int i=0; i < nums.length; i++)
                    fileWriter.write(nums[i] + " ");
                fileWriter.close();

            }
            catch(Exception e)
            {
                System.out.println("Eroare" + e);
            }

        }
        catch(Exception e)
        {
            System.out.println("Eroare" + e);
        }

    }

}