linguagem

topico

nome

Erlang QSort

titulo

Erlang QSort

descritor

apoie, apoie.org, componente, Erlang, linguagem, lista, função, programação, desenvolvimento

lead

Tutorial para ordenar lista de forma crescente ou decrescente utilizando Erlang.

origem

Erlang.xml

topico

titulo

Problema: ordenar lista

desc

ordenar(lista) => lista ordenada
ex: ordenar ([4, 3, 9, 3, 7, 4, 2]) => [2, 3, 3, 4, 4, 7, 9]

topico

titulo

Rodar exemplos

desc

• ordenar ([4, 3, 9, 3, 7, 4, 2])
• ordenar([1,2,a,3,4,b,5,6]
• ordenar([])
• outros exemplos
  

topico

titulo

Idéia da solução: usar quick sort

desc

ordenar(lista) => lista ordenada

1. pegar primeiro elemento da lista: 4
2. criar 2 listas e ordená-las:
• elementos menores que o primeiro:
  ordenar [ 3, 3, 2] => [2, 3, 3]
• restante dos elementos: 
  ordenar [9, 7, 4] => [4, 7, 9]
3. Concatenar listas:
   [2, 3, 3] ++ [4] ++ [4, 7, 9] => [2, 3, 3, 4, 4, 7, 9]
   

topico

titulo

Função para ordenar

desc

ordenar([]) -> [];
ordenar([Primeiro|Resto]) ->
    ordenar([X|| X <- Resto, X < Primeiro]) ++ [Primeiro] ++ ordenar([X|| X <- Resto, X >= Primeiro]).

topico

titulo

Componentes usados

desc

• lista
• lista com Resto
• list comprehension

topico

titulo

Componentes usados - Lista

desc

... ordenar([4, 3, 9, 3, 7, 4, 2]) -> ..

topico

titulo

Componentes usados - Lista com resto

desc

... ordenar([Primeiro|Resto]) -> ...
... ordenar([4 | 3, 9, 3, 7, 4, 2]) -> ...
Primeiro = 4
Resto = [3, 9, 3, 7, 4, 2]

topico

titulo

Componentes usados - List Comprehension

desc

[X|| X <- Resto, X < Primeiro]
A lista de X tal que X pertence a Resto e X é menor que Primeiro.

[X|| X <- [3, 9, 3, 7, 4, 2], X < 4]
The list of X such that X is taken from the list [3,9,3,7,4,2]and X is less than 4.

topico

titulo

Função completa para ordenar

desc

-module(quicksort).
-export([ordenar/1]).

ordenar([]) -> [];
ordenar([Primeiro|Resto]) ->
    ordenar([X|| X <- Resto, X < Primeiro]) ++ 
[Primeiro] ++ 
ordenar([X|| X <- Resto, X >= Primeiro]).

1. "-module(quicksort).": nome do arquivo = quicksort.erl
2. "-export([ordenar/1]).":
   lista de "função/quantidade de parâmetros" 
   funções visíveis externamente
   

topico

titulo

Fazer função

desc

ordenar lista de forma crescente ou decrescente
ordenar(tipo da ordenação, lista) => lista ordenada
tipo da ordenação:

• c = crescente
• d = decrescente
  
  

topico

titulo

Avaliar solução

desc

-module(quicksort2).
-export([ordenar/1, ordenar/2]).

ordenar(Lista) -> ordenar(c,Lista).

ordenar(_,[]) -> [];
ordenar(c,[Primeiro|Resto]) -> ordenar(c,[X||X <- Resto, X < Primeiro]) ++ [Primeiro] ++ ordenar(c,[X||X <- Resto, X >= Primeiro]);

ordenar(d,[Primeiro|Resto]) -> ordenar(d,[X||X <- Resto, X > Primeiro]) ++ [Primeiro] ++ ordenar(d,[X||X <- Resto, X =< Primeiro]).

topico

titulo

Retrospectiva :) :(

desc