The standard bubble sort can be made more efficient, this improved sorting technique is called the modified bubble sort. If we make a complete pass of the array elements and do not need to swap any items, then we know the array must be in order and we can stop the sort. Also, at the end of each passone more item is in the correct position (starting at the end), so the list to be sorted can be shortened by one.
To accomplish this, we must use a flag variable that indicates if any swaps were done. The flag will be set on at the beginning of a pass and when a swap is performed, it will be set off. If at the end of a pass, the flag is still on, then we know no swaps took place and we can terminate the sort.
We will let our flag variable be called 'done'. If we make it Boolean then it can only take the values 'true' or 'false'. We will also replace the outer 'for' loop with a 'loop' command, so we can use the 'exit when' command to terminate the sort.
The following is the code necessary to sort our list from the previous examples, using a modified bubble sort.
var done : boolean
var n : int := 5 % n is the # of items in list
var list : array 1..5 of int := init(9, 5, 8, 3, 1)
var temp : int
var numtosort : int
put " " % display the unsorted array
put "the unsorted list is:"
for x : 1..n
put list(x)," "..
end for
numtosort := n % keeps track of items left to sort
loop % replaces the former 'for i' loop, starts a pass
done := true % set the flag 'done' on, assume the list is sorted
for j : 1 .. numtosort-1 % j will indicate the position of the value being compared
% to its neighbor
if list (j) > list (j+1) then % a swap must be made
temp := list (j+1)
list (j+1) := list (j)
list (j) := temp
done := false % set flag 'done' to false, to indicate some swap happened
end if
end for
numtosort := numtosort - 1 % after each pass one more item is in order
exit when done = true or numtosort <= 1 % terminate sorting when no swaps happened
% or only one item left to sort
end loop
put " " % display the sorted array
put "the sorted list is:"
for x : 1..n
put list(x)," "..
end for |
This is more efficient because no unneeded passes through a sorted array are performed