Quick Sort Algorithm in Scala

1. Introduction

Quick Sort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

2. Implementation Steps

1. Choose a pivot from the array.

2. Partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

3. Recursively apply the step 1 and 2 to the sub-arrays.

4. Combine the sub-arrays and pivot to form a sorted array.

3. Implementation in Scala

object QuickSort {
  def quickSort(lst: List[Int]): List[Int] = {
    if (lst.length <= 1) lst
    else {
      val pivot = lst(lst.length / 2)
      quickSort(lst.filter(_ < pivot)) ++
      lst.filter(_ == pivot) ++
      quickSort(lst.filter(_ > pivot))
    }
  }
}

Client Code:

val numbers = List(64, 25, 12, 22, 11)
println("Original List: " + numbers)
val sortedList = QuickSort.quickSort(numbers)
println("Sorted List: " + sortedList)

Output:

Original List: List(64, 25, 12, 22, 11)
Sorted List: List(11, 12, 22, 25, 64)

Explanation:

1. object QuickSort: This is the singleton object for the Quick Sort algorithm in Scala.

2. quickSort(lst: List[Int]): A recursive function that sorts a list using the Quick Sort algorithm.

3. val pivot = lst(lst.length / 2): Choosing the middle element as the pivot.

4. lst.filter(_ < pivot): This filters elements from the list that are less than the pivot.

5. lst.filter(_ == pivot): This filters the pivot elements from the list.

6. lst.filter(_ > pivot): This filters elements from the list that are greater than the pivot.

7. ++: This is the concatenation operator in Scala used to join lists.

8. Client Code: Demonstrates how to use the QuickSort object to sort a list of integers.

The Quick Sort algorithm uses a divide-and-conquer approach to select a pivot and partition the list into two sub-lists, which are then sorted recursively. This process continues until the list is fully sorted.