Insert Sort ou Método de Inserção
Por: Bruno Oliveira • 19/11/2018 • Trabalho acadêmico • 1.577 Palavras (7 Páginas) • 260 Visualizações
Insert Sort ou Método de Inserção
O método de Inserção é eficiente se aplicado a um número pequeno de elementos, devido o método ter de percorrer todo o vetor de elementos da esquerda para a direita e ao mesmo tempo em que avança, vai deixando os elementos à esquerda mais ordenados. Um exemplo prático desse método é como você organiza sua mão em um jogo de pôquer. Assim sempre que recebe um valor vai se ordenando de acordo com sua faixa. (1.https://joaoschmitt.wordpress.com/2013/05/14/algoritmos-de-ordenacao-em-java/).
Exemplo gráfico do Insert Sort:
V | 15 | 139 | 12 | 8 | 22 | 1 | |
| ↑ |
|
|
|
|
| |
| 15 |
|
|
|
|
| |
|
|
|
|
|
|
| |
| 15 | 139 |
|
|
|
| |
| [pic 1][pic 2]
|
|
|
|
|
| |
| 12 | 15 | 139 |
|
|
| |
| [pic 3][pic 4][pic 5]
|
|
|
|
|
| |
| 8 | 12 | 15 | 139 |
|
| |
|
|
|
| [pic 6]
|
|
| |
| 8 | 12 | 15 | 22 | 139 |
| |
| [pic 7][pic 8][pic 9][pic 10][pic 11]
|
|
|
|
|
| |
| 1 | 8 | 12 | 15 | 22 | 139 |
Observe que a cada inserção de um novo elemento, o método vai percorrendo o vetor e alocando-o de acordo com o seu valor. O vetor será percorrido da esquerda para direita para ordenar os elementos. Em seu melhor caso será O(n) é quando o vetor está ordenado e utilizará o menor número de trocas. Seu pior caso será O(n²).quando há muitas trocas e acaba perdendo tempo e espaço na memória. (2. http://www.htmlstaff.org/ver.php?id=20863).
Bubble Sort
Bubble sort é um algoritmo de ordenação onde cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 1 será comparado com o elemento da posição 2. Caso o elemento da posição 1 for maior que o da posição 2, eles trocam de lugar e assim por diante. Por causa desse modo de execução, o vetor terá que ser percorrido quantas vezes for necessário para que se possa deixar em ordem crescente.
Exemplo de Ordenação:
8 | 18 | 5 | 14 | 1 |
1º Caso
8 | 18 | 5 | 14 | 1 |
↑ ↑
Vamos analisar se 8 > 18? Como 8 não é maior, então não fazemos a troca.
2º Caso
8 | 18 | 5 | 14 | 1 |
↑ ↑
Vamos analisar se 18>5? Como é verdadeiro neste caso vamos ter que fazer a troca deixando da seguinte maneira.
8 | 5 | 18 | 14 | 1 |
3º Caso
8 | 5 | 18 | 14 | 1 |
↑ ↑
Vamos analisar se 18>14? Verdadeiro, então fazemos a troca.
8 | 5 | 14 | 18 | 1 |
...