Sorter traits

package com.shockang.study.algorithm.archive.sort

trait Sorter {
  def sort(a: Array[Int])

  protected def swap(a: Array[Int], i: Int, j: Int) :Unit = {
    val tmp = a(i)
    a(i) = a(j)
    a(j) = tmp
  }
}
Copy the code

Three O(n^2) sorting algorithms

Bubble sort

package com.shockang.study.algorithm.archive.sort.bubble

import com.shockang.study.algorithm.archive.sort.Sorter

/** ** ** @author Shockang */
class BubbleSorter extends Sorter {
  override def sort(a: Array[Int) :Unit = {
    if (a == null || a.length < 2) return
    // I traverses each array element from left to right, and j bubbles from right to left
    for (i <- a.indices; j <- i - 1 to 0 by - 1) {
      if (a(j) > a(j + 1)) swap(a, j, j + 1)}}}Copy the code

Insertion sort

package com.shockang.study.algorithm.archive.sort.insert

import com.shockang.study.algorithm.archive.sort.Sorter

/** * insert sort ** @author Shockang */
class InsertSorter extends Sorter {
  override def sort(a: Array[Int) :Unit = {
    if (a == null || a.length < 2) return
    val n = a.length
    // I iterates through each array element from left to right, skipping the first element
    for (i <- 1 until n) {
      val num = a(i)
      var j = i
      // j inserts from right to left
      while (j > 0 && a(j - 1) > a(j)) {
        // Move to the right to make room for inserts
        a(j - 1) = a(j)
        j -= 1
      }
      / / insert
      a(j) = num
    }
  }
}

Copy the code

Selection sort

package com.shockang.study.algorithm.archive.sort.select

import com.shockang.study.algorithm.archive.sort.Sorter

/** * select sort ** @author Shockang */
class SelectSorter extends Sorter {
  override def sort(a: Array[Int) :Unit = {
    if (a == null || a.length < 2) return
    val n = a.length
    // I iterates through each array element from left to right
    for (i <- 0 until n) {
      var min = Int.MaxValue
      // j selects the smallest value from left to right
      for (j <- i until n) {
        min = math.min(min, a(j))
      }
      a(i) = min
    }
  }
}

Copy the code

Three O(nlogn) sorting algorithms

Merge sort

package com.shockang.study.algorithm.archive.sort.merge

import com.shockang.study.algorithm.archive.sort.Sorter

/** * @author Shockang */
class MergeSorter extends Sorter {
  override def sort(a: Array[Int) :Unit = {
    if (a == null || a.length < 2) return
    mergeSort(a, 0, a.length - 1)}/** * merge sort ** @param a sorted array * @param low left margin * @param high right margin */
  def mergeSort(a: Array[Int], low: Int, high: Int) :Unit = {
    if (low < high) {
      // Take the index of the middle element
      val mid = low + ((high - low) >> 1)
      mergeSort(a, low, mid)
      mergeSort(a, mid + 1, high)
      merge(a, low, mid, high)
    }
  }

  /** * merge ** @param a sorted array * @param low * @param mid index of the middle element * @param high right */
  def merge(a: Array[Int], low: Int, mid: Int, high: Int) = {
    // Move the elements from low to mid in a to a new array, and place a sentinel on the last element of the new array
    val a1 = new Array[Int](mid - low + 2)
    for (i <- 0 to a1.length - 2) {
      a1(i) = a(low + i)
    }
    a1(a1.length - 1) = Int.MaxValue
    // Add a sentry to the last element of the new array
    val a2 = new Array[Int](high - mid + 1)
    for (i <- 0 to a2.length - 2) {
      a2(i) = a(mid + 1 + i)
    }
    a2(a2.length - 1) = Int.MaxValue
    // The elements of the two new arrays are compared and placed in the original array, because the presence of the sentry reduces the comparison
    var i, j = 0
    for (k <- low to high) {
      if (a1(i) <= a2(j)) {
        a(k) = a1(i)
        i += 1
      } else {
        a(k) = a2(j)
        j += 1}}}}Copy the code

Quick sort

package com.shockang.study.algorithm.archive.sort.quick

import com.shockang.study.algorithm.archive.sort.Sorter

/** ** quicksort ** @author Shockang */
class QuickSorter extends Sorter {
  override def sort(a: Array[Int) :Unit = {
    if (a == null || a.length < 2) return
    quickSort(a, 0, a.length - 1)}/** * quick sort ** @param a to sort array * @param low left margin * @param high right margin */
  def quickSort(a: Array[Int], low: Int, high: Int) :Unit = {
    if (low < high) {
      val curPoint = getCutPoint(a, low, high)
      quickSort(a, low, curPoint)
      quickSort(a, curPoint + 1, high)
    }
  }

  ** @param a sorted array * @param low left margin * @param high right margin * @return */
  def getCutPoint(a: Array[Int], low: Int, high: Int) :Int = {
    // The initial split point is the middle value of left, middle and right, which is more efficient
    val curPoint = getMedianValue(a(low), a(high), a(low + ((high - low) >> 1)))
    var l = low
    var r = high
    while (l < r) {
      // Find the index of the first element smaller than the cut point from right to left
      while (l < r && a(r) >= curPoint) r -= 1
      // Find the index of the first element greater than the point of segmentation from left to right
      while (l < r && a(l) <= curPoint) l += 1
      / / exchange
      if (l < r) swap(a, l, r)
    }
    a(l) = curPoint
    l
  }

  def getMedianValue(a: Int, b: Int, c: Int) :Int = {
    if ((b - a) * (a - c) >= 0) a
    else if ((a - b) * (b - c) >= 0) b
    else c
  }
}
Copy the code

Heap sort

package com.shockang.study.algorithm.archive.sort.heap

import com.shockang.study.algorithm.archive.sort.Sorter

import scala.util.control.Breaks. _/** * heap sort ** @author Shockang */
class HeapSorter extends Sorter {
  override def sort(a: Array[Int) :Unit = {
  	if (a == null || a.length < 2) return
    // Adjust the structure from bottom to top and from right to left from the first non-leaf node
    for (i <- (a.length - 1) / 2 to 0 by - 1) {
      adjustHeap(a, i, a.length)
    }
    // Adjust the heap structure + swap the top element and the end element
    for (i <- a.length - 1 until 0 by - 1) {
      // Swap the top element with the end element
      swap(a, 0, i)
      // Resize the heap
      adjustHeap(a, 0, i)
    }
  }

  /** * adjust heap ** @param a to be sorted * @param parent parent * @param length To be sorted last element index */
  private def adjustHeap(a: Array[Int], parent: Int, length: Int) :Unit = {
    // Use temp as the parent node
    val temp = a(parent)
    / / the left child
    var lChild = 2 * parent + 1
    var p = parent
    breakable(while (lChild < length) {
      / / right child
      val rChild = lChild + 1
      If there is a right child and the value of the right child is greater than that of the left child, select the right child
      if (rChild < length && a(lChild) < a(rChild)) lChild += 1
      // If the value of the parent node is already greater than the value of the child node, it ends
      if (temp >= a(lChild)) break
      // Assign the value of the child to the parent
      a(p) = a(lChild)
      // Select the left child of the child node and continue filtering down
      p = lChild
      lChild = 2 * lChild + 1
    })
    a(p) = temp
  }
}

Copy the code

A single measurement

Why do I dare say my sorting algorithmAbsolutely rightNo problem at all, because of the unit test cases I wrote

package com.shockang.study.algorithm.archive.sort.main

import com.shockang.study.algorithm.archive.sort.Sorter
import com.shockang.study.algorithm.archive.sort.bubble.BubbleSorter
import com.shockang.study.algorithm.archive.sort.insert.InsertSorter
import com.shockang.study.algorithm.archive.sort.merge.MergeSorter
import com.shockang.study.algorithm.archive.sort.quick.QuickSorter
import com.shockang.study.algorithm.archive.sort.select.SelectSorter

import scala.util.Random

object Main extends App {
  assertSorter(new BubbleSorter)
  assertSorter(new InsertSorter)
  assertSorter(new SelectSorter)
  assertSorter(new MergeSorter)
  assertSorter(new QuickSorter)
  assertSorter(new HeapSorter)

  private def assertSorter(sorter: Sorter) :Unit = {
    println(format(s"Start to assert:${sorter.getClass.getSimpleName}"))
    assertNull(sorter)
    for(_ < -Range(0.100)) assertArray(sorter, generateRandomArray())
    println(format(s"Succeed to assert:${sorter.getClass.getSimpleName}"))}private def assertNull(sorter: Sorter) {
    assertArray(sorter, null)
    assertArray(sorter, new Array[Int] (0))}private def assertArray(sorter: Sorter, a: Array[Int) :Unit = {
    sorter.sort(a)
    assert(checkArray(a))
  }

  private def generateRandomArray() :Array[Int] = {
    val n = Random.nextInt(10000)
    val a = new Array[Int](n)
    for (i <- a.indices) {
      a(i) = Random.nextInt()
    }
    a
  }

  private def checkArray(a: Array[Int) :Boolean = {
    if (a == null) return true
    var pre = Int.MinValue
    for (num <- a) {
      if (num < pre) return false
      pre = num
    }
    true
  }

  private def format(s: String) :String = {
    val str = "-" * 10
    str + s + str
  }
}
Copy the code

Console output

----------Start to assert:BubbleSorter----------
----------Succeed to assert:BubbleSorter----------
----------Start to assert:InsertSorter----------
----------Succeed to assert:InsertSorter----------
----------Start to assert:SelectSorter----------
----------Succeed to assert:SelectSorter----------
----------Start to assert:MergeSorter----------
----------Succeed to assert:MergeSorter----------
----------Start to assert:QuickSorter----------
----------Succeed to assert:QuickSorter----------
----------Start to assert:HeapSorter----------
----------Succeed to assert:HeapSorter----------
Copy the code

It can be seen that a hundred consecutive tests support the sorting of up to 10,000 random integers each time. In this case, the sorting algorithm logic is absolutely correct.