Quick Sort

quickSort1.java//////////////////////////////////////////////////////////////// class QuickSort1App { public static void main(String[] args) { int maxSize = 16; // tamanho do vetor ArrayIns arr; arr = new ArrayIns(maxSize); // cria vetor for(int j=0; j<maxSize; j++) // constrói o vetor com { // números randomicos long n = (int)(java.lang.Math.random()*99); arr.insere(n); } arr.imprime(); // imprime itens arr.quickSort(); // chama quicksort arr.imprime(); // imprime itens novamente } // fim main() } // fim classe QuickSort1App ////////////////////////////////////////////////////////////////

// demonstração da versão simples do quicksort //////////////////////////////////////////////////////////////// class ArrayIns { private long[] Vetor; // referência para Vetor private int nElems; // número de itens //-------------------------------------------------------------public ArrayIns(int max) // construtor { Vetor = new long[max]; // cria o vetor nElems = 0; } //-------------------------------------------------------------public void insere(long valor) //insere elementos novetor { Vetor[nElems] = valor; // insere valor nElems++; // incrementa tamanho } //-------------------------------------------------------------public void imprime() // imprime conteúdo do vetor { System.out.print("A="); for(int j=0; j
public int particaoIt(int esq, int dir, long pivo) { int esqPtr = esq-1; // antes de esq int dirPtr = dir; // dir-1 while(true) { // encontra maior item while( Vetor[++esqPtr] < pivo ) ; // nenhuma operação // encontra menor item while(dirPtr > 0 && Vetor[--dirPtr] > pivo) ; // nenhuma operação if(esqPtr >= dirPtr) // se ponteiros se cruzam, break; // partição feita else // não cruza, então troca(esqPtr, dirPtr); // troca elementos } // fim while(true) troca(esqPtr, dir); // muda lugar do pivô return esqPtr; // return localização do pivô } // fim particaoIt() //-------------------------------------------------------------public void troca(int dex1, int dex2) // troca dois elementos { long temp = Vetor[dex1]; // A em temp Vetor[dex1] = Vetor[dex2]; // B em A Vetor[dex2] = temp; // temp em B } // fim troca( //-------------------------------------------------------------} // fim classe ArrayIns