Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Kotlin

1 min

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

Section I: Introduction to Data Structures & Algorithms

Section 1: 2 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 8 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 6 chapters
Show chapters Hide chapters

14. O(n²) Sorting Algorithms
Written by Matei Suica, Kelvin Lau and Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now

O(n²) time complexity is not great performance, but the sorting algorithms in this category are easy to understand and useful in some scenarios. These algorithms are space efficient, and they only require constant O(1) additional memory space. For small data sets, these sorts compare favorably against more complex sorts. It’s usually not recommended to use O(n²) in production code, but you’ll need to start somewhere, and these algorithms are a great place to start.

In this chapter, you’ll look at the following sorting algorithms:

  • Bubble sort.
  • Selection sort.
  • Insertion sort.

All of these are comparison-based sorting methods. In other words, they rely on a comparison method, such as the less than operator, to order elements. You measure a sorting technique’s general performance by counting the number of times this comparison gets called.

Bubble sort

One of the simplest sorts is the bubble sort. The bubble sort repeatedly compares adjacent values and swaps them, if needed, to perform the sort. The larger values in the set will, therefore, bubble up to the end of the collection.

Example

Consider the following hand of cards, and suppose you want to sort them in ascending order:

Implementation

To get started, open the starter project for this chapter. Because you already know that you’ll need to do a lot of swapping, the first thing you need to do is write an extension for ArrayList to swap elements.

fun <T> ArrayList<T>.swapAt(first: Int, second: Int) {
  val aux = this[first]
  this[first] = this[second]
  this[second] = aux
}

fun <T : Comparable<T>> ArrayList<T>.bubbleSort(showPasses: Boolean = false) {
  // 1
  if (this.size < 2) return
  // 2
  for (end in (1 until this.size).reversed()) {
    var swapped = false
    // 3
    for (current in 0 until end) {
      if (this[current] > this[current + 1]) {
        // 4
        this.swapAt(current, current + 1)
        swapped = true
      }
    }
    // 5 
    if(showPasses) println(this)
    // 6
    if (!swapped) return
  }
}

"bubble sort" example {
  val list = arrayListOf(9, 4, 10, 3)
  println("Original: $list")
  list.bubbleSort(true)
  println("Bubble sorted: $list")
}

---Example of bubble sort---
Original: [9, 4, 10, 3]
[4, 9, 3, 10]
[4, 3, 9, 10]
[3, 4, 9, 10]
Bubble sorted: [3, 4, 9, 10]

Selection sort

Selection sort follows the basic idea of bubble sort but improves upon this algorithm by reducing the number of swapAt operations. Selection sort only swaps at the end of each pass. You’ll see how that works in the following implementation.

Example

Assume you have the following hand of cards:

Implementation

In src ▸ selectionsort, create a new file named SelectionSort.kt. Since you added the swapAt() extension for the bubble sort, you’ll leverage it here too.

fun <T : Comparable<T>> ArrayList<T>.selectionSort(showPasses: Boolean = false) {

  if (this.size < 2) return
  // 1
  for (current in 0 until (this.size - 1)) {
    var lowest = current
    // 2
    for (other in (current + 1) until this.size) {
      if (this[lowest] > this[other]) {
        lowest = other
      }
    }
    // 3
    if (lowest != current) {
      this.swapAt(lowest, current)
    }
    // 4
    if(showPasses) println(this)
  }
}

"selection sort" example {
  val list = arrayListOf(9, 4, 10, 3)
  println("Original: $list")
  list.selectionSort(true)
  println("Bubble sorted: $list")
}

---Example of selection sort---
Original: [9, 4, 10, 3]
[3, 4, 10, 9]
[3, 4, 10, 9]
[3, 4, 9, 10]
Bubble sorted: [3, 4, 9, 10]

Insertion sort

Insertion sort is a more useful algorithm. Like bubble sort and selection sort, insertion sort has an average time complexity of O(n²), but the performance of insertion sort can vary. The more the data is already sorted, the less work it needs to do. Insertion sort has a best time complexity of O(n) if the data is already sorted.

Example

The idea of insertion sort is like how you’d sort a hand of cards. Consider the following hand:

Implementation

In src ▸ selectionsort of your starter project, create a new file named InsertionSort.kt. Write the following inside of the file:

fun <T : Comparable<T>> ArrayList<T>.insertionSort(showPasses: Boolean = false) {
  if (this.size < 2) return
  // 1
  for (current in 1 until this.size) {
    // 2
    for (shifting in (1..current).reversed()) {
      // 3
      if (this[shifting] < this[shifting - 1]) {
        this.swapAt(shifting, shifting - 1)
      } else {
        break
      }
    }
    // 4
    if(showPasses) println(this)
  }
}

"insertion sort" example {
  val list = arrayListOf(9, 4, 10, 3)
  println("Original: $list")
  list.insertionSort(true)
  println("Bubble sorted: $list")
}

---Example of insertion sort---
Original: [9, 4, 10, 3]
[4, 9, 10, 3]
[4, 9, 10, 3]
[3, 4, 9, 10]
Bubble sorted: [3, 4, 9, 10]

Generalization

In this section, you’ll generalize these sorting algorithms for list types other than ArrayList. Exactly which list types won’t matter, as long as they’re mutable since you need to be able to swap elements. The changes are small and simple but important. You always want your algorithms to be as generic as possible.

fun <T> MutableList<T>.swapAt(first: Int, second: Int)

fun <T : Comparable<T>> MutableList<T>.bubbleSort(showPasses: Boolean = false)

fun <T : Comparable<T>> MutableList<T>.selectionSort(showPasses: Boolean = false)

fun <T : Comparable<T>> MutableList<T>.insertionSort(showPasses: Boolean = false)

Challenges

Challenge 1: To the left, to the left

Given a list of Comparable elements, bring all instances of a given value in the list to the right side of the array.

Solution 1

The trick to this problem is to find the elements that need to be moved and shift everything else to the left. Then, return to the position where the element was before, and continue searching from there.

fun<T: Comparable<T>> MutableList<T>.rightAlign(element: T) {
  // 1
  if(this.size < 2) return
  // 2
  var searchIndex = this.size - 2
  while(searchIndex >= 0) {
    // 3
    if(this[searchIndex] == element) {
      // 4
      var moveIndex = searchIndex
      while(moveIndex < this.size - 1 &&
        this[moveIndex + 1] != element) {
        swapAt(moveIndex, moveIndex + 1)
        moveIndex++
      }
    }
    // 5
    searchIndex--
  }
}

Challenge 2: Duplicate finder

Given a list of Comparable elements, return the largest element that’s a duplicate in the list.

Solution 2

Finding the biggest duplicated element is rather straightforward. To make it even easier, you can sort the list with one of the methods you’ve already implemented.

fun<T: Comparable<T>> MutableList<T>.biggestDuplicate(): T? {
  // 1
  this.selectionSort()
  // 2
  for(i in (1 until this.size).reversed()) {
    // 3
    if(this[i] == this[i - 1]) {
      return this[i]
    }
  }
  return null
}

Challenge 3: Manual reverse

Reverse a list of elements by hand. Do not rely on reverse or reversed; you need to create your own.

Solution 3

Reversing a collection is also quite straightforward. Using the double reference approach, you start swapping elements from the start and end of the collection, making your way to the middle.

fun<T: Comparable<T>> MutableList<T>.rev() {

  var left = 0
  var right = this.size - 1

  while (left < right) {
    swapAt(left, right)
    left++
    right--
  }
}

Key points

  • n² algorithms often have a terrible reputation, but some of these algorithms usually have some redeeming points. insertionSort can sort in O(n) time if the collection is already in sorted order and gradually scales down to O(n²).
  • insertionSort is one of the best sorts in situations wherein you know ahead of time that your data is in sorted order.
  • Design your algorithms to be as generic as possible without hurting the performance.
13. Priority Queues
15. Merge Sort
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2023 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now