A list can be iterated as follows:
scala> val thrill = "Will" :: "fill" :: "until" :: Nilval thrill: List[String] = List(Will, fill, until)scala> thrill.map(s => s + "y")val res14: List[String] = List(Willy, filly, untily)The above code first creates a list and then the second command creates a map with an iterable called as 's', the map creates a new string from 's' by appending the char 'y'.
However, I do not understand the following iteration process:
scala> thrill.sortWith((s,t) => s.charAt(0).toLower < t.charAt(0).toLower)val res19: List[String] = List(fill, until, Will)Does the tuple (s,t) take two elements of thrill at once and compares them? How is sorting performed exactly using this syntax/function?
Best Answer
Yes the function compares two elements at a time to determine their ordering.
The implementation of sortWith falls back on Java's Array.sort (docs) with the following signature
sort(T[] a, Comparator<? super T> c)which takes in an Array of T and a comparator, equipped with a binary function that can compare any two elements of the set of possible values of T and give you some information about how they relate to each other (as in should come before, same or after based on your function).
Behind the scenes it is really just an iterative merge sort details of which can be found on the wikipedia page for merge sort
Leaving the optimizations aside, if you aren't familiar with it, merge sort, which is a divide and conquer algorithm, simply breaks down the collection you have until you have groups of 2 elements and then merges the smaller lists in a sorted way simply by comparing 2 elements at a time, which is where the binary comparison function you pass in comes to play.
i.e.
List(4, 11, 2, 1, 9, 0) //original listBreak down to chunks:
[4, 11], [2, 1], [9, 0]Sort internally:
[4, 11], [1, 2], [0, 9]Merge:
[1, 4, 11], [2], [0, 9][1, 2, 4, 11], [0, 9][0, 1, 2, 4, 11], [9][0, 1, 2, 4, 9, 11]P.S. a nit picky detail, sortedWith takes in a Function2 (a function of arity 2). This function you pass in is used to generate what we call an Ordering in Scala, which is then implicity converted to a Comparator. Above, I have linked to the implementation of sorted which is what sortedWith calls once it generates this ordering and which is where most of the sorting logic happens.
Sorting is arranging the data in ascending or descending order. Sorted data helps us searching easily.Scala uses TimSort, which is a hybrid of Merge Sort and Insertion Sort.
Here is signature of sortWith function in scala -
def sortWith(lt: (A, A) => Boolean): Repr
The sortWith function Sorts this sequence according to a comparison function. it takes a comparator function and sort according to it.you can provide your own custom comparison function.
It will perform Tim Sort on the input list to result sorted output.