Computer Science‎ > ‎

Basic Data Structures in Ruby - Insertion Sort



Programming With Ruby


Insertion Sort


The Insertion Sort is a popular quadratic sorting algorithm, which has been discussed in detail, with examples and C code over here : Arrays and Sorting: Insertion Sort ( with C Program source code). In this tutorial, we will take a quick look at the ruby implementation of Insertion Sort.

# Insertion Sort ************************
# Insertion Sort -> A popular quadratic sorting algorithm with O(n^2) complexity
def insertionSort(arr)
    for size in 2..arr.length
        # Remember, this is a zero-start array
        element = arr[size-1]   

        # Bring this element down to its appropriate position
        # elements[0] ... elemets[size-2] are already in a sorted order
        index = size - 2
        while(index >0) && (element < arr[index])
            arr[index + 1] = arr[index]
            index-=1
        end
        arr[index+1] = element
    end
        
end

puts "Original Array :"
original_array=[2,19,5,4,3,14,2]
p original_array
puts "Sorted Array Using Insertion Sort:"
insertionSort(original_array)
p original_array

=begin
Sample Output :
puts "Original Array :"
original_array=[2,19,5,4,3,14,2]
p original_array
puts "Sorted Array Using Insertion Sort:"
insertionSort(original_array)
p original_array
=end


 


Check out some of our other Ruby Tutorials :

Introduction to Ruby

 Introduction to Ruby and some playing around with the Interactive Ruby Shell (irb) Introduction to Ruby - Conditional statements and Modifiers: If-then, Unless, Case Introduction to Ruby Comments - Single and Multi-Line comments Introduction to Ruby Loops - Using While, Until, For, Break, Next , Redo, Retry
 Introduction to Ruby - Arrays - Sorting, Filtering (Select), Transforming, Multi-Dimensional Arrays Introduction to Ruby - Strings Introduction to Ruby - Making a Script Executable Introduction to Ruby - Regular Expressions, Match, Scan
 Introduction to Ruby - Computing Factorials Recursively : An Example of Recursion Introduction to Ruby - Binomial Coefficients (nCr) : An Example of Recursion Introduction to Ruby - Computing a Power Set : An Example of Recursion Introduction to Ruby - Towers of Hanoi : An Example of Recursion
 Introduction to Ruby - Strings: Substitution, Encoding, Built-In Methods 



Basic Data Structures With Ruby




Programming With Ruby

 Introduction to Ruby and some playing around with the Interactive Ruby Shell (irb)

Introduction to Ruby - Conditional statements and Modifiers: If-then, Unless, Case

Introduction to Ruby Comments - Single and Multi-Line comments

Introduction to Ruby Loops - Using While, Until, For, Break, Next , Redo, Retry

Introduction to Ruby - Arrays - Sorting, Filtering (Select), Transforming, Multi-Dimensional Arrays 

Introduction to Ruby - Strings

Introduction to Ruby - Making a Script Executable

Introduction to Ruby - Regular Expressions, Match, Scan

Introduction to Ruby - Computing Factorials Recursively : An Example of Recursion

Introduction to Ruby - Binomial Coefficients (nCr) : An Example of Recursion

Introduction to Ruby - Computing a Power Set : An Example of Recursion

Introduction to Ruby - Towers of Hanoi : An Example of Recursion

 Introduction to Ruby - Strings: Substitution, Encoding, Built-In Methods

Basic Data Structures in Ruby - Insertion Sort

Basic Data Structures in Ruby - Selection Sort

Basic Data Structures in Ruby - Merge Sort

Basic Data Structures in Ruby - Quick Sort

Functional Programming with Ruby

Basic Data Structures in Ruby - Stack

Basic Data Structures in Ruby - The Queue

Basic Data Structures in Ruby - Linked List - ( A Simple, Singly Linked List)

Basic Data Structures in Ruby - Binary Search Tree