C#
- Algoritmos de ordenação - IV
![]() |
Hoje vamos continuar apresentando os algoritmos de ordenação usando a linguagem C#. |
Continuando o artigo anterior vamos tratar agora do algoritmo de ordenação Shell Sort.
Ordenação com Shell Sort
O
Shell Sort é basicamente um truque para fazer a
ordenação Insertion Sort ser executada mais
rapidamente. Se você der uma olhada rápida no código e vai perceber que além da
presença de dois laços externos adicionais o código é muito semelhante.
Como o Insertion Sort remove uma inversão por
troca, ele não pode ser executado mais rápido do que o número de inversões nos
dados, que no pior caso é O (N2)
O algoritmo difere
do método de inserção direta pelo fato de no lugar de considerar o array a ser
ordenado como um único segmento, ele considera vários segmentos sendo aplicado o
método de inserção direta em cada um deles. Basicamente o algoritmo passa várias
vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é
aplicado o método da ordenação por inserção. (wikipédia)
O truque no Shell Sort é começar trocando elementos
que estão mais separados. Embora isso possa remover apenas uma inversão às
vezes, muitas vezes muitas mais inversões são removidas com elementos
intermediários. A ordenação Shell considera as
subseqüências de elementos espaçados por k elementos. Existem k dessas
seqüências começando nas posições 0 a k-1 no array. Nesses tipos, os elementos
separados por k posições são trocados, removendo entre 1 e 2 (k-1) inversões +1.
Trocar elementos distantes não é suficiente, geralmente, então um
Shell Sort fará várias passagens com valores
decrescentes de k, terminando com k = 1.
A seguir temos uma implementação da ordenação com Shell Sort no C#:
using System;
namespace Shell_Sort
{
class Program
{
static void Main(string[] args)
{
int[] numeros = { 230, 45, 345, 4, 324, 90, 76, 34, 67, 11 };
Console.WriteLine("######## Ordenação com Shell Sort ########\n");
Console.WriteLine("Intervalos [1, 2, 4, 8]\n");
Console.WriteLine("Array original\n");
foreach (int numero in numeros)
Console.Write($"{numero} ");
Console.WriteLine("\n\nOrdenando o array usando Shell Short\n");
int[] intervalos = { 1, 2, 4, 8 };
int[] arrayOrdenado = IntArrayShellSort(numeros, intervalos);
Console.WriteLine("Array Ordenado\n");
foreach (int numero in arrayOrdenado)
Console.Write($"{numero} ");
Console.ReadLine();
}
public static int[] IntArrayShellSort(int[] data, int[] intervalos)
{
int i, j, k, m;
int N = data.Length;
// Os intervalos precisam ter uma ordenação ascendente
for (k = intervalos.Length - 1; k >= 0; k--)
{
int intervalo = intervalos[k];
for (m = 0; m < intervalo; m++)
{
for (j = m + intervalo; j < N; j += intervalo)
{
for (i = j; i >= intervalo && data[i] < data[i - intervalo]; i -= intervalo)
{
TrocarValores(data, i, i - intervalo);
}
}
}
}
return data;
}
public static int[] TrocarValores(int[] arrayDados, int m, int n)
{
int temp;
temp = arrayDados[m];
arrayDados[m] = arrayDados[n];
arrayDados[n] = temp;
return arrayDados;
}
}
}
|
No exemplo classificamos todas as subsequências dos elementos 8 à parte, depois 4, 2 e 1. Observe que esses intervalos são para mostrar como o método funciona - não como o método funciona melhor.
Uma implementação alternativa (wikipédia) sem usar métodos auxiliares pode ser vista a seguir:
public static int[] ShellSort(int[] array)
{
int h = 1;
int n = array.Length;
while (h < n)
{
h = h * 3 + 1;
}
h = h / 3;
int c, j;
while (h > 0)
{
for (int i = h; i < n; i++)
{
c = array[i];
j = i;
while (j >= h && array[j - h] > c)
{
array[j] = array[j - h];
j = j - h;
}
array[j] = c;
}
h = h / 2;
}
return array;
}
|
Executando o projeto teremos o resultado abaixo :
Pegue o projeto
completo aqui:
Algoritmos_Ordenacao4.zip
Na próxima parte do artigo veremos o algoritmo de ordenação quicksort.
Aquele que crê
no Filho (Jesus) tem a vida eterna; mas aquele que não crê no Filho não verá a
vida, mas a ira de Deus sobre ele permanece.
João 3:36
Referências:
C# - Tasks x Threads. Qual a diferença
VB .NET - Datas, horas: conceitos e operações
C# - Programação Assíncrona como : Asycn e Task
Algoritmos de ordenação - Macoratti.net
NET - Números Perfeitos - Macoratti.net
SQL - O Algoritimo Soundex - Macoratti.net
C# - Estrutura de dados - Algorítmos
C# - Operadores Lógicos - Macoratti.net
C# - Apresentando Arrays - Macoratti.net
C# - Usando delegates na prática - Ordenação