1

2 sl = list.clone

3 sl.each_index do |i|

4 ( sl.length - i - 1 ).times do |j|

5 if ( sl[j+1] < sl[j] )

6 sl[j], sl[j+1] = sl[j+1], sl[j]

7 end

8 end

9 end

10 end

11

12 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]

13 p list

14 p bubble_sort(list)

15

Take the first element , compare it to the second element, if the

second is smaller, swap the elements, repeat until you hit the end of

the list. start again , this time repeat till you get to the end of

the list - 1. repeat n times.

Selection Sort:

1

2 sl = list.clone

3 sl.each_index do |i|

4 min = i

5 (i..(sl.size-1)).each do |j|

6 min = j if sl[j] < sl[min]

7 end

8 sl[i], sl[min] = sl[min], sl[i]

9 end

10 end

11

12 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]

13 p list

14 p selection_sort(list)

15

Same as Bubble Sort except that you only swap one element at each pass

Insertion Sort: (in place)

1

2 sl = list.clone

3 sl.each_index do |i|

4 j = i

5 while j > 0 && sl[j] < sl[j-1]

6 sl[j], sl[j-1]= sl[j-1], sl[j]

7 j -=1

8 end

9 end

10 end

11

12 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]

13 p list

14 p insertion_sort(list)

15

Split the list to be sorted into two lists, sorted and unsorted. Start with a sorted list of 1 element and work up until n inserting each new element into its correct place in the sub list. Easily improvable running time.

Merge Sort:

1

2 return ls if ls.size <= 1

3 left = ls[0, ls.length/2]

4 right = ls[ls.length/2, ls.length]

5 merge(merge_sort(left), merge_sort(right))

6 end

7

8 sl = []

9 until l.empty? or r.empty?

10 sl << (l[0] <= r[0] ? l.shift : r.shift)

11 end

12 sl.concat(l).concat(r)

13 end

14

15 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]

16 p list

17 p merge_sort(list)

First reasonable running time. Take the list and split it in half. Take each half and split those in half until you have done so lg(n) times.

Merge the bottom row of elements which are at this point 1 element each. O(1) * n/2

Merge the higher up elements which are at this point 2 sorted elements each. O(3) *n/4

Merge the higher up elements which are at this point 4 sorted elements each. O(7) *n/8

Do so until you reach the n/2 sorted list

lgN steps max N comparisons at each step.

Heap Sort:

1

2 sl = []

3 heap = build_heap(list)

4 heap.size.times do

5 sl << heap.shift

6 heap = heapify(heap, 0)

7 end

8 sl.reverse

9 end

10 ; ((i+1)*2)-1; end

11 ; (i+1)*2; end

12

13 max = root

14 l, r = left(root), right(root)

15 if ( l < h.size && h[l] > h[max])

16 max = l

17 end

18 if ( r < h.size && h[r] > h[max])

19 max = r

20 end

21 if( root != max)

22 h[root], h[max] = h[max], h[root]

23 return heapify(h, max)

24 else

25 return h

26 end

27 end

28

29 heap = list.clone

30 (((heap.size)-1)/2).downto(0) do |e|

31 heap = heapify(heap, e)

32 end

33 heap

34 end

35

36 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]

37 p list

38 p heap_sort(list)

39

Heap sort relies on the fact that a heap structure will have a constant speed get max. and a lgn heapify method. as well as an nlogn build heap method.

First step build a binary heap. where every parent is bigger than its (2 for binary heap) children. So you pull the first object off of a list.

QuickSort:

1

2 sl = list.clone

3 return sl if sl.size <= 1

4 pivot = sl.pop

5 left, right = sl.partition {|e| e < pivot }

6 quick_sort(left) + [pivot] + quick_sort(right)

7 end

8

9 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]

10 p list

11 p quick_sort(list)

12

Very similar to Merge only that this time you randomly pick a pivot point, then divide the resulting list to be sorted into two sublists. One containing numbers smaller than your pivot and the other containing the numbers larger than your pivot. You recursively call this method on the sublists and return when the sublist is of size 0 or 1.(or even two if you want to speed it up a bit.)

Counting Sort:

Equivalent to bucket sort with size 1 bucket ranges.

1

2 counts = Array.new(max+1, 0)

3 list.each do |i|

4 counts[i] += 1

5 end

6 sorted = []

7 counts.each_index do |index|

8 counts[index].times { sorted << index }

9 end

10 sorted

11 end

12

13 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]

14 p list

15 p counting_sort(list, 43)

Wow, thank you very much.

ReplyDeleteAmazing and concise stuff ..!! Extremely useful..!!

ReplyDeleteVery Useful.....

ReplyDeleteThank you...