-
Notifications
You must be signed in to change notification settings - Fork 2.1k
/
Linked_List_Selection_Sort.rb
130 lines (100 loc) · 1.75 KB
/
Linked_List_Selection_Sort.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
=begin
Author: Jennifer Tran
Last Updated: 21/10/2016
=end
def main
list = LinkedList.new()
puts("Before sorting:")
list.add(13)
list.add(4)
list.add(10)
list.add(1)
list.add(20)
list.add(7)
list.printList
puts("\nAfter sorting:")
list.selectionSort
list.printList
end
class LinkedList
def initialize
@top = nil
end
# Inserts the items at the end of the list
def add(newItem)
curr = @top
# Top is empty insert at the front
if(curr == nil)
@top = Node.new(newItem,nil)
else
# Traverse through the list until it reaches the end
while curr.getNext != nil do
curr = curr.getNext
end
# Now set the new node
curr.setNext(Node.new(newItem,nil))
end
end
def printList
curr = @top
while(curr != nil)
print (curr.getItem)
print " "
curr = curr.getNext
end
puts()
end
def selectionSort
beg = @top
min = @top
# Iterate through the list
while(beg.getNext != nil)
min = beg
curr = beg.getNext
while(curr != nil)
# Check to see if its the smallest
if(curr.getItem < min.getItem)
min = curr
end
curr = curr.getNext
end
# Swap the values
temp = beg.getItem
beg.setItem(min.getItem)
min.setItem(temp)
beg = beg.getNext
end
end
end
class Node
# Constructor
def initialize(newItem,newLink)
@item = newItem
@link = newLink
end
# Gets the item
def getItem
@item
end
# Gets the next node
def getNext
@link
end
# Sets the next node
def setNext(newLink)
@link = newLink
end
# Sets the next item
def setItem(newItem)
@item = newItem
end
end
# Calls the main method
main
=begin
OUTPUT:
Before sorting:
13 4 10 1 20 7
After sorting:
1 4 7 10 13 20
=end