java 39 lines · 7 steps

Quicksort with Lomuto partitioning in Java

A recursive in-place sort that partitions around a pivot and conquers each half.

Explained by highlit

Intermediate recursion divide-and-conquer in-place partitioning sorting

1public final class Quicksort {
2 
  private Quicksort() {
  }
5 
  public static void sort(int[] array) {
      if (array == null || array.length < 2) {
          return;
      }
      quicksort(array, 0, array.length - 1);
  }
12 
  private static void quicksort(int[] array, int low, int high) {
      if (low < high) {
          int pivotIndex = partition(array, low, high);
          quicksort(array, low, pivotIndex - 1);
          quicksort(array, pivotIndex + 1, high);
      }
  }
20 
  private static int partition(int[] array, int low, int high) {
      int pivot = array[high];
      int i = low - 1;
      for (int j = low; j < high; j++) {
          if (array[j] <= pivot) {
              i++;
              swap(array, i, j);
          }
      }
      swap(array, i + 1, high);
      return i + 1;
  }
33 
  private static void swap(int[] array, int a, int b) {
      int temp = array[a];
      array[a] = array[b];
      array[b] = temp;
  }
39}

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

1Quicksort sorts in place by recursively partitioning subranges around a chosen pivot.
2The Lomuto scheme keeps everything ≤ the pivot to the left, then drops the pivot into its final slot.
3Guarding the public entry point against null and tiny arrays keeps the recursive core simple.

Related explainers

java

public interface GitHubClient {
 
    @GetExchange("/users/{username}")
    GitHubUser getUser(@PathVariable String username);

Declarative HTTP clients in Spring

http-client declarative-api proxy

Intermediate 8 steps

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

Building a trie for autocomplete in Java

trie prefix-tree recursion

Intermediate 8 steps

ruby

class KeyTransformer
  def self.camelize(data)
    new.camelize(data)
  end

Recursively camelizing nested Ruby data

recursion data-transformation pattern-matching

Intermediate 7 steps

java

@RestController
@RequestMapping("/api/products")
public class ProductSearchController {

Binding collection query params in Spring

rest-api query-parameters dependency-injection

Intermediate 6 steps

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

Evaluating math expressions with two stacks

stacks parsing operator-precedence

Intermediate 9 steps

java

@Entity
@Table(name = "orders")
@SQLDelete(sql = "UPDATE orders SET deleted = true, deleted_at = now() WHERE id = ?")
@Where(clause = "deleted = false")