1. Introduction
Quick sort is an efficient sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
2. Implementation Steps
1. Choose a 'pivot' element from the array and partition the remaining elements into two sub-arrays, according to whether they are less than or greater than the pivot.
2. Recursively apply the above step to the sub-arrays.
3. The base case of the recursion is an array of size zero or one, which are considered to be sorted.
3. Implementation in Ruby Programming
def quick_sort(arr)
return arr if arr.length <= 1
# Choosing the pivot
pivot = arr.delete_at(rand(arr.length))
# Partitioning the array
left, right = arr.partition { |x| x < pivot }
# Recursive call
quick_sort(left) + [pivot] + quick_sort(right)
end
# Client code
array = [34, 2, 10, 19, 7, 50, 32]
puts "Original array: #{array}"
sorted_array = quick_sort(array)
puts "Sorted array: #{sorted_array}"
Output:
Original array: [34, 2, 10, 19, 7, 50, 32] Sorted array: [2, 7, 10, 19, 32, 34, 50]
Explanation:
1. The primary operation in the quick sort algorithm is the partitioning of the array. A random element called the pivot is selected from the array.
2. The array is then partitioned into two sets - one with elements less than the pivot and the other with elements greater than the pivot.
3. These two sets are then sorted recursively using the same process.
4. The sorted set with elements less than the pivot, the pivot, and the sorted set with elements greater than the pivot are concatenated to give the final sorted array.
5. This process continues until the base case is reached, which is an array of size zero or one.
Comments
Post a Comment