# 1. Algoritmos de Ordenação

Nesta aula, estudaremos diferentes algoritmos de ordenação, os quais podem ser utilizados em diversas situações. Quando temos um conjunto de dados quaisquer, ou seja, não temos conhecimento prévio dos mesmos, podemos fazer uso de um conjunto de técnicas de ordenação cuja complexidade inferior está limitada a $\theta(n\log n)$. As seguintes técnicas serão abordadas:
* Insertion Sort
* Mergesort
* Quicksort
* Heapsort

No entanto, quando algum conhecimento dos dados a serem ordenados é dado, podemos fazer uso de algumas técnicas de ordenação linear, tais como:
* Counting Sort
* Radix Sort
* Bucket Sort
As próximas seções tratam de abordas as técnicas mencionadas.

## 1.1. Insertion Sort

O algoritmo de ordenação por Insertion sort é indicado em situações nas quais os dados chegam ao **longo do tempo**, dado que a sua premissa consiste em inserir cada elemento em sua posição correta no vetor de dados. A Figura 1 apresenta um exemplo de funcionamento do algoritmo Insertion sort, em que o elemento que está sendo comparado na iteração atual (variável $v$ no algoritmo) encontra-se destacado em amarelo.
<br><br>

<figure>

<figcaption>Figura 1: Funcionamento da técnica Insertion Sort.</figcaption>
</figure>

O algoritmo abaixo implementa a técnica Insertion sort, cuja análise de complexidade é dada da seguinte maneira:
* Complexidade de espaço: $\theta(n)$
* Complexidade de tempo: $O(n^2)$
* Estável: Sim
* In-place: Sim


```python
import numpy
import math
from collections import deque
```


```python
def InsertionSort(A):
    n = len(A)
    for i in range(2,n):
        v = A[i]
        j = i-1

        while (A[j] > v) and (j >= 0):
            A[j+1] = A[j]
            j = j-1
        A[j+1] = v
        
```

Note que o laço mais **externo** executa $n-1$ vezes, ou seja, $\theta(n)$ vezes. A complexidade do algoritmo de Insertion sort é dominada pelo laço mais **interno**. Caso tenhamos um vetor ordenado de forma **crescente**, por exemplo, a condição `A[j+1] > v` nunca será satisfeita e, por conseguinte, o laço mais interno não será executado. Nesta situação hipotética, a complexidade seria então dada por $\theta(n)$, que seria então a situação de **melhor caso** para o Insertion sort.

Entretanto, no **pior caso**, ou seja, um vetor ordenado de forma **decrescente**, o laço mais interno será executado $i-1$ vezes para cada valor de $i$. Desta forma, teremos $i(i-1)\approx i^2$ execuções, resultando em uma complexidade final de $O(n^2)$.

Exemplo de funcionamento:


```python
A = numpy.random.randint(-20, 20, 10)
print('Vetor de entrada: '+ str(A))
InsertionSort(A)
print('Vetor ordenado: '+ str(A))
```

    Vetor de entrada: [-10   5 -12   6  10  -4  -6  -2  -8 -11]
    Vetor ordenado: [-12 -11 -10  -8  -6  -4  -2   5   6  10]


## 1.2. Mergesort

O algoritmo de ordenação por Mergesort é baseado na metodologia de **divisão e conquista**, em que o problema principal é dividido em subproblemas que são resolvidos e, posteriormente, agrupados com o intuito de gerar a solução final. A divisão é realizada em $\theta(1)$, ao passo que a conquista é realizada em $\theta(n)$. De maneira geral, a ténica realiza divisões no vetor pela metade, até que um único elemento é obtido. Em seguida, o processo de conquista é realizado, em que os elementos são agrupados de maneira ordenada. A Figura 2 apresenta esse processo, em que os elementos cinza denotam a primeira metade do vetor, e os elementos em azul correspondem ao final da etapa de divisão.
<br><br>

<figure>

<figcaption>Figura 2: Funcionamento da técnica Mergesort.</figcaption>
</figure>

O algoritmo abaixo implementa a técnica Mergesort, cuja análise de complexidade é dada da seguinte maneira:
* Complexidade de espaço: $\theta(2n)$
* Complexidade de tempo: $\theta(n\log n)$
* Estável: Sim
* In-place: Não

A complexidade de tempo pode ser calculada por meio do **Teorema Mestre** da seguinte maneira:

