Slide Ordenação Algoritmos Elementares-2021 1

Ordenac¸˜ao: algoritmos elementares Estrutura de Dados — QXD0010 Prof. At´ılio Gomes Luiz gomes.atilio@ufc.br Universidade Federal do Cear´a 1º semestre/2021 Introduc¸˜ao • Colocar um vetor num´erico em ordem crescente ou decrescente ´e o primeiro passo na soluc¸˜ao de muitos problemas pr´aticos. • Um vetor pode ser ordenado de muitas maneiras diferentes: algumas elementares, outras mais sofisticadas e eficientes. • Pode-se usar basicamente duas estrat´egias para ordenar os dados: (1) inserir os dados na estrutura respeitando sua ordem. (2) a partir de um conjunto de dados j´a criado, aplicar um algoritmo para ordenar seus elementos. 2 Introduc¸˜ao • Colocar um vetor num´erico em ordem crescente ou decrescente ´e o primeiro passo na soluc¸˜ao de muitos problemas pr´aticos. • Um vetor pode ser ordenado de muitas maneiras diferentes: algumas elementares, outras mais sofisticadas e eficientes. • Pode-se usar basicamente duas estrat´egias para ordenar os dados: (1) inserir os dados na estrutura respeitando sua ordem. (2) a partir de um conjunto de dados j´a criado, aplicar um algoritmo para ordenar seus elementos. 2 Ordenac¸˜ao O problema da ordenac¸˜ao de um vetor consiste em: • rearranjar os elementos de um vetor A[0 . . . n − 1] de tal modo que ele se torne crescente, ou seja, de modo que A[0] ≤ · · · ≤ A[n − 1]. 3 7 1 6 5 2 4 0 8 9 0 1 2 3 4 5 6 7 8 9 Nos c´odigos vamos ordenar vetores de int • Mas ´e f´acil alterar para comparar double ou string • ou comparar struct por algum de seus campos ◦ O valor usado para a ordenac¸˜ao ´e a chave de ordenac¸˜ao ◦ Podemos at´e desempatar por outros campos 3 Ordenac¸˜ao O problema da ordenac¸˜ao de um vetor consiste em: • rearranjar os elementos de um vetor A[0 . . . n − 1] de tal modo que ele se torne crescente, ou seja, de modo que A[0] ≤ · · · ≤ A[n − 1]. 3 7 1 6 5 2 4 0 8 9 0 1 2 3 4 5 6 7 8 9 Nos c´odigos vamos ordenar vetores de int • Mas ´e f´acil alterar para comparar double ou string • ou comparar struct por algum de seus campos ◦ O valor usado para a ordenac¸˜ao ´e a chave de ordenac¸˜ao ◦ Podemos at´e desempatar por outros campos 3 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 8 2 7 6 3 5 1 9 10 i j 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 8 2 7 6 3 5 1 9 10 i=0 j=9 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 8 2 7 6 3 5 1 9 10 i=0 j=8 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 8 2 7 6 3 5 1 9 10 i=0 j=7 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 8 2 7 6 3 1 5 9 10 i=0 j=6 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 8 2 7 6 1 3 5 9 10 i=0 j=5 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 8 2 7 1 6 3 5 9 10 i=0 j=4 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 8 2 1 7 6 3 5 9 10 i=0 j=3 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 8 1 2 7 6 3 5 9 10 i=0 j=2 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 4 1 8 2 7 6 3 5 9 10 i=0 j=1 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 4 8 2 7 6 3 5 9 10 i=1 j=9 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 4 8 2 7 6 3 5 9 10 i=1 j=8 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 4 8 2 7 6 3 5 9 10 i=1 j=7 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 4 8 2 7 6 3 5 9 10 i=1 j=6 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 4 8 2 7 3 6 5 9 10 i=1 j=5 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 4 8 2 3 7 6 5 9 10 i=1 j=4 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 4 8 2 3 7 6 5 9 10 i=1 j=3 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 4 2 8 3 7 6 5 9 10 i=1 j=2 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 4 8 3 7 6 5 9 10 i=2 j=9 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 4 8 3 7 6 5 9 10 i=2 j=8 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 4 8 3 7 6 5 9 10 i=2 j=7 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 4 8 3 7 5 6 9 10 i=2 j=6 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 4 8 3 5 7 6 9 10 i=2 j=5 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 4 8 3 5 7 6 9 10 i=2 j=4 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 4 3 8 5 7 6 9 10 i=2 j=3 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 8 5 7 6 9 10 i=3 j=9 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 8 5 7 6 9 10 i=3 j=8 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 8 5 7 6 9 10 i=3 j=7 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 8 5 6 7 9 10 i=3 j=6 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 8 5 6 7 9 10 i=3 j=5 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 8 6 7 9 10 i=3 j=4 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 8 6 7 9 10 i=4 j=9 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 8 6 7 9 10 i=4 j=8 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 8 6 7 9 10 i=4 j=7 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 8 7 9 10 i=4 j=6 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 8 7 9 10 i=4 j=5 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 8 7 9 10 i=5 j=9 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 8 7 9 10 i=5 j=8 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 8 7 9 10 i=5 j=7 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 7 8 9 10 i=5 j=6 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 7 8 9 10 i=6 j=9 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 7 8 9 10 i=6 j=8 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 7 8 9 10 i=6 j=7 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 7 8 9 10 i=7 j=9 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 7 8 9 10 i=7 j=8 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 7 8 9 10 i=8 j=9 5 BubbleSort – Ordenac¸˜ao por flutuac¸˜ao Ideia: • do fim para o comec¸o, vamos trocando pares invertidos • eventualmente, encontramos o menor elemento • ele ser´a trocado com os elementos que estiverem antes 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } 1 2 3 4 5 6 7 8 9 10 i j 5 BubbleSort — Complexidade do algoritmo 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No caso m´edio: • comparac¸˜oes: ≈ n2/2 = O(n2) • trocas: ≈ n2/2 = O(n2) No melhor caso: • comparac¸˜oes: ≈ n2 = O(n2) 6 BubbleSort — Complexidade do algoritmo 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No caso m´edio: • comparac¸˜oes: ≈ n2/2 = O(n2) • trocas: ≈ n2/2 = O(n2) No melhor caso: • comparac¸˜oes: ≈ n2 = O(n2) 6 BubbleSort — Complexidade do algoritmo 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No caso m´edio: • comparac¸˜oes: ≈ n2/2 = O(n2) • trocas: ≈ n2/2 = O(n2) No melhor caso: • comparac¸˜oes: ≈ n2 = O(n2) 6 BubbleSort — Complexidade do algoritmo 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No caso m´edio: • comparac¸˜oes: ≈ n2/2 = O(n2) • trocas: ≈ n2/2 = O(n2) No melhor caso: • comparac¸˜oes: ≈ n2 = O(n2) 6 BubbleSort — Complexidade do algoritmo 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No caso m´edio: • comparac¸˜oes: ≈ n2/2 = O(n2) • trocas: ≈ n2/2 = O(n2) No melhor caso: • comparac¸˜oes: ≈ n2 = O(n2) 6 BubbleSort — Complexidade do algoritmo 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No caso m´edio: • comparac¸˜oes: ≈ n2/2 = O(n2) • trocas: ≈ n2/2 = O(n2) No melhor caso: • comparac¸˜oes: ≈ n2 = O(n2) 6 BubbleSort — Complexidade do algoritmo 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No caso m´edio: • comparac¸˜oes: ≈ n2/2 = O(n2) • trocas: ≈ n2/2 = O(n2) No melhor caso: • comparac¸˜oes: ≈ n2 = O(n2) 6 BubbleSort — Complexidade do algoritmo 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No caso m´edio: • comparac¸˜oes: ≈ n2/2 = O(n2) • trocas: ≈ n2/2 = O(n2) No melhor caso: • comparac¸˜oes: ≈ n2 = O(n2) 6 BubbleSort — Complexidade do algoritmo 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No caso m´edio: • comparac¸˜oes: ≈ n2/2 = O(n2) • trocas: ≈ n2/2 = O(n2) No melhor caso: • comparac¸˜oes: ≈ n2 = O(n2) 6 Parando quando n˜ao h´a mais trocas Se n˜ao aconteceu nenhuma troca, podemos parar o algoritmo 1 void bubblesort_v2 (int A[], int n) { 2 bool trocou = true; 3 for (int i = 0; i < n-1 && trocou; i++){ 4 trocou = false; 5 for (int j = n-1; j > i; j--) 6 if (A[j] < A[j -1]) { 7 std :: swap(A[j],A[j -1]); 8 trocou = true; 9 } 10 } 11 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No melhor caso: • comparac¸˜oes: O(n) • trocas: O(1) 7 Parando quando n˜ao h´a mais trocas Se n˜ao aconteceu nenhuma troca, podemos parar o algoritmo 1 void bubblesort_v2 (int A[], int n) { 2 bool trocou = true; 3 for (int i = 0; i < n-1 && trocou; i++){ 4 trocou = false; 5 for (int j = n-1; j > i; j--) 6 if (A[j] < A[j -1]) { 7 std :: swap(A[j],A[j -1]); 8 trocou = true; 9 } 10 } 11 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No melhor caso: • comparac¸˜oes: O(n) • trocas: O(1) 7 Parando quando n˜ao h´a mais trocas Se n˜ao aconteceu nenhuma troca, podemos parar o algoritmo 1 void bubblesort_v2 (int A[], int n) { 2 bool trocou = true; 3 for (int i = 0; i < n-1 && trocou; i++){ 4 trocou = false; 5 for (int j = n-1; j > i; j--) 6 if (A[j] < A[j -1]) { 7 std :: swap(A[j],A[j -1]); 8 trocou = true; 9 } 10 } 11 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No melhor caso: • comparac¸˜oes: O(n) • trocas: O(1) 7 Parando quando n˜ao h´a mais trocas Se n˜ao aconteceu nenhuma troca, podemos parar o algoritmo 1 void bubblesort_v2 (int A[], int n) { 2 bool trocou = true; 3 for (int i = 0; i < n-1 && trocou; i++){ 4 trocou = false; 5 for (int j = n-1; j > i; j--) 6 if (A[j] < A[j -1]) { 7 std :: swap(A[j],A[j -1]); 8 trocou = true; 9 } 10 } 11 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No melhor caso: • comparac¸˜oes: O(n) • trocas: O(1) 7 Parando quando n˜ao h´a mais trocas Se n˜ao aconteceu nenhuma troca, podemos parar o algoritmo 1 void bubblesort_v2 (int A[], int n) { 2 bool trocou = true; 3 for (int i = 0; i < n-1 && trocou; i++){ 4 trocou = false; 5 for (int j = n-1; j > i; j--) 6 if (A[j] < A[j -1]) { 7 std :: swap(A[j],A[j -1]); 8 trocou = true; 9 } 10 } 11 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No melhor caso: • comparac¸˜oes: O(n) • trocas: O(1) 7 Parando quando n˜ao h´a mais trocas Se n˜ao aconteceu nenhuma troca, podemos parar o algoritmo 1 void bubblesort_v2 (int A[], int n) { 2 bool trocou = true; 3 for (int i = 0; i < n-1 && trocou; i++){ 4 trocou = false; 5 for (int j = n-1; j > i; j--) 6 if (A[j] < A[j -1]) { 7 std :: swap(A[j],A[j -1]); 8 trocou = true; 9 } 10 } 11 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No melhor caso: • comparac¸˜oes: O(n) • trocas: O(1) 7 Parando quando n˜ao h´a mais trocas Se n˜ao aconteceu nenhuma troca, podemos parar o algoritmo 1 void bubblesort_v2 (int A[], int n) { 2 bool trocou = true; 3 for (int i = 0; i < n-1 && trocou; i++){ 4 trocou = false; 5 for (int j = n-1; j > i; j--) 6 if (A[j] < A[j -1]) { 7 std :: swap(A[j],A[j -1]); 8 trocou = true; 9 } 10 } 11 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No melhor caso: • comparac¸˜oes: O(n) • trocas: O(1) 7 Parando quando n˜ao h´a mais trocas Se n˜ao aconteceu nenhuma troca, podemos parar o algoritmo 1 void bubblesort_v2 (int A[], int n) { 2 bool trocou = true; 3 for (int i = 0; i < n-1 && trocou; i++){ 4 trocou = false; 5 for (int j = n-1; j > i; j--) 6 if (A[j] < A[j -1]) { 7 std :: swap(A[j],A[j -1]); 8 trocou = true; 9 } 10 } 11 } No pior caso toda comparac¸˜ao gera uma troca: • comparac¸˜oes: n(n − 1)/2 = O(n2) • trocas: n(n − 1)/2 = O(n2) No melhor caso: • comparac¸˜oes: O(n) • trocas: O(1) 7 Ordenac¸˜ao por Inserc¸˜ao Ideia: • Se j´a temos v[0], v[1], . . ., v[i-1] ordenado, ent˜ao inserimos v[i] na posic¸˜ao correta ◦ Fazemos algo similar ao BubbleSort: ficamos com v[0], v[1], . . ., v[i] ordenado Retirado do livro do Cormen. 9 Ordenac¸˜ao por Inserc¸˜ao Algoritmo 1 void insertionsort (int A[], int n) { 2 int i, j, key; 3 for (j = 1; j < n; j++) { 4 key = A[j]; 5 i = j -1; 6 while(i >= 0 && A[i] > key) { 7 A[i+1] = A[i]; 8 i--; 9 } 10 A[i+1] = key; 11 } 12 } Testar com o vetor: [4, 8, 2, 7, 6, 3, 5, 1, 9, 10] 10 Ordenac¸˜ao por Inserc¸˜ao Algoritmo 1 void insertionsort (int A[], int n) { 2 int i, j, key; 3 for (j = 1; j < n; j++) { 4 key = A[j]; 5 i = j -1; 6 while(i >= 0 && A[i] > key) { 7 A[i+1] = A[i]; 8 i--; 9 } 10 A[i+1] = key; 11 } 12 } Testar com o vetor: [4, 8, 2, 7, 6, 3, 5, 1, 9, 10] 10 InsertionSort - Complexidade do algoritmo 1 void insertionsort(int A[], int n) { 2 int i, j, key; 3 for (j = 1; j < n; j++) { 4 key = A[j]; 5 i = j-1; 6 while(i >= 0 && A[i] > key) { 7 A[i+1] = A[i]; 8 i--; 9 } 10 A[i+1] = key; 11 } 12 } • O consumo de tempo do insertionSort é proporcional ao número de execuções da comparação A[i] > key. InsertionSort - Complexidade do algoritmo 1 void insertionsort(int A[], int n) { 2 int i, j, key; 3 for (j = 1; j < n; j++) { 4 key = A[j]; 5 i = j-1; 6 while(i >= 0 && A[i] > key) { 7 A[i+1] = A[i]; 8 i--; 9 } 10 A[i+1] = key; 11 } 12 } • O consumo de tempo do insertionSort é proporcional ao número de execuções da comparação A[i] > key. • Para cada j, a variável i assume no máximo j valores: j-1, j-2,...,0. InsertionSort - Complexidade do algoritmo 1 void insertionsort(int A[], int n) { 2 int i, j, key; 3 for (j = 1; j < n; j++) { 4 key = A[j]; 5 i = j-1; 6 while(i >= 0 && A[i] > key) { 7 A[i+1] = A[i]; 8 i--; 9 } 10 A[i+1] = key; 11 } 12 } • O consumo de tempo do insertionSort é proporcional ao número de execuções da comparação A[i] > key. • Para cada j, a variável i assume no máximo j valores: j-1, j-2,...,0. • Como 1 ≤ j ≤ n-1, o número de execuções da linha 6 é igual a ∑_{j=1}^{n-1} j no pior caso. InsertionSort - Complexidade do algoritmo 1 void insertionsort(int A[], int n) { 2 int i, j, key; 3 for (j = 1; j < n; j++) { 4 key = A[j]; 5 i = j-1; 6 while(i >= 0 && A[i] > key) { 7 A[i+1] = A[i]; 8 i--; 9 } 10 A[i+1] = key; 11 } 12 } • O consumo de tempo do insertionSort é proporcional ao número de execuções da comparação A[i] > key. • Para cada j, a variável i assume no máximo j valores: j - 1, j - 2, ..., 0. • Como 1 ≤ j ≤ n - 1, o número de execuções da linha 6 é igual a ∑_{j=1}^{n-1} j no pior caso. • Essa soma é igual a n(n-1)/2 = O(n²). Universidade Federal do Ceará Campus Quixadá SelectionSort Universidade Federal do Ceará Campus Quixadá Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n -1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n -1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n -1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=0 j=1 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=0 j=2 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=2 j=2 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=2 j=3 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=2 j=4 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=2 j=5 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=2 j=6 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=2 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=7 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=7 j=8 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 4 8 2 7 6 3 5 1 9 10 i=0 min=7 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=0 min=7 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=1 min=1 j=2 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=1 min=2 j=2 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=1 min=2 j=3 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=1 min=2 j=4 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=1 min=2 j=5 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=1 min=2 j=6 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=1 min=2 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=1 min=2 j=8 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 8 2 7 6 3 5 4 9 10 i=1 min=2 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=1 min=2 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=2 j=3 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=3 j=3 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=3 j=4 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=4 j=4 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=4 j=5 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=5 j=5 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=5 j=6 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=5 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=5 j=8 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 8 7 6 3 5 4 9 10 i=2 min=5 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 7 6 8 5 4 9 10 i=2 min=5 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 7 6 8 5 4 9 10 i=3 min=3 j=4 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 7 6 8 5 4 9 10 i=3 min=3 j=5 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 7 6 8 5 4 9 10 i=3 min=3 j=6 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 7 6 8 5 4 9 10 i=3 min=3 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 7 6 8 5 4 9 10 i=3 min=7 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 7 6 8 5 4 9 10 i=3 min=7 j=8 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 7 6 8 5 4 9 10 i=3 min=7 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 6 8 5 7 9 10 i=3 min=7 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 6 8 5 7 9 10 i=4 min=4 j=5 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 6 8 5 7 9 10 i=4 min=4 j=6 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 6 8 5 7 9 10 i=4 min=6 j=6 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 6 8 5 7 9 10 i=4 min=6 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 6 8 5 7 9 10 i=4 min=6 j=8 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 6 8 5 7 9 10 i=4 min=6 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 8 6 7 9 10 i=4 min=6 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 8 6 7 9 10 i=5 min=5 j=6 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 8 6 7 9 10 i=5 min=6 j=6 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 8 6 7 9 10 i=5 min=6 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 8 6 7 9 10 i=5 min=6 j=8 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 8 6 7 9 10 i=5 min=6 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 8 7 9 10 i=5 min=6 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 8 7 9 10 i=6 min=6 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 8 7 9 10 i=6 min=7 j=7 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 8 7 9 10 i=6 min=7 j=8 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 8 7 9 10 i=6 min=7 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 7 8 9 10 i=6 min=7 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 7 8 9 10 i=7 min=7 j=8 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 7 8 9 10 i=7 min=7 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 7 8 9 10 i=7 min=7 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 7 8 9 10 i=8 min=8 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 7 8 9 10 i=8 min=8 j=9 13 Ordenac¸˜ao por Selec¸˜ao Ideia: • Trocar v[0] com o m´ınimo de v[0], v[1], . . ., v[n-1] • Trocar v[1] com o m´ınimo de v[1], v[2], . . ., v[n-1] • . . . 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } 1 2 3 4 5 6 7 8 9 10 i=8 min=8 j=9 13 SelectionSort – Complexidade do algoritmo 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } • n´umero de comparac¸˜oes: (n − 1) + (n − 2) + · · · + 1 = n(n − 1)/2 = O(n2) • n´umero de trocas: n − 1 = O(n) ◦ Muito bom quando trocas s˜ao muito caras ◦ Por´em, talvez seja melhor usar ponteiros nesse caso 14 SelectionSort – Complexidade do algoritmo 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } • n´umero de comparac¸˜oes: (n − 1) + (n − 2) + · · · + 1 = n(n − 1)/2 = O(n2) • n´umero de trocas: n − 1 = O(n) ◦ Muito bom quando trocas s˜ao muito caras ◦ Por´em, talvez seja melhor usar ponteiros nesse caso 14 SelectionSort – Complexidade do algoritmo 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } • n´umero de comparac¸˜oes: (n − 1) + (n − 2) + · · · + 1 = n(n − 1)/2 = O(n2) • n´umero de trocas: n − 1 = O(n) ◦ Muito bom quando trocas s˜ao muito caras ◦ Por´em, talvez seja melhor usar ponteiros nesse caso 14 SelectionSort – Complexidade do algoritmo 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } • n´umero de comparac¸˜oes: (n − 1) + (n − 2) + · · · + 1 = n(n − 1)/2 = O(n2) • n´umero de trocas: n − 1 = O(n) ◦ Muito bom quando trocas s˜ao muito caras ◦ Por´em, talvez seja melhor usar ponteiros nesse caso 14 SelectionSort – Complexidade do algoritmo 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } • n´umero de comparac¸˜oes: (n − 1) + (n − 2) + · · · + 1 = n(n − 1)/2 = O(n2) • n´umero de trocas: n − 1 = O(n) ◦ Muito bom quando trocas s˜ao muito caras ◦ Por´em, talvez seja melhor usar ponteiros nesse caso 14 Algoritmos in Loco Universidade Federal do Ceará Campus Quixadá Algoritmos in loco • Um algoritmo in loco ´e um algoritmo que transforma a entrada sem usar estruturas de dados auxiliares. ◦ uma quantidade constante e pequena de espac¸o de armazenamento extra ´e permitida (geralmente para vari´aveis auxiliares). • A entrada ´e geralmente sobrescrita pela sa´ıda conforme o algoritmo ´e executado. O algoritmo in loco atualiza a entrada apenas por meio da substituic¸˜ao ou troca de elementos. • Pergunta: BubbleSort, Insertion-Sort e Selection-Sort s˜ao algoritmos in loco? 16 Algoritmos in loco • Um algoritmo in loco ´e um algoritmo que transforma a entrada sem usar estruturas de dados auxiliares. ◦ uma quantidade constante e pequena de espac¸o de armazenamento extra ´e permitida (geralmente para vari´aveis auxiliares). • A entrada ´e geralmente sobrescrita pela sa´ıda conforme o algoritmo ´e executado. O algoritmo in loco atualiza a entrada apenas por meio da substituic¸˜ao ou troca de elementos. • Pergunta: BubbleSort, Insertion-Sort e Selection-Sort s˜ao algoritmos in loco? 16 Algoritmos in loco • Um algoritmo in loco ´e um algoritmo que transforma a entrada sem usar estruturas de dados auxiliares. ◦ uma quantidade constante e pequena de espac¸o de armazenamento extra ´e permitida (geralmente para vari´aveis auxiliares). • A entrada ´e geralmente sobrescrita pela sa´ıda conforme o algoritmo ´e executado. O algoritmo in loco atualiza a entrada apenas por meio da substituic¸˜ao ou troca de elementos. • Pergunta: BubbleSort, Insertion-Sort e Selection-Sort s˜ao algoritmos in loco? 16 Algoritmos in loco • Um algoritmo in loco ´e um algoritmo que transforma a entrada sem usar estruturas de dados auxiliares. ◦ uma quantidade constante e pequena de espac¸o de armazenamento extra ´e permitida (geralmente para vari´aveis auxiliares). • A entrada ´e geralmente sobrescrita pela sa´ıda conforme o algoritmo ´e executado. O algoritmo in loco atualiza a entrada apenas por meio da substituic¸˜ao ou troca de elementos. • Pergunta: BubbleSort, Insertion-Sort e Selection-Sort s˜ao algoritmos in loco? 16 Ordenação Estável Ordenac¸˜ao est´avel • Um algoritmo de ordenac¸˜ao ´e est´avel se n˜ao altera a posic¸˜ao relativa de elementos que tˆem um mesmo valor. • Por exemplo, se o vetor tiver dois elementos de valor 13, um algoritmo de ordenac¸˜ao est´avel manter´a o primeiro 13 antes do segundo. • Exemplo: Suponha que os elementos de um vetor s˜ao pares da forma (d, m) que representam datas de um certo ano: a primeira componente representa o dia e a segunda o mˆes. 18 Ordenac¸˜ao est´avel • Um algoritmo de ordenac¸˜ao ´e est´avel se n˜ao altera a posic¸˜ao relativa de elementos que tˆem um mesmo valor. • Por exemplo, se o vetor tiver dois elementos de valor 13, um algoritmo de ordenac¸˜ao est´avel manter´a o primeiro 13 antes do segundo. • Exemplo: Suponha que os elementos de um vetor s˜ao pares da forma (d, m) que representam datas de um certo ano: a primeira componente representa o dia e a segunda o mˆes. 18 Ordenac¸˜ao est´avel • Um algoritmo de ordenac¸˜ao ´e est´avel se n˜ao altera a posic¸˜ao relativa de elementos que tˆem um mesmo valor. • Por exemplo, se o vetor tiver dois elementos de valor 13, um algoritmo de ordenac¸˜ao est´avel manter´a o primeiro 13 antes do segundo. • Exemplo: Suponha que os elementos de um vetor s˜ao pares da forma (d, m) que representam datas de um certo ano: a primeira componente representa o dia e a segunda o mˆes. 18 Ordenac¸˜ao est´avel — Exemplo • Suponha que o vetor est´a em ordem crescente das componentes d: (1,12), (7,12), (16,3), (25,9), (30,3), (30,6), (31,3). • Agora ordene o vetor pelas componentes m. Se usarmos um algoritmo de ordenac¸˜ao est´avel, o resultado estar´a em ordem cronol´ogica: (16,3), (30,3), (31,3), (30,6), (25,9), (1,12), (7,12). • Se o algoritmo de ordenac¸˜ao n˜ao for est´avel, o resultado pode n˜ao ficar em ordem cronol´ogica: (30,3), (16,3), (31,3), (30,6), (25,9), (7,12), (1,12). 19 Ordenac¸˜ao est´avel — Exemplo • Suponha que o vetor est´a em ordem crescente das componentes d: (1,12), (7,12), (16,3), (25,9), (30,3), (30,6), (31,3). • Agora ordene o vetor pelas componentes m. Se usarmos um algoritmo de ordenac¸˜ao est´avel, o resultado estar´a em ordem cronol´ogica: (16,3), (30,3), (31,3), (30,6), (25,9), (1,12), (7,12). • Se o algoritmo de ordenac¸˜ao n˜ao for est´avel, o resultado pode n˜ao ficar em ordem cronol´ogica: (30,3), (16,3), (31,3), (30,6), (25,9), (7,12), (1,12). 19 Ordenac¸˜ao est´avel — Exemplo • Suponha que o vetor est´a em ordem crescente das componentes d: (1,12), (7,12), (16,3), (25,9), (30,3), (30,6), (31,3). • Agora ordene o vetor pelas componentes m. Se usarmos um algoritmo de ordenac¸˜ao est´avel, o resultado estar´a em ordem cronol´ogica: (16,3), (30,3), (31,3), (30,6), (25,9), (1,12), (7,12). • Se o algoritmo de ordenac¸˜ao n˜ao for est´avel, o resultado pode n˜ao ficar em ordem cronol´ogica: (30,3), (16,3), (31,3), (30,6), (25,9), (7,12), (1,12). 19 Exerc´ıcio – Ordenac¸˜ao est´avel • BubbleSort ´e um algoritmo est´avel? 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } Sim! 20 Exerc´ıcio – Ordenac¸˜ao est´avel • BubbleSort ´e um algoritmo est´avel? 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } Sim! 20 Exerc´ıcio – Ordenac¸˜ao est´avel • BubbleSort ´e um algoritmo est´avel? 1 void bubblesort(int A[], int n) { 2 for (int i = 0; i < n-1; i++) 3 for (int j = n -1; j > i; j--) 4 if (A[j] < A[j -1]) { 5 int aux = A[j]; 6 A[j] = A[j -1]; 7 A[j -1] = aux; 8 } 9 } Sim! 20 Exerc´ıcio – Ordenac¸˜ao est´avel • Insertion-Sort ´e um algoritmo est´avel? 1 void insertionsort (int A[], int n) { 2 int i, j, key; 3 for (j = 1; j < n; j++) { 4 key = A[j]; 5 i = j -1; 6 while(i >= 0 && A[i] > key) { 7 A[i+1] = A[i]; 8 i--; 9 } 10 A[i+1] = key; 11 } 12 } Sim! 21 Exerc´ıcio – Ordenac¸˜ao est´avel • Insertion-Sort ´e um algoritmo est´avel? 1 void insertionsort (int A[], int n) { 2 int i, j, key; 3 for (j = 1; j < n; j++) { 4 key = A[j]; 5 i = j -1; 6 while(i >= 0 && A[i] > key) { 7 A[i+1] = A[i]; 8 i--; 9 } 10 A[i+1] = key; 11 } 12 } Sim! 21 Exerc´ıcio – Ordenac¸˜ao est´avel • Insertion-Sort ´e um algoritmo est´avel? 1 void insertionsort (int A[], int n) { 2 int i, j, key; 3 for (j = 1; j < n; j++) { 4 key = A[j]; 5 i = j -1; 6 while(i >= 0 && A[i] > key) { 7 A[i+1] = A[i]; 8 i--; 9 } 10 A[i+1] = key; 11 } 12 } Sim! 21 Exerc´ıcio – Ordenac¸˜ao est´avel • Selection-Sort ´e um algoritmo est´avel? 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } N˜ao! Por exemplo, teste a sequˆencia 443 22 Exerc´ıcio – Ordenac¸˜ao est´avel • Selection-Sort ´e um algoritmo est´avel? 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } N˜ao! Por exemplo, teste a sequˆencia 443 22 Exerc´ıcio – Ordenac¸˜ao est´avel • Selection-Sort ´e um algoritmo est´avel? 1 void selectionsort (int A[], int n) { 2 for (int i = 0; i < n-1; i++) { 3 int min = i; 4 for (int j = i+1; j < n; j++) 5 if(A[j] < A[min ]) 6 min = j; 7 int aux = A[i]; 8 A[i] = A[min ]; 9 A[min] = aux; 10 } 11 } N˜ao! Por exemplo, teste a sequˆencia 443 22 FIM