defmodule QSort do
  @moduledoc """
  An implementation of quicksort
  This is not the quickest implementation because it is based on lists
  (it is elixir) and because the final list assembly is done using ++
  which takes linear time in the first list size.
  Still it works
  author: gtowell
  Created: Jul 2022
  """
  @doc """
  Partition a list according to the first element in the list.
  This is known to have bad failure modes but so be it
  return a tuple of {lesser list, splitter, greater list}
  First, if the list is empty
  """
  defp partition([]) do
    {[],nil,[]}
  end

  @doc """
  partition when the list ot be partitioned has exactly one item
  """
  defp partition([a]) do
    {[], a, []}
  end

  @doc """
  partition when the list has more than one item
  """
  defp partition([a|r]) do
    ipartition(a,r)
  end

  @doc """
  Actually do the work of partitioning.
  Only gets called on non-empty original list
  First, when the list to be partitioned has onothing more than the
  splitter
  """
  defp ipartition(split, []) do
    {[], split, []}
  end

  @doc """
  when the first element in the list is less than the
  splitter, add that element to the lesser list
  """
  defp ipartition(split, [h|r]) when h<split do
    {a,_,b}=ipartition(split, r)
    {[h|a], split, b}
  end

  @doc """
  When the first element is greater than or equal,
  add it to the greater list
  """
  defp ipartition(split, [h|r]) do
    {a,_,b}=ipartition(split, r)
    {a, split, [h|b]}
  end

  @doc """
  Actually do quicksort
  When the list is empty do nothing
  """
  def quicksort([]) do
    []
  end

  @doc """
  When the list has exactly one item, return a list of that item
  """
  def quicksort([a]) do
    [a]
  end

  @doc """
  Do the actual work of quicksort,
  """
  def quicksort(lst) do
    {l,p,h} = partition(lst)
    quicksort(l) ++ [p | quicksort(h)]
  end

  @doc """
  A simple driver method showing examples of use
  """
  def main do
    aa=1013397
    Enum.map(1..aa, fn _a -> :rand.uniform(aa)+10000 end)
      |> quicksort
      |> IO.inspect
  end
end

QSort.main