\begin{equation}
\tag{1}
\label{e.recurrence_analysis_mergesort_part1}
T(n) =
    \begin{cases}
      1 & \text{se $n=1$}\\
      aT\left(\frac{n}{b}\right) + f(n)& \text{caso contrário.}
    \end{cases}  
\end{equation}

Como pode ser observado, a função `MergeSort` é invocada duas vezes de maneira recursiva, em que cada chamada é realizada em metade do vetor. Desta forma, temos que $a=b=2$. 

Entretanto, falta ainda analisarmos o termo **residual** $f(n)$ da Equação \ref{e.recurrence_analysis_mergesort_part1}, o qual é composto por três laços: (i) o primeiro deles copia a primeira metade do vetor de dados de entrada $A$ para o vetor **auxiliar** $B$ e possui complexidade de tempo $\theta\left(\frac{n}{n}\right)\in\theta(n)$; (ii) o segundo laço copia a segunda metade do vetor $A$ em $B$, porém de maneira invertida, e também possui complexidade de tempo $\theta\left(\frac{n}{n}\right)\in\theta(n)$; e (iii) o último laço copia os elementos de $B$ no vetor de dados de entrada $A$ de maneira ordenada, ou seja, nesta etapa é realizada a junção (*merge*) dos dados, e possui complexidade $\theta(n)$. Desta forma, o termo residual, ou seja, a conquista, possui complexidade $\theta(n)$.

Assim sendo, podemos reescrever a Equação \ref{e.recurrence_analysis_mergesort_part1} da seguinte maneira:

\begin{equation}
\tag{2}
\label{e.recurrence_analysis_mergesort_part2}
T(n) =
    \begin{cases}
      1 & \text{se $n=1$}\\
      2T\left(\frac{n}{2}\right) + n& \text{caso contrário.}
    \end{cases}  
\end{equation}
O termo residual pode ser mapeado para a forma $cn^k$ assumindo $c=k=1$. Desta forma, de acordo com o Teorema Mestre, a complexidade final de tempo do Mergesort é dada por $\theta(n^k\log_bn)=\theta(n\log n)$.


```python
def MergeSort(A, e, d):
    if (d > e):
        
        # Divisão é realizada em theta(1) *****
        m = math.floor((e+d)/2) 
        MergeSort(A, e, m)
        MergeSort(A, m+1, d)
        # Fim da divisão **********************
        
        # Conquista é realizada em theta(n) ***
        B = numpy.zeros(d+1);
        
        for k in range(0, m+1):
            B[k] = A[k]
        
        j = d
        for k in range(m+1, d+1):
            B[j] = A[k]
            j = j-1
        
        i = e
        j = d
        for k in range(e, d+1):
            if(B[i] < B[j]):
                A[k] = B[i]
                i = i+1
            else:
                A[k] = B[j]
                j = j-1
        # Fim da conquista ********************
```

Exemplo de funcionamento:


```python
A = numpy.random.randint(-20, 20, 10)
print('Vetor de entrada: '+ str(A))
MergeSort(A, 0, 9)
print('Vetor ordenado: '+ str(A))
```

    Vetor de entrada: [ 17  14  -3 -12 -10  15  11 -11   0  -5]
    Vetor ordenado: [-12 -11 -10  -5  -3   0  11  14  15  17]


 ## 1.3. Quicksort
 
O algoritmo de ordenação Quicksort também é baseado na metodologia de divisão e conquista, em que esta última é realizada em tempo $\theta(1)$, ao passo que o "gargalo" da técnica está justamente na etapa de divisão. O algoritmo faz uso de um elemento denominado **pivô**, e assume que os elementos à **esquerda** deste são menores ou iguais à ele; ao passo que os elementos à sua **direita** são maiores ou iguais ao pivô. Note que, não necessariamente, os elementos que estão à esquerda e à direita estarão ordenados entre si.

Desta forma, a complexidade de tempo do Quicksort depende, necessariamente, da **posição** do pivô durate a execução do algoritmo. Se conseguíssemos garantir que o pivô sempre dividisse o vetor de entrada ao meio, então a a complexidade de ordenação seria igual à do Mergesort, ou seja, $\theta(n\log n)$. Entretanto, essa garantia não é possível de ser assegurada. A Figura 3 apresenta o funcionamento da técnica Quicksort, em que os elementos à esquerda do pivô são representador pela cor cinza, os elementos azuis correspondem aos valores que são maiores ou iguais ao pivô e, finalmente, o pivô está representado em laranja.
<br><br>

<figure>

<figcaption>Figura 3: Funcionamento da técnica Quicksort.</figcaption>
</figure>

O algoritmo abaixo implementa a técnica Quicksort, cuja análise de complexidade é dada da seguinte maneira:
* Complexidade de espaço: $\theta(n)$
* Complexidade de tempo: $O(n^2)$, porém sua complexidade no caso médio é de $O(n\log n)$
* Estável: Não
* In-place: Sim



```python
def Quicksort(A, e, d):
    if (d > e):
            index = Partition(A, e, d) #função que retorna o novo índice do pivô (elemento laranja)
            Quicksort(A, e, index-1) # executa o Quicksort na parte cinza
            Quicksort(A, index+1, d) # executa o Quicksort na parte laranja

def Partition(A, e, d):
    pivot = A[d]
    p_index = e

    for i in range(e,d):
        if (A[i] <= pivot):
            A[i], A[p_index] = A[p_index], A[i]
            p_index = p_index + 1
        
    A[p_index], A[d] = A[d], A[p_index]

    return p_index
```

Exemplo de funcionamento:


```python
A = numpy.random.randint(-20, 20, 6)
print('Vetor de entrada: '+ str(A))
Quicksort(A, 0, 5)
print('Vetor ordenado: '+ str(A))
```

    Vetor de entrada: [-18 -18   4  13 -18  -3]
    Vetor ordenado: [-18 -18 -18  -3   4  13]


## 1.4. Heapsort

O algoritmo de ordenação Heapsort é uma técnica baseada em comparações, cujo funcionamento é dividido em três partes: (i) construção de um heap (usualmente binário) a partir dos dados de entrada, (ii) remover a raiz e inserir na última posição do vetor, e (iii) mover último nó para a posição da raiz. Note que este último passo exige que o heap seja atualizado a cada remoção de tal forma a manter suas propriedades. Para uma ordenação **crescente**, devemos utilizar um **heap máximo**, ao passo que para uma ordenação **decrescente** deve-se empregar um **heap mínimo**. 

A primeira parte, como citado anteriormente, consiste em transformar um vetor de entrada em um **heap binário**, o qual, por sua vez, utiliza uma estrutura de **árvore binária**. Isto pode ser feito, basicamente, por meio de uma associação de índices do próprio vetor, como apresenta a Figura 4. 
<br><br>

<figure>

<figcaption>Figura 4: Mapeando um vetor para uma árvore binária.</figcaption>
</figure>

Neste caso, temos que a raiz é representada pelo elemento $A[0]$, cujos filhos são os elementos $A[1]$ e $A[2]$. Por conseguinte, os filhos do nó $A[1]$ são dados por $A[3]$ e $A[4]$, e o último nó representado por $A[5]$. Assim sendo, temos que:

* A[0]: possui como filhos $A[1]$ e $A[2]$, ou seja, $A[i+1]$ e $A[i+2]$ para $i=0$.
* A[1]: possui como filhos $A[3]$ e $A[4]$, ou seja, $A[i+2]$ e $A[i+3]$ para $i=1$.
* A[2]: possui como filho $A[5]$, ou seja, $A[i+3]$ para $i=2$.

Podemos, então, generalizar da seguinte forma: $A[i]$ possui como filhos os elementos $A[2i+1]$ e $A[2i+2]$.

Em seguida, precisamos verificar se o heap obedece à propriedade de um heap máximo, ou seja, o valor armazenado em um nó pai tem que ser maior ou igual ao(s) valor(es) armazenzado(s) em seu(s) nó(s) filho(s). A Figura 5 apresenta essa metodologia.
<br><br>

<figure>

<figcaption>Figura 5: Mapeando uma árvore árvore binária para um heap máximo.</figcaption>
</figure>

Em seguida, o nó raiz (maior valor) é removido e inserido na última posição do vetor, e o último nó do heap toma o seu lugar. Entretanto, após esta operação, precisamos verificar se o heap obedece à propriedade de heap máximo, ou seja, um nó filho tem sempre um valor menor ou igual ao seu pai (procedimento implementado pela função `Heapify` no algoritmo abaixo). Após atualizarmos a estrutura, o procedimento todo é repetido novamente até que todos os elementos tenham sido removidos do heap. A Figura 6 ilustra este procedimento.
<br><br>

<figure>

<figcaption>Figura 6: Funcionamento da técnica Heapsort.</figcaption>
</figure>

O algoritmo abaixo implementa a técnica Heapsort, cuja análise de complexidade é dada da seguinte maneira:
* Complexidade de espaço: $\theta(n)$
* Complexidade de tempo: $O(n\log n)$
* Estável: Não
* In-place: Sim


```python
#Algoritmo baseado no código disponível em https://www.tutorialspoint.com/python-program-for-heap-sort

# função que verifica se um heap obedece às propriedades de heap máximo
def Heapify(A, n, i):
    
    maior = i # maior valor
    l = 2*i + 1 # filho à esquerda
    r = 2*i + 2 # filho à esquerda

    # verifica se filho à esquerda existe e quem possui o maior valor
    if (l < n) and (A[i] < A[l]):
        maior = l
        
    # verifica se filho à direita existe e quem possui o maior valor
    if (r < n) and (A[maior] < A[r]):
        maior = r
    
    # analisa raiz
    if (maior != i):
        A[i],A[maior] = A[maior],A[i] # faz a troca entre a raiz e o maior valor encontrado

        # executa todo o processo novamente
        Heapify(A, n, maior)

# Heapsort
def Heapsort(A):
    
    n = len(A)
    
    # cria o heap máximo
    for i in range(n-1, -1, -1):
        Heapify(A, n, i)
        
    # remoção da raiz e sua inserção na posição correta do vetor ordenado
    for i in range(n-1, 0, -1):

        A[i], A[0] = A[0], A[i]
        Heapify(A, i, 0)
```

Note que o primeiro laço da função `Heapsort`executa $n+1$ vezes, ou seja, $\theta(n)$ vezes, ao passo que o segundo laço executa, também, $\theta(n)$ vezes. Agora, precisamos calcular a complexidade da função `Heapify`, a qual objetiva manter a estrutura de acordo com as propriedades de um heap máximo, conforme mencionado anteriormente. Como a criação do heap objetiva a construção de uma árvore binária balanceada, sabemos que sua altura pode ser dada por $O(\log n)$. No pior caso, ou seja, quando um nó folha precisa ser movido até a raiz, temos que um número $O(\log n)$ de comparações deve ser efetuado até que a propriedade do heap máximo seja satisfeita. Desta forma, temos que a função `Heapify` possui complexidade $O(\log n)$, resultando em uma complexidade final de $O(n\log n)$ para o algoritmo do Heapsort.

Exemplo de funcionamento:


```python
A = numpy.random.randint(-20, 20, 6)
print('Vetor de entrada: '+ str(A))
Heapsort(A)
print('Vetor ordenado: '+ str(A))
```

    Vetor de entrada: [ -8  17   1 -20   9   5]
    Vetor ordenado: [-20  -8   1   5   9  17]


## 1.4. Counting Sort

Suponha que tenhamos um vetor $A$ com $n$ elementos naturais, isto é, $A[i]\geq 0$, $\forall i=1,2,\dots,n$, tal que seu maior elemento possui o valor $k$. Neste caso, podemos fazer uso da técnica de ordenação por Counting Sort a qual, basicamente, conta quantos elementos são menores do que $A[i]$. O mais interessante da técnica é que ela faz a ordenação de um conjunto de valores **sem realizar comparações**. A Figura 7 ilustra este procedimento.
<br><br>

<figure>

<figcaption>Figura 7: Funcionamento da técnica Counting Sort.</figcaption>
</figure>

O algoritmo abaixo implementa a técnica Counting Sort, cuja análise de complexidade é dada da seguinte maneira:
* Complexidade de espaço: $\theta(2n+k)$
* Complexidade de tempo: $\theta(n)$
* Estável: Sim
* In-place: Sim


```python
def CountingSort(A, k):
    
    n = len(A)
    B = numpy.zeros(n+1, dtype=int)
    C = numpy.zeros(k+1, dtype=int)

    # C[A[i]] armazena o número de vezes que o elemento A[i] aparece no vetor a ser ordenado
    for i in range(0, n):
        C[A[i]] = C[A[i]] + 1
    
    # C[i] armazena
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]
    
    for i in range(n-1, -1, -1):
        B[C[A[i]]] = A[i]
        C[A[i]] = C[A[i]] - 1
    
    return B
```

O primeiro laço do algoritmo é executado $\theta(n)$ vezes, ao passo que o segundo laço é executado por $\theta(k)$ iterações. Finalmente, o terceiro laço também é executado $\theta(n)$. Desta forma, temos uma complexidade dada por 

Exemplo de funcionamento:


```python
k = 10
A = numpy.random.randint(0, k, 20)
print('Vetor de entrada: '+ str(A))
B = CountingSort(A, k)
print('Vetor ordenado: '+ str(B))
```

    Vetor de entrada: [4 5 3 9 0 3 0 2 3 4 9 8 5 8 9 9 5 3 6 8]
    Vetor ordenado: [0 0 0 2 3 3 3 3 4 4 5 5 5 6 8 8 8 9 9 9 9]


## 1.5. Bucket Sort

O algoritmo de ordenação Bucket Sort supõe que os elementos do vetor a ser ordenado $A$ encontram-se distribuídos **uniformemente** no intervalo $[0,1)$. A ideia consiste em dividir os elementos em $k$ segmentos (buckets) de igual tamanho e distribuir os elementos nesses segmentos. Como partimos da premissa de que os elementos do vetor de entrada encontram-se distribuídos uniformemente, é esperado que os segmentos contenham o mesmo número de elementos. Posteriormente, os elementos de cada segmento são ordenados por um método qualquer e o vetor final ordenado é obtido **concatenando** os segmentos em **ordem crescente**.

Diversos algoritmos podem ser utilizados para a ordenação dos elementos de cada segmento, muito embora uma das abordagens mais empregadas é o **Insertion Sort**, dado que o seu tempo de ordenação é baseado no quão distante um elemento está de sua posição final no conjunto ordenado. Ao dividir o vetor em segmentos, na prática, estamos facilitando a tarefa do algoritmo de ordenação, pois teremos menos elementos a serem ordenados quando consideramos um segmento por vez. A Figura 8 ilustra o funcionamento do Bucket Sort.
<br><br>

<figure>

<figcaption>Figura 8: Funcionamento da técnica Bucket Sort.</figcaption>
</figure>

O algoritmo abaixo implementa a técnica Bucket Sort utilizando Insertion Sort para o procedimento de ordenação de cada segmento, cuja análise de complexidade é dada da seguinte maneira:
* Complexidade de espaço: $\theta(n+k)$
* Complexidade de tempo:
* * Melhor caso: $O(n)$
* * Caso médio: $O(n)$ quando $k\approx n$
* * Pior caso: $O(n^2)$
* Estável: Sim
* In-place: Não


```python
def BucketSort(A):
    
    n = len(A)
    
    # criando um vetor de listas ligadas
    B = numpy.empty(n)
    B = B.tolist()

    for i in range(0, n):
        B[i] = deque()
    
    for i in range(0, n):
        B[math.floor(n*A[i])].append(A[i]) # insere elemento A[i] em seu segmento (bucket) específico
    
    z = 0
    for i in range(0, n):
        InsertionSort(B[i]) # ordena segmento i
        
        for j in range(0, len(B[i])): # gerando vetor ordenado final pela concatenação dos segmentos
            A[z] = B[i].popleft()
            z = z+1
            
```

O primeiro laço do algoritmo é executado $\theta(n)$ vezes, e consiste na criação dos apontadores para as listas ligadas. Já o segundo laço, o qual também é executado $\theta(n)$ vezes, insere cada elemento do vetor de entrada $A$ em sua posição (segmento ou bucket) correspondente, a qual é calculada como segue: 

\begin{equation}
\label{e.bucketsort}
\tag{3}
B[\lfloor n* A[i]\rfloor] = A[i].
\end{equation}

Note que estamos seguindo a implementaçNo último laço, o qual executa $\theta(n)$ vezes, cada segmento é ordenado utilizando Insertion Sort para posterior geração do vetor final ordenado bastando, apenas, concatenar cada segmento ordenado. Falta, apenas, determinarmos a complexidade do Insertion Sort. No **melhor caso**, teríamos apenas um único elemento em cada segmento, bastando copiar (concatenar) os elementos do vetor auxiliar $B$ no vetor de saída $A$, o qual resultaria em $\theta(n)$ operações. Já o **pior caso** contemplaria a situação em que todos os elementos seriam mapeados para um mesmo segmento. Nesta situação, sabemos que Insertion Sort possui complexidade $O(n^2)$.

Exemplo de funcionamento:


```python
A = numpy.random.random(10)
print('Vetor de entrada: '+ str(A))
BucketSort(A)
print('Vetor ordenado: '+ str(A))
```

    Vetor de entrada: [0.89806448 0.81719929 0.78607081 0.30571191 0.91212116 0.30742524
     0.64817982 0.58592705 0.38073669 0.62501044]
    Vetor ordenado: [0.30571191 0.30742524 0.38073669 0.58592705 0.64817982 0.62501044
     0.78607081 0.89806448 0.81719929 0.91212116]


## 1.5. Radix Sort

Suponha que o conjunto de dados $A$ a ser ordenado é composto por números **inteiros** com até $d$ dígitos. A ideia, de maneira geral, é bastante simples: considerando cada um dos dígitos, da esquerda para a direita, ordene o conjunto de elementos utilizando alguma técnica de ordenação **estável**. Assim sendo, a complexidade final do algoritmo Radix Sort será dependente da técnica utilizada para a ordenação dos números de acordo com cada dígito. A estabilidade garante que os números não trocarão de posição após serem ordenados para cada dígito. A Figura 9 ilustra o funcionamento do Radix Sort.
<br><br>

<figure>

<figcaption>Figura 9: Funcionamento da técnica Radix Sort.</figcaption>
</figure>

O algoritmo abaixo implementa a técnica Radix Sort, cuja análise de complexidade é dada da seguinte maneira:
* Complexidade de espaço: $\theta(g(n))$, em que $g(n)$ denota a complexidade de espaço do algoritmo utilizado para a ordenação
* Complexidade de tempo: $O(df(n))$, em que $f(n)$ denota a complexidade de tempo do algoritmo utilizado para a ordenação
* Estável: Sim
* In-place: Sim/Não (depende do algoritmo utilizado para a ordenação)

No exemplo abaixo, utilizaremos uma heurística similar à técnica Counting Sort, em que os números são posicionados em seus respectivos segmentos (buckets) de acordo com o dígito em questão.


```python
def RadixSort(A):
    
    radix = 10
    aux = 1
    fim = False
    
    while not fim:
        
        fim = True
        B = [list() for _ in range(radix)] # cria os buckets
        for i in A:
            tmp = i/aux
            B[int(tmp % radix)].append(i)
            if(fim) and (tmp > 0):
                fim = False

        j = 0
        for b in range(radix):
            buck = B[b]
        
            for i in buck:
                A[j] = i
                j = j + 1

        aux = aux * radix
```

O laço principal (comando `while`) executa $\theta(d)$ vezes, em que $d$ corresponde ao número de dígitos do maior elemento. Já o primeiro laço interno executa $\theta(n)$ vezes, pois percorre todos os elementos do vetor $A$, e o segundo laço interno percorre cada um dos $10$ segmentos. Como estamos utilizando um conjunto de valores a serem ordenados que pertencem à um sistema decimal, ou seja, `radix = 10`, temos que esse laço executa $10$ vezes,ou seja, em tempo constante $\theta(1)$. Note que a palavra **radix** tem origem no latim e significa **raiz**, ou base. Assim, a técnica Radix Sort ordena os números de acordo com sua base decimal.

Desta forma, a **complexidade de tempo** do Radix Sort é dada por $\theta(dn)$, ao passo que sua **complexidade de espaço** é dada por $\theta(2n)$, dado que temos o vetor de antrada $A$ com $n$ elementos e uma estrutura de lista ligada temporária (`buckets`) que armazena os elementos. Segue, abaixo, um exemplo de funcionamento:


```python
d = 3 # número de dígitos do maior elemento a ser gerado aleatoriamente
A = numpy.random.randint(0, math.pow(10,d)-1, 20)
print('Vetor de entrada: '+ str(A))
RadixSort(A)
print('Vetor ordenado: '+ str(A))
```

    Vetor de entrada: [367 622  62 777 214 360 580 863 153 653 818 701 826 962 700 939 336 376
     667 996]
    Vetor ordenado: [ 62 153 214 336 360 367 376 580 622 653 667 700 701 777 818 826 863 939
     962 996]



```python

```
