- Método de ordenação
BUBBLE
Um loop eterno. Vai trocando até acaber.
Funciona como uma bolha
Ordem N2
INSERTION
for dentro de for. No segundo for, parte do elemento definido no for anterior e vai voltando até o início tentando trocar.
N2.
//Algorithm
1: for(j = 1; j < length; j++) // Note!
2: {
3: keyelement = array[j];
4: for (i = j - 1; (i >= 0) && (array[i] < keyelement); i--)
5: {
6: array[i+1] = array[i];
7: }
8: array[i+1] = keyelement;
9: }
for dentro de for, em cada passada, escolhe o menor e troca no final do loop
//Algorithm
1: for (i= length - 1; i > 0; i--)
2: {
3: firstelement = 0;
4: for (j=1; j<=i; j++)
5: {
6: if (array[j] < array[firstelement])
7: firstelement = j;
8: }
9: temp = array[firstelement];
10: array[firstelement] = array[i];
11: array[i] = temp;
12: }
Generaliza o insert sort. Permite que itemns longe sejam trocado.
Começa com ordenamentos entre elementos em distancia = N/2 .
Enquanto tiver troca continua.
Depois faz o mesmo para o distancia = distancia/2.
Repete até distancia < 1; //Algorithm
1: d = length;
2: flag = 1;
3: while ( flag || (d > 1))
4: {
5: flag = 0;
6: d = (d + 1)/2;
7: for (i =0; i < (length - d); i++)
8: {
9: if (array[i + d] > array[i])
10: {
11: tmp = array[i+d];
12: array[i + d] = array[i];
13: array[i] = tmp;
14: flag = 1;
15: }
16: }
17: }
Algorithm of Divide and conquer. Lista dividida em 2, depois essa é dividida em dois.
Faz o mesmo para a direita e pra esquerda. Depois faz o merge.
No merge criar um helper com os valores do vetor e tem-se low, middle e high. Percorre-se enquanto i<=middle e j<=high. Se o valor o i < valor do helper[j], copia v[i] e i++, senão v[j] e j++. Copia o resto do do helper para o v
1: private void mergesort(int low, int high) {
2: // Check if low is smaller then high, if not then the array is sorted
3: if (low < high) {
4: // Get the index of the element which is in the middle
5: int middle = low + (high - low) / 2;
6: // Sort the left side of the array
7: mergesort(low, middle);
8: // Sort the right side of the array
9: mergesort(middle + 1, high);
10: // Combine them both
11: merge(low, middle, high);
12: }
13: }
14: private void merge(int low, int middle, int high) {
15: // Copy both parts into the helper array
16: for (int i = low; i <= high; i++) {
17: helper[i] = numbers[i];
18: }
19: int i = low;
20: int j = middle + 1;
21: int k = low;
22: // Copy the smallest values from either the left or the right side back
23: // to the original array
24: while (i <= middle && j <= high) {
25: if (helper[i] <= helper[j]) {
26: numbers[k] = helper[i];
27: i++;
28: } else {
29: numbers[k] = helper[j];
30: j++;
31: }
32: k++;
33: }
34: // Copy the rest of the left side of the array into the target array
35: while (i <= middle) {
36: numbers[k] = helper[i];
37: k++;
38: i++;
39: }
40: }
QUICK SORT
http://www.youtube.com/watch?v=gu7x-jgzuOU
Método de dividir e conquistar. Escolhe o pivo e ordena de acordo com ele.
escolhe um pivot, no N/2.
Depois divide em duas listas. E joga os maiores a direita do pivo e os menores a esquerda através das trocas sucessivas.
i=low, j=high. Faz o mesmo à direita e a esquerda.
1: private void quicksort(int low, int high) {
2: int i = low, j = high;
3: // Get the pivot element from the middle of the list
4: int pivot = numbers[low + (high-low)/2];
5: // Divide into two lists
6: while (i <= j) {
7: // If the current value from the left list is smaller then the pivot
8: // element then get the next element from the left list
9: while (numbers[i] < pivot) {
10: i++;
11: }
12: // If the current value from the right list is larger then the pivot
13: // element then get the next element from the right list
14: while (numbers[j] > pivot) {
15: j--;
16: }
17: // If we have found a values in the left list which is larger then
18: // the pivot element and if we have found a value in the right list
19: // which is smaller then the pivot element then we exchange the
20: // values.
21: // As we are done we can increase i and j
22: if (i <= j) {
23: exchange(i, j);
24: i++;
25: j--;
26: }
27: }
28: // Recursion
29: if (low < j)
30: quicksort(low, j);
31: if (i < high)
32: quicksort(i, high);
33: }
HEAP (nLogn) com pior = caso médio
Cria-se uma arvore heap na ordem da lista que vira uma árvore balanceada.
Ordena: Troca os valores das sub-arvores com os elementos acima, caso o valor seja maior recursivamente até chegar à raiz.
Envia esse valor pro vetor. Como a raiz ficará vazia, pegue qualquer elemento folha e jogue pra raíz.
A ideia é dos menores valores irem sendo jogados para a raiz.
http://sciencetechpedia.blogspot.com.au/2012/11/heap-sort-using-java.html
Nenhum comentário:
Postar um comentário