oaktree

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