Interative QuickSort

Prévia do material em texto

Interative QuickSort
package br.edu.uni7.pod.sorting;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
public class InteractiveQuick <T, C extends Comparator<T>> implements Sorter<T, C>{
	public void sort(T[] items, C comparator) {
		helper(items, comparator, 0, items.length - 1);
	}
	private void helper(T[] items, C comparator, int fisrt, int last) {
	 Deque<Integer[]> stack = new ArrayDeque<Integer[]>();
	 
 	stack.push(new Integer[] {fisrt, last});
	 
		while (!stack.isEmpty()) {
			sortStep(items, stack, comparator);
		}
	}
	
	private void sortStep(T[] vect, Deque<Integer[]> stack, C comparator) {
	 // initialize indices
	 Integer[] temp = stack.pop();
		Integer first = temp[0];
	 Integer last = temp[1];
	 Integer boundLo = first;
	 Integer boundHi = last;
	 Integer pivot = first;
	 pivot = partition(vect, comparator, first, last);
	 if(boundLo < (pivot - 1)) 
	 stack.add(new Integer[] {boundLo, pivot - 1});
	 if(boundHi > (pivot + 1)) 
	 stack.add(new Integer[] {pivot + 1, boundHi});
	}
	private int partition(T[] items, C comparator, int first, int last) {
		T pivot = items[first];
		int leftMark = first + 1;
		int rightMark = last;
		boolean done = false;
		while (!done) {
			// items[leftMark] <= pivot
			while (leftMark <= rightMark && 
					comparator.compare(items[leftMark], pivot) <= 0) {
				leftMark = leftMark + 1;
			}
			while (comparator.compare(pivot, items[rightMark]) <= 0 && 
					(rightMark >= leftMark)) {
				rightMark = rightMark - 1;
			}
			if (rightMark < leftMark) {
				done = true;
			} else {
				T temp = items[leftMark];
				items[leftMark] = items[rightMark];
				items[rightMark] = temp;
			}
		}
		
		T aux = items[first];
		items[first] = items[rightMark];
		items[rightMark] = aux;
		return rightMark;
	}
}
RESULTADOS
A partir de 15 iterações o código recursivo quebra por StackOverflow:
Rodamos o QuickSort e o InterativeQuickSort para comparamos as performances nos 3 cenários, melhor cenário, cenário médio e pior cenário.
· Melhor cenário:
· Cenário médio:
· Pior cenário: 
Deixamos o programa rondando durante mais ou menos 1 hora no melhor cenário e com 21 iterações ele não tinha quebrado.
CONCLUSÃO
Depois dos testes feitos podemos concluir que ambos os algoritmos são muito parecidos no desempenho, onde somente em um cenário o InterativeQuickSort leva desvantagem.
 No cenário médio é onde a maior diferença de desempenho e o QuickSort acaba levando uma vantagem significante, sendo assim é recomendado usá-lo nesse cenário.
 No melhor cenário, a diferença diminui bastante comparado com o cenário médio, o InterativeQuickSort acaba usando um tempo maior para a ordenação de dados, mas ainda sim podendo ser usado sim no lugar de outros algoritmos. 
No pior caso o desempenho é praticamente igual, fazendo com que não faça muito diferença na hora de usar ou o QuickSort ou InterativeQuickSort.