Sorting Algorithm

Question 1

Selection Sort

Answer 1

Time Complexity: O(n^2)

def selection_sort(a)
return “No Elements” if a.size == 0
for i in (0…a.size) do
for j in (i+1…a.size) do
switch(a, i, j) if a[i] > a[j]
end
end
return a
end

def switch(a, i, j)
 temp = a[i]
 a[i] = a[j]
 a[j] = temp
end

Question 2

Bubble Sort

Answer 2

Time Complexity: O(n^2)

def bubble\_sort(a)
 return "No Elements Found" if a.size == 0
n = a.size-1
swapped = false 
 for i in (0...n) do
 for j in (0...n-i) do
 switch(a, j, j+1) if a[j] \> a[j+1]
 swapped = true;
 end
 break if swapped == false
end
 return a
 end

Question 3

Shell Sort

Answer 3

Time Complexity: O(n^2)

def shell\_sort(a)
return "No Elements Found" if a.size == 0
 h=1
 n= a.size
 while (h<n><span class="c6">3</span><span class="c5">)<br> h= (</span><span class="c6">3</span><span class="c5">*h)+</span><span class="c6">1</span><br> <span class="c5"> end</span><br> <br> <span class="c13">while</span><span class="c5"> </span><span class="c13">h</span><span class="c5"> &gt; </span><span class="c13">0</span><br> <span class="c5"> for i in h...n<br> j=i<br> while (j &gt;=h)<br> switch(a,j,j-h) if a[j] &lt; a[j-h]<br> j -= h<br> end<br> </span><span class="c13">end</span><br> <span class="c5"> h/= </span><span class="c6">3</span><br> <span class="c5">end</span><br> <span class="c13">return</span><span class="c5"> </span><span class="c13">a</span><br> <span class="c5">end</span></n>

Question 4

Insertion Sort

Answer 4

Time Complexity: O(n²)

Space Complexity: O(1)

def insertion_sort(a)
return “No elements found” if a.size == 0
for i in (0…a.size) do
t = a[i]
j = i - 1
while j >= 0 && a[j] > t
a[j+1] = a[j]
j -= 1
end
j += 1
a[j] = t
end
return a
end

Question 5

Quicksort

Answer 5

Time Complexity: O(n²)

def quick_sort(a, s,l)
return if s >= l
i = partition(a, s, l)
quick_sort(a,s,i-1)
quick_sort(a,i+1,l)
return a
end

def partition(a, s, l)
pivot = a[l]
p_index = s
(s…l).each do |i|
if a[i] <= pivot
switch(a, i, p_index)
p_index += 1
end
end
switch(a, p_index, l)
return p_index
end

def switch(a, i, j)
 temp = a[i]
a[i] = a[j]
a[j] = temp
end

Question 6

Merge Sort

Answer 6

Time Complexity: O(n*Log n)

Auxiliary Space: O(n)

def merge\_sort(a)
return a if a.size == 1
 h = (a.size/2).round
 a1 = a.take(h)
 a2 = a.drop(h)

 l = merge\_sort(a1)
 r = merge\_sort(a2)
return merge(l,r)
 end

def merge(a, b)
q = Array.new
while a.size > 0 and b.size > 0
if a[0] <= b[0]
q << a.shift()
else
q << b.shift()
end
end

while a.size > 0
q << a.shift()
end

while b.size > 0
q << b.shift()
end
return q
end