Sorting algorithms/Gnome sort: Difference between revisions

Content added Content deleted

Inline

@@ Line 630: / Line 630: @@
 <lang Eiffel>
 class
-	GNOME_SORT
+	GNOME_SORT [G -> COMPARABLE]
 feature
-	sort(ar: ARRAY[INTEGER]): ARRAY[INTEGER]
-		-- sort array ar with gnome sort
+	sort (ar: ARRAY [G]): ARRAY [G]
+			-- sort array ar with gnome sort
-	require
+		require
-		array_not_void: ar/= VOID
+			array_not_void: ar /= VOID
-	local
+		local
-		i,j, ith: INTEGER
+			i, j: INTEGER
-	do
-		from
+			ith: G
+		do
-			i:= 2
+			create Result.make_empty
-			j:= 3
+			Result.deep_copy (ar)
-		until
-			i>ar.count
+			from
+				i := 2
-		loop
-			if	ar[i-1] <= ar[i] then
+				j := 3
-				i:= j
+			until
-				j:= j+1
+				i > Result.count
-			else
+			loop
-				ith := ar[i-1]
+				if Result [i - 1] <= Result [i] then
-				ar[i-1] := ar[i]
+					i := j
-				ar[i] := ith
+					j := j + 1
-				i:= i-1
+				else
-				if i=1 then
+					ith := Result [i - 1]
-					i:=j
+					Result [i - 1] := Result [i]
-					j:= j+1
+					Result [i] := ith
+					i := i - 1
+					if i = 1 then
+						i := j
+						j := j + 1
+					end
 				end
 			end
-		end
-		Result := ar
 		ensure
 			same_length: ar.count = Result.count
+			Result_is_sorted: is_sorted (Result)
-			same_items: Result.same_items (ar)
-	end
+		end
+feature {NONE}
+	is_sorted (ar: ARRAY [G]): 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:
@@ Line 673: / Line 700: @@
 class
 	APPLICATION
-inherit
-	ARGUMENTS
 create
-    make
+	make
 feature
-    make
+	make
-	do
+		do
-		test:= <<7, 99, -7, 1, 0, 25, -10>>
+			test := <<7, 99, -7, 1, 0, 25, -10>>
-		create gnome
+			io.put_string ("unsorted:%N")
-                test:= gnome.sort (test)
+			across
-		across test as ar loop io.put_string( ar.item.out + "%T") end
+				test as ar
-	end
+			loop
+				io.put_string (ar.item.out + "%T")
+			end
+			io.new_line
+			io.put_string ("sorted:%N")
+			create gnome
+			test := gnome.sort (test)
+			across
+				test as ar
+			loop
+				io.put_string (ar.item.out + "%T")
+			end
+		end
+	test: ARRAY [INTEGER]
+	gnome: GNOME_SORT [INTEGER]
-	test: ARRAY[INTEGER]
-	gnome: GNOME_SORT[INTEGER]
 end
 </lang>
 OUTPUT:
 <pre>
-Unsorted: 1 27 32 99 1 -7 3 5
+Unsorted:
-Sorted: -7 1 1 3 5 27 32 99
+99    -7    1    0    25    -10
+Sorted:
+-7    -10    0    1    7    25    99
 </pre>