SHARE
TWEET

QuickSort

a guest Apr 26th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package Sort;
  2.  
  3. import java.util.Scanner;
  4.  
  5. public class QuickSort {
  6.     public static void main(String[] args) {
  7.         Scanner in = new Scanner(System.in);
  8.         int[] arr = new int[in.nextInt()];
  9.         for (int i = 0; i < arr.length; i++) {
  10.             arr[i] = in.nextInt();
  11.         }
  12.         quickSort(arr, 0, arr.length);
  13.         for (int i = 0; i < arr.length; ++i) {
  14.             System.out.print(arr[i] + " ");
  15.         }
  16.         System.out.println();
  17.     }
  18.  
  19.     static int partition(int[] arr, int low, int high) {
  20.         //Para comparar, iguala o pivot a posição inicial do array atual.
  21.         int pivot = arr[low];
  22.         /*
  23.         Faz com que tudo comece pelo lugar inicial do arr e
  24.         pelo lugar final do arr.
  25.         */
  26.         int i = low-1, j = high+1;
  27.         //Continua indeterminadamente.
  28.         while (true) {
  29.             //Procura o primeiro item maior ou igual ao pivot.
  30.             //Este começa do inicio e vêm.
  31.             do {
  32.                 i++;
  33.             } while (arr[i] < pivot);
  34.             //Procura o primeiro item menor ou igual que o pivot.
  35.             //Este começa do final e volta.
  36.             do {
  37.                 j--;
  38.             } while (arr[j] > pivot);
  39.             /*
  40.             retorna o J que conterá o pivot que deverá ser tomado como
  41.             ponto de onde continuaremos.
  42.             */
  43.             if (i >= j) {
  44.                 return j;
  45.             }
  46.             /*
  47.                 Caso não tenha encontrado um pivot novo para ser retornado,
  48.                 fazemos o swap do primeiro item maior que o pivot pela esquerda
  49.                 e o menor item que o pivot pela direita.
  50.             */
  51.             int aux = arr[i];
  52.             arr[i] = arr[j];
  53.             arr[j] = aux;
  54.         }
  55.     }
  56.  
  57.     static  void quickSort(int[] arr, int low, int high){
  58.         /*
  59.             Compara o low atual com o high, se o low for igual ao high significa
  60.             que o trecho analisado do array é atômico e por isso não precisa continuar.
  61.         */
  62.         if(low<high){
  63.             //Descobre onde ficará o novo pivot.
  64.             int pivot = partition(arr, low, high);
  65.             //Faz o sort do que está a esquerda do pivot atual.
  66.             quickSort(arr, low, pivot-1);
  67.             //Faz o sort do que está a direita do pivot atual.
  68.             quickSort(arr, pivot+1, high);
  69.         }
  70.     }
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top