Kotlinlearncs.online LogoJava

    ← Prev

    Index

    Next →

    Kotlin
    Java

    • Binary Search : 54

    • Quicksort : 53

    • Merge Sort : 52

    • Sorting Algorithms : 51

    • Practice with Recursion : 50

    • Trees and Recursion : 49

    • Trees : 48

    • Recursion : 47

    • Lists Review and Performance : 46

    • Linked Lists : 45

    • Algorithms and Lists : 44

    • Lambda Expressions : 43

    • Anonymous Classes : 42

    • Practice with Interfaces : 41

    • Implementing Interfaces : 40

    • Using Interfaces : 39

    • Working with Exceptions : 38

    • Throwing Exceptions : 37

    • Catching Exceptions : 36

    • References and Polymorphism : 35

    • References : 34

    • Data Modeling 2 : 33

    • Equality and Object Copying : 32

    • Polymorphism : 31

    • Inheritance : 30

    • Data Modeling 1 : 29

    • Companion Objects : 28

    • Encapsulation : 27

    • Constructors : 26

    • Objects, Continued : 25

    • Introduction to Objects : 24

    • Compilation and Immutability : 23

    • Practice with Collections : 22

    • Maps and Sets : 21

    • Lists and Type Parameters : 20

    • Imports and Libraries : 19

    • Multidimensional Arrays : 18

    • Practice with Strings : 17

    • null : 16

    • Algorithms and Strings : 15

    • Strings : 14

    • Functions and Algorithms : 13

    • Practice with Functions : 12

    • More About Functions : 11

    • Errors and Debugging : 10

    • Functions : 9

    • Practice with Loops and Algorithms : 8

    • Algorithms I : 7

    • Loops : 6

    • Arrays : 5

    • Compound Conditionals : 4

    • Conditional Expressions and Statements : 3

    • Operations on Variables : 2

    • Variables and Types : 1

    • Hello, world! : 0

    Quicksort

    import cs125.sorting.quicksort.Partitioner.partition
    val array = arrayOf("you", "are", "not", "alone")
    partition(array)
    println(array.contentDeepToString())

    We continue our discussion of sorting algorithms by introducing the wild child: Quicksort. Quicksort can achieve best-case sorting behavior while using less space than Mergesort. But, Quicksort also has some pathological cases we need to understand. Let’s get started!

    Warm Up Debugging Challenge
    Warm Up Debugging Challenge

    You knew it was coming…

    Partitioning
    Partitioning

    Mergesort was our first recursive sorting algorithm. It employed a bottom-up approach—first breaking the array into individual chunks, and then merging them back together.

    Quicksort is another recursive approach, but it works differently. Let’s first examine its operation at a high level, and then break it down further.

    Like Mergesort, Quicksort is also based on another building block: partitioning. Let’s see how that works:

    You’ll get to complete partition on our next homework! But we can at least experiment with it using the method built-in to our playground:

    // Experiment with partition

    Quicksort
    Quicksort

    Next, first we’ll implement Quicksort. Then we’ll analyze its performance!

    Implementation
    Implementation

    Next, let’s build a recursive sorting algorithm based on Partitioner.partition! Once we have a partition method, completing the implementation is quite straightforward!

    // Quicksort

    Performance Analysis
    Performance Analysis

    Next, let’s use the Quicksort implementation we completed above to experiment with its performance. Surprises are in store!

    // Quicksort Performance Analysis
    import kotlin.random.Random
    fun randomIntArray(length: Int): Array<Int> {
    return Array<Int>(length) { Random.nextInt(128) }
    }
    println(randomIntArray(8).contentDeepToString())

    What’s going on here? Let’s consider things visually.

    Sorting Algorithm Review
    Sorting Algorithm Review

    Let’s review the sorting algorithms we’ve covered together:

    Let’s review salient aspects of sorting performance. Specifically: best and worst case inputs and runtime, and memory usage.

    Sorting Tradeoffs
    Sorting Tradeoffs

    Sorting algorithms represent a fascinating set of tradeoffs between different performance attributes. For example:

    Timsort, the default sorting algorithm used by several languages including Python and Java, actually combines elements of both insertion sort and Mergesort, in addition to some other tricks.

    Sorting Stability
    Sorting Stability

    As a final note, let’s discuss sort algorithm stability. Stability is a desirable property of sorting algorithms. It means that items with equal values will not change positions while the array is sorted.

    Why is stability desirable? Because it allows us to run a sorting algorithm multiple times on complex data and produce meaningful results.

    For example, imagine that want a list of restaurants sorted first by cuisine and then by name. Assuming our sorting algorithm is stable, we can accomplish this by first sorting the list by name and then by cuisine. However, if the sorting algorithm in unstable that second sort by cuisine will destroy the results of the sort by name, and render the combination meaningless.

    Solve: Quicksort Partition (First Value)

    Created By: Geoffrey Challen
    / Version: 2020.6.0

    Create a method fun partition(value: IntArray?) that returns the input array partitioned using the first array value as the pivot. All values smaller than the pivot should precede it in the array, and all values larger than or equal to the pivot should follow it. Your method should return the index of the pivot value. If the array is null or empty you should return -1.

    More Practice

    Need more practice? Head over to the practice page.