Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted

Inline

@@ Line 876: / Line 876: @@
   }
 }</lang>
+=={{header|Eiffel}}==
+<lang Eiffel>
+class
+	HEAPSORT
+feature
+	sort_array (ar: ARRAY [INTEGER])
+			-- Sorts array 'ar' in ascending order.
+		local
+			i, j, r, l, m, n: INTEGER
+			sorted: BOOLEAN
+		do
+			n := ar.count
+			j := 0
+			i := 0
+			m := 0
+			r := n
+			l := (n // 2)+1
+			from
+			until
+				sorted
+			loop
+				if l > 1 then
+					l := l - 1
+					m := ar.item (l)
+				else
+					m := ar.item (r)
+					ar.put (ar.item (1), r)
+					r := r - 1
+					if r = 1 then
+						ar.put (m, 1)
+						sorted := True
+					end
+				end
+				if not sorted then
+					i := l
+					j := l * 2
+					from
+					until
+						j > r
+					loop
+						if (j < r) and (ar.item (j) < ar.item (j + 1)) then
+							j := j + 1
+						end
+						if m < ar.item (j) then
+							ar.put (ar.item (j), i)
+							i := j
+							j := j + i
+						else
+							j := r + 1
+						end
+					end
+					ar.put (m, i)
+				end
+			end
+		end
+	is_sorted (ar: ARRAY [INTEGER]): BOOLEAN
+			--- Is 'ar' sorted in ascending order?
+		require
+			ar_not_empty: ar.is_empty = False
+		local
+			i: INTEGER
+		do
+			Result := True
+			from
+				i := ar.lower
+			until
+				i = ar.upper
+			loop
+				if ar [i] > ar [i + 1] then
+					Result := False
+				end
+				i := i + 1
+			end
+		end
+end
+</lang>
+Test:
+<lang Eiffel>
+class
+	APPLICATION
+create
+	make
+feature
+	make
+		local
+			test: ARRAY [INTEGER]
+		do
+			create test.make_empty
+			test := <<5, 91, 13, 99,7, 35>>
+			io.put_string ("Unsorted: ")
+			across
+				test as t
+			loop
+				io.put_string (t.item.out + " ")
+			end
+			io.new_line
+			create heap_sort
+			heap_sort.sort_array (test)
+			io.put_string ("Sorted: ")
+			across
+				test as t
+			loop
+				io.put_string (t.item.out + " ")
+			end
+		end
+	heap_sort: HEAPSORT
+end
+</lang>
+{{out}}
+<pre>
+Unsorted: 5 91 13 99 7 35
+Sorted: 5 7 13 35 91 99
+</pre>
 =={{header|F Sharp|F#}}==