Skip to content

Instantly share code, notes, and snippets.

@Kumassy
Created August 5, 2016 10:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Kumassy/9a18e8c248afb95f9221f34d30a0cd96 to your computer and use it in GitHub Desktop.
Save Kumassy/9a18e8c248afb95f9221f34d30a0cd96 to your computer and use it in GitHub Desktop.
Implementation of quick sort in Ruby
require 'rspec'
def q_sort(list)
list = Array(list)
case list.length
when 0
[]
when 1
list
when 2
if list.first < list.last
list
else
list.reverse
end
else
head = list.first
tail = list.last(list.length - 1)
q_sort(tail.select{|x| x <= head}) + Array(head) + q_sort(tail.select{|x| x > head})
end
end
describe "q_sort" do
it 'should return empty array for nil' do
list = nil
expect(q_sort list).to eq []
end
it 'should return empty array for empty array' do
list = []
expect(q_sort list).to eq []
end
it 'should return same array for 1 length array' do
list = [3]
expect(q_sort list).to eq [3]
end
it 'should sort 2 length array' do
list = [1,6]
expect(q_sort list).to eq [1,6]
end
it 'should sort 2 length array' do
list = [9,6]
expect(q_sort list).to eq [6, 9]
end
it 'should do sort' do
list = [1, 10, 4, 6, 7, 3, 2]
expect(q_sort list).to eq [1, 2, 3, 4, 6, 7, 10]
end
it 'should do sort even containing duplicate value' do
list = [1, 10, 3, 3, 4, 10, 6, 3, 7, 3, 2]
expect(q_sort list).to eq [1, 2, 3, 3, 3, 3, 4, 6, 7, 10, 10]
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment