Sélection trier dans Scala fonctionnel

Je pense que c'est raisonnablement possible de faire une sélection dans un style fonctionnel, mais comme Daniel l'indiquait, il a de bonnes chances d'accomplir horriblement.

Je viens de m'essayer de la main d'une bulle fonctionnelle, comme un peu Un cas de sélection plus simple et dégénéré. Voici ce que j'ai fait, et cela sugviennent à ce que vous pouviez faire: p> xxx pré>

une fois que c'est fini recouvrant, le plus grand élément est à la fin de la liste. Maintenant, P>

Break list into two sub-lists, 
either by counting off half the elements into one sublist 
  and the rest in the other,
or by copying every other element from the original list 
  into either of the new lists.

Sort each of the two smaller lists (recursion here, obviously).

Assemble a new list by selecting the smaller from the front of either sub-list
until you've exhausted both sub-lists.

Merci pour les indices ci-dessus, ils étaient très inspirants. Voici une autre approche fonctionnelle de l'algorithme de tri de sélection. J'ai essayé de le baser sur l'idée suivante: la recherche d'un max / min peut être faite assez facilement par min (a) = si a = nil -> int.maxvalue d'autre min (A.Head, min (A.tail ))) code>. Le premier min est la min d'une liste, la seconde la minute de deux chiffres. Ceci est facile à comprendre, mais malheureusement pas à la queue récursive. Utilisation de la méthode de l'accumulateur La définition MIN peut être transformée comme ceci, maintenant dans la correction SCALA:

def ssort(xs: List[Int], accu: List[Int]): List[Int] = minl(xs) match {
    case Nil => accu
    case min :: rest => ssort(rest, min::accu)
}

Voici une autre implémentation de la sélection de sélection (version générique).

def less[T <: Comparable[T]](i: T, j: T) = i.compareTo(j) < 0

def swap[T](xs: Array[T], i: Int, j: Int) { val tmp = xs(i); xs(i) = xs(j); xs(j) = tmp }

def selectiveSort[T <: Comparable[T]](xs: Array[T]) {
    val n = xs.size
    for (i <- 0 until n) {
        val min = List.range(i + 1, n).foldLeft(i)((a, b) => if (less(xs(a), xs(b))) a else b)
        swap(xs, i, min)
    }
  }     

Voici mon point de vue sur ce problème: sélectionsort. SCALA

def selectionsort[A <% Ordered[A]](list: List[A]): List[A] = {
  def sort(as: List[A], bs: List[A]): List[A] = as match {
    case h :: t => select(h, t, Nil, bs)
    case Nil => bs
  }

  def select(m: A, as: List[A], zs: List[A], bs: List[A]): List[A] = 
    as match {
      case h :: t => 
        if (m > h) select(m, t, h :: zs, bs)
        else select(h, t, m :: zs, bs)
      case Nil => sort(zs, m :: bs)
    }

  sort(list, Nil)
}

même si, lorsque vous préférez Scala, je préfère préférer le style de programmation fonctionnelle (via des combinaisons ou une récursivité) sur un style impératif (via des variables et des itérations), cette fois, pour ce problème spécifique, les boucles imbriquées de l'ancienne écolière entraînent Code plus simple et plus performant.

Je ne pense pas que la retouche au style impératif est une erreur de certains classes de problèmes, tels que le tri des algorithmes qui transforment généralement le tampon d'entrée en place plutôt que sur une nouvelle collection. p>

Ma solution est la suivante: p> xxx pré>

Comme vous pouvez le constater, pour atteindre le polymorphisme paramétrique, plutôt que d'utiliser java.lang.cablable code>, J'ai préféré scala.math.Ordered code> et Scala View limites plutôt que les limites supérieures. Cela fonctionne certainement grâce à des conversions implicites Scala implicites de types primitifs vers des wrappers riches. P>

Vous pouvez écrire un programme client comme suit: P>

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new SelectionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))

Un programme fonctionnel simple pour la sélection - Trier dans SCALA

def selectionSort(list:List[Int]):List[Int] = {
  @tailrec
  def selectSortHelper(list:List[Int], accumList:List[Int] = List[Int]()): List[Int] = {

    list match {
      case Nil => accumList
      case _ => {
        val min  = list.min
        val requiredList = list.filter(_ != min)
        selectSortHelper(requiredList, accumList ::: List.fill(list.length - requiredList.length)(min))
      }
    }
  }
  selectSortHelper(list)
}

Voici ma solution

def sort(list: List[Int]): List[Int] = {
    @tailrec
    def pivotCompare(p: Int, l: List[Int], accList: List[Int] = List.empty): List[Int] = {
      l match {
        case Nil              => p +: accList
        case x :: xs if p < x => pivotCompare(p, xs, accList :+ x)
        case x :: xs          => pivotCompare(x, xs, accList :+ p)
      }
    }
    @tailrec
    def loop(list: List[Int], accList: List[Int] = List.empty): List[Int] = {
      list match {
        case x :: xs =>
          pivotCompare(x, xs) match {
            case Nil       => accList
            case h :: tail => loop(tail, accList :+ h)
          }
        case Nil => accList
      }
    }

    loop(list)
  }