Introdução
Julia, como a maioria das linguagens de programação, oferece uma grande variedade de tipos de coleção.
Alguns são ordenados por natureza (incluindo Vectors e Arrays de dimensões maiores), então podemos acessar os elementos pela posição.
Outras coleções não têm ordem (Sets, Dicts), e os elementos precisam ser acessados pela chave ou pelo valor.
No caso mais simples, suponha que temos um Vector de Ints e queremos ordená-lo em ordem crescente.
julia> v = [3, 2, 4, 1]
4-element Vector{Int64}:
3
2
4
1
julia> sort(v)
4-element Vector{Int64}:
1
2
3
4
# sort descending
julia> sort(v, rev=true)
4-element Vector{Int64}:
4
3
2
1
Simples!
A função sort() tem um nome óbvio e, aparentemente, retorna o Vector ordenado.
Só brincadeira!
A essa altura do curso, você talvez suspeite (com razão) que existem nuances que precisamos discutir.
Funções que modificam vs. funções que não modificam
Depois de rodar sort(v), o que é v?
julia> v
4-element Vector{Int64}:
3
2
4
1
julia> issorted(v)
false
O vetor original não mudou.
sort() é uma função que não modifica a entrada: ela retorna uma cópia dela.
Isso é um bom design em muitos contextos: temos uma função pura cujo comportamento é fácil de entender, até mesmo em código paralelo e distribuído.
Por outro lado, suponha que tivéssemos um array de um bilhão de strings e quiséssemos ordená-lo.
A ordenação provavelmente é lenta.
Além disso, precisamos copiar tudo (lento!) e alocar memória suficiente (vários GigaBytes!) para guardar a cópia.
Compare com este código bem parecido:
# v is as previously
julia> issorted(v)
false
julia> sort!(v)
4-element Vector{Int64}:
1
2
3
4
julia> v
4-element Vector{Int64}:
1
2
3
4
julia> issorted(v)
true
Agora o Vector de entrada é ordenado no lugar, sem cópia, e a ordem original é perdida para sempre.
Isso pode ser eficiente, pode ter bugs e causar efeitos colaterais inesperados, e pode confundir outras pessoas que usam o seu código.
Escolha com cuidado!
sort!() é uma "função que modifica", e por convenção (muito forte), toda função que modifica suas entradas tem um ! acrescentado ao nome, como aviso para quem programa.
Ordenar por array de índices
Se os elementos que estão sendo ordenados forem objetos grandes, pode ser mais fácil trabalhar com o índice de posição deles.
julia> langs = ["Julia", "C++", "Python", "Elixir"]
4-element Vector{String}:
"Julia"
"C++"
"Python"
"Elixir"
julia> inxs = sortperm(langs) # => Integers
4-element Vector{Int64}:
2
4
1
3
julia> langs[inxs] # sort the entire vector
4-element Vector{String}:
"C++"
"Elixir"
"Julia"
"Python"
julia> langs[inxs[1:2]] # slice the indices
2-element Vector{String}:
"C++"
"Elixir"
Como langs é um Vector, cada índice é um número inteiro no intervalo 1:length(langs).
A saída de sortperm() é uma permutação desses inteiros, correspondendo a uma ordenação do vetor de entrada.
Instruções
Você foi contratado como Engenheiro de Produção Assistente em uma empresa que produz colchas para tartarugas.
Os pedidos chegam ao longo do dia na forma de um nome ou número de cliente e uma quantidade pedida.
Eles são então processados de manhã, antes de a produção do dia começar.
Você pode ir para casa com o pagamento integral assim que todos os pedidos do dia forem atendidos, então há um incentivo para encurtar o dia de trabalho o máximo possível.
Como cada pedido é processado por uma única máquina, agendar primeiro os maiores permite empurrar o custo de iniciar um trabalho para os pedidos menores, encurtando o tempo total de produção.
Por isso, você decidiu criar algumas funções de ordenação para ajudar a acelerar esse agendamento, para poder chegar em casa e tricotar um suéter para sua tartaruga.
1. Ordene a quantidade!
Como observado, o array de quantidades precisará ser ordenado do maior para o menor.
Como esses arrays podem ser muito grandes, eles devem ser ordenados in-place.
Para acompanhar tudo corretamente, você também vai precisar ordenar o array de clientes de acordo com as quantidades, então será necessária uma permutação de ordenação das quantidades.
Escreva uma função sortquantity!(qty) que recebe um Vector de quantidades Integer.
Essa função ordena a entrada qty in-place em ordem decrescente e retorna uma permutação de ordenação dessa ordem.
julia> qty = [8, 9, 5, 6]
4-element Vector{Int64}:
8
9
5
6
julia> sortquantity!(qty)
4-element Vector{Int64}:
2
1
4
3
julia> qty # original vector is sorted in-place
4-element Vector{Int64}:
9
8
6
5
2. Ordene o cliente
Como dito acima, você precisa acompanhar os clientes em uma ordem definida.
Escreva uma função sortcustomer(cust, srtperm) que recebe um Vector de clientes cust e um Vector de permutação de ordenação srtperm.
Essa função retorna um novo array com os clientes na ordem indicada pela permutação de ordenação.
julia> cust = ["a", "b", "c"]
3-element Vector{String}:
"a"
"b"
"c"
julia> sortcustomer(cust, [2, 3, 1])
3-element Vector{String}:
"b"
"c"
"a"
julia> cust # original vector remains unsorted
3-element Vector{String}:
"a"
"b"
"c"
3. Cronograma de produção!
Agora você pode juntar tudo para ajudar a manter essas tartarugas aquecidas!
Agora você consegue ordenar as quantidades e os clientes corretamente, mas precisa conseguir recuperar a ordem original para o envio.
Isso pode ser feito com uma permutação de ordenação inversa.
Escreva uma função production_schedule!(cust, qty) que recebe um Vector de clientes e um Vector de quantidades.
Essa função ordena as quantidades in-place em ordem decrescente.
Ela retorna um novo Vector de clientes ordenados na mesma ordem que as quantidades e uma permutação de ordenação inversa, que pode ser usada para restaurar os vetores ordenados à sua ordem original.
julia> cust, qty = ["a", "b", "c"], [2, 3, 1]
(["a", "b", "c"], [2, 3, 1])
julia> orderedcust, invperm = production_schedule!(cust, qty)
(["b", "a", "c"], [2, 1, 3])
julia> qty # has been sorted in-place
3-element Vector{Int64}:
3
2
1
julia> orderedcust[invperm], qty[invperm] # inverse permutation gives original ordering
(["a", "b", "c"], [2, 3, 1])
Exercício de aprendizagem
