# Quick Sort - Ruby

Mar 19th, 2016
50
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #! /usr/bin/env ruby
2.
3. # str is array of chars
4. # pivot point is index in array to pivot on
5. # returns type like `str`
6. def quicksort(str, pivot_point)
7.     strlen = str.length
8.
9.     # recursion terminating condition:
10.     return str if strlen <= 1
11.
12.     # find the pivot character
13.     pivot_char = str[pivot_point]
14.
15.     # make new arrays for left and right of pivot
16.     # note: I'm very much aware that this is not the most efficient method,
17.     # but it WILL make it easier to understand the concept of quicksort before
18.     # I proceed to cover the in-place version
19.     left = []
20.     right = []
21.
22.     # go through all the elements, put the ones smaller than pivot_char on the left;
23.     # ...bigger on the right.
24.     for i in 0...strlen # exclusive range: 0 to one less than str's length
25.         next if i == pivot_point # skip over the pivot, we don't want to put it anywhere
26.         # because it'll already be in final position at the end of the function.
27.
28.         if str[i] < pivot_char
29.             left << str[i]
30.         else
31.             right << str[i]
32.         end
33.     end
34.
35.     # utilize recursion to sort the left and right arrays, until the partitions become
36.     # a singular-element array or an empty one.
37.     left = quicksort(left, rand(left.length))
38.     right = quicksort(right, rand(right.length))
39.
40.     # overwrite the original str and drop the new stuff in, in order
41.     str = []
42.     str << left << pivot_char << right
43.
44.     return str.flatten # flatten because we pushed an array, a character/one-letter-string, and another array
45.     # FYI: flatten makes a 2+D array 1D.
46.
47. end
48.
49. puts "give me a string"
50. str = gets.chomp.split('')
51.
52. puts quicksort(str, rand(str.length)).join('')
RAW Paste Data