1require "spec_helper"
 2
 3# average case: O(n logn)
 4# worst case: O(n^2)
 5# Quick sort is a divide and conquer algorithm.
 6# Base case: 0,1 elements in the array
 7# First divide the list into two smaller lists (high list, and low list)
 8# 1. pick a pivot value.
 9# 2. move items smaller than pivot into smaller list, and greater into greater list.
10# 3. recursively split up lists until the base case
11# 4. combine the lesser list with the greater list
12describe QuickSort do
13  subject { QuickSort.new }
14
15  it "should sort an empty array" do
16    expect(subject.sort([])).to eq([])
17  end
18
19  it "should sort an array with one item" do
20    expect(subject.sort([1])).to eq([1])
21  end
22
23  it "should sort an array of numbers" do
24    n = 600
25    numbers = Array.new(n) { rand(n) }
26    sorted_numbers = numbers.sort
27    Benchmark.bmbm do |x|
28      x.report("quick sort") { expect(subject.sort(numbers)).to eq(sorted_numbers) }
29    end
30  end
31end