Método QuickSort

Sr. Jericho, você não quer dividir seu problema em pedaços primeiro?
(O famoso método “Jack o Estripador” - a vida é mais simples se dividi-la em pedaços)

A pior maneira de atacar seu problema é ficar com ele em cima da mesa.

Escreva o que deve ser feito no papel primeiro (ok, se você não tem lápis e papel, serve o Bloco de Notas mesmo).

Divida seu problema em pedaços. Por exemplo, olhando seu problema, há vários pedaços nele:

a) Como criar um array de 10000 posições
b) Como gerar 10000 números aleatórios e colocá-los em um array
c) Como medir o tempo de execução de um método
d) Como ordenar um array com o algoritmo 1 e totalizar a quantidade de trocas no algoritmo 1
e) Como ordenar um array com o algoritmo 2 e totalizar a quantidade de trocas no algoritmo 2
f) Como ordenar um array com o algoritmo 3 e totalizar a quantidade de trocas no algoritmo 3
g) Como ordenar um array com o algoritmo 4 e totalizar a quantidade de trocas no algoritmo 4
h) Como gerar 10000 números sequenciais e colocá-los em um array

Transforme cada coisa em um método e boa sorte!

A propósito, para esses algoritmos propostos existem várias implementações na Internet.
Não acho que seu professor vai querer que você não “copie” o código já existente; se eu fosse seu professor, desejaria que você pegasse o código da Internet e conseguisse mudá-lo para que continuasse correto (ou seja, ordenasse os números) e fizesse também o que é necessário (no seu caso, totalizar a quantidade de trocas, que é uma coisa que vai sendo feita dentro do algoritmo).

Assim eu esqueci de citar os 4 algoritmos!!! É o Bubble Sort, Select Sort, Insert Sort e QuickSort.

Como fazer?

@entanglement muito obrigado pela dica!!

Me ajuda aí pessoal, por favor? Por enquanto só tive duas aulas de estrutruras de dados... como estou indo? Não estou conseguindo pensar em muita coisa :/

// a) Como criar um array de 10000 posições 

public class QuickSort {

    static void Vector(int n) {
        n = 10000;
        int array[] = new int[n];
    }
    // b) Como gerar 10000 números aleatórios e colocá-los em um array 

    static void numerosAleatorios() {

        int i = (int) (1 + Math.random() * 10000);

    }
    // c) Como medir o tempo de execução de um método 

    static void tempoExecucao() {
        long inicio = System.currentTimeMillis();
        long fim = System.currentTimeMillis() - inicio;


    }

    // d) Como ordenar um array com o algoritmo 1 e totalizar a quantidade de trocas no algoritmo 1 
    static void quickSort(int vetor[]) {
        quickSort(vetor, 0, vetor.length - 1);
    }

    static void quickSort(int vetor[], int i, int s) {
        int e = i, d = s;
        int item = vetor[((e + d) / 2)];
        while (e <= d) {
            while (vetor[e] < item) {
                e++;
            }
            while (vetor[e] < item) {
                d++;
            }
            if (e <= d) {
                int aux; //Variável auxlixar para as trocas
                aux = vetor[e];
                vetor[e] = vetor[d];
                vetor[d] = aux;
                d--;
                e++;
            }
        }
        if (d - i > 0) {
            quickSort(vetor, i, d);
        }
        if (s - e > 0) {
            quickSort(vetor, e, s);
        }
    }
}

Agora entendi. Vou tentar fazer, mais tarde posto o meu código aqui.

Sim, já tive aulas de POO.

No exercício são citados 4 algorítmos, mas sua dúvida está focada apenas no Quicksort, é isso?
No próprio Wikipedia tem o exemplo de código então poderia ser mais claro na sua dúvida? Onde está o problema em si?

Jericho:

Assim eu esqueci de citar os 4 algoritmos!!! É o Bubble Sort, Select Sort, Insert Sort e QuickSort.

Blz! Agora entendi o que você quer!

A resposta do @entanglement é uma boa proposta de como fazer.

Após isso, coloque aqui o que você fez (especialmente se não estiver funcionando) para que possamos tirar suas dúvidas em relação ao que está errado.

Esse deveria ser um exercício básico de algorítmos mas não necessariamente trivial, porém é onde você pode perceber sua própria lógica evoluindo, nem que seja a capacidade de pegar algo pronto na internet e utilizá-lo em sua necessidade.

Sinceramente, o máximo que faria por você, com o que você já postou é:

public class Homework { public static void main(String args[]) { //seu codigo começa aqui. }
}

Um monte de métodos estáticos soltos como você fez não resolvem seu problema. Apenas “colocam seus problemas num único saco”.

Salvo o método Quicksort, todos os demais poderiam ser aglomerados no método main. O método tempoDeExecucao não faz nada de útil pois cada uma de suas chamadas deveriam “envolver” a chamada do método quicksort()

long inicio = System.currentTimeMillis(); quickSort(vetor, i, s); long fim = System.currentTimeMillis(); System.out.println("Tempo de execucao: " + (fim - inicio) + "ms");

o método vector() ou não precisa de parâmetro ou necessita de um teste:

static void vector() { int array[] = new int[10000]; }
ou static void vector(int n) { if(n <= 0) n = 10000; int array[] = new int[n]; }

Porém, em ambos os casos, o array é inútil pois está no escopo do método e, ao terminar o escopo, esse array criado é perdido (deixo pra vocè pensar mais um pouco aqui).

Por fim, uma dúvida: Antes dessas duas aulas de estrutura de dados, não houveram outras aulas de Java?