C# - Algoritmos de ordenação - V

 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 Quick Sort.

Ordenação com Quick Sort

O Quick Sort é um algoritmo de ordenação que usa o método de divisão e conquista. Ele pega um elemento pivô e o coloca em sua posição correta. Em seguida, o array à esquerda e à direita do elemento pivô é novamente ordenado usando o Quick Sort. Isso é feito até que todo o array seja ordenado.

Existem muitas versões diferentes do quickSort que selecionam o pivô de maneiras diferentes :

O algoritmo usado pode ser resumido da seguinte forma:

  1. SELECIONE um ponto de pivô;
  2. REORDENE a coleção de forma que todos os valores menores que o pivô estejam antes do pivô e todos os valores maiores que o pivô estejam depois dele;
  3. CONTINUAR RECURSIVO: Retorne à Etapa 1, selecionando um novo pivô em cada uma das seções divididas superior e inferior, até que a matriz seja classificada.

A seguir temos uma implementação da ordenação com Quick Sort no C#:

using System;
namespace Quick_Sort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numeros = { 230, 45, 345, 4, 324, 90, 76, 34, 67, 11, 7 };
            Console.WriteLine("######## Ordenação com Quick Sort ########\n");

            Console.WriteLine("Array original\n");
            foreach (int numero in numeros)
                Console.Write($"{numero} ");
            int[] arrayOrdenado = IntArrayQuickSort(numeros);
            Console.WriteLine("\n\nArray Ordenado\n");
            foreach (int numero in arrayOrdenado)
                Console.Write($"{numero} ");
            Console.ReadLine();
        }
        public static int[] IntArrayQuickSort(int[] data)
        {
            var resultado = IntArrayQuickSort(data, 0, data.Length - 1);
            return resultado;
        }
        public static int[] IntArrayQuickSort(int[] data, int l, int r)
        {
            int i, j;
            int x;
            i = l;
            j = r;
            x = data[(l + r) / 2]; /* acha o item pivot */
            while (true)
            {
                while (data[i] < x)
                    i++;
                while (x < data[j])
                    j--;
                if (i <= j)
                {
                    TrocarValores(data, i, j);
                    i++;
                    j--;
                }
                if (i > j)
                    break;
            }
            if (l < j)
                IntArrayQuickSort(data, l, j);
            if (i < r)
                IntArrayQuickSort(data, i, r);
            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;
        }
    }
}

A complexidade do QuickSort depende da seleção do pivô.

O pior caso de complexidade de tempo desse algoritmo é O(N²), se o maior ou o menor elemento for selecionado como pivô.

A complexidade de tempo médio de caso desse algoritmo também é O(NLogN).

Executando o projeto teremos o resultado abaixo :

Pegue o projeto completo aqui:  Algoritmos_Ordenacao5.zip

"Porque do céu se manifesta a ira de Deus sobre toda a impiedade e injustiça dos homens, que detêm a verdade em injustiça."
Romanos 1:18

Referências:

José Carlos Macoratti