BUBBLE SORT 1 - EFFICIENT:
DECLARE TheList: ARRAY OF INTEGER
PROCEDURE BubbleSort
DECLARE MaxIndex, Index, Temp: INTEGER
DECLARE NoMoreSwap: BOOLEAN
Swapped ← TRUE
MaxIndex ← LENGTH(TheList) - 1
WHILE MaxIndex > 1 AND Swapped = TRUE DO
Swapped ← FALSE
FOR Index ← 1 TO MaxIndex:
IF TheList [Index] > TheList [Index + 1]
Temp ← TheList [Index]
TheList [Index] ← TheList [Index + 1]
TheList [Index + 1] ← Temp
Swapped = TRUE
ENDIF
NEXT Index
MaxIndex ← MaxIndex - 1
ENDWHILE
ENDPROCEDURE
Why efficient?
# Reduces the size of the array after exit of inner loop
# The outer loop terminates if the array is sorted
BUBBLE SORT 2 – NOT EFFICIENT:
DECLARE TheList: ARRAY OF INTEGER
PROCEDURE BubbleSort
DECLARE MaxIndex, Index, OuterIndex, Temp: INTEGER
MaxIndex ← LENGTH(TheList) - 1
FOR OuterIndex ← 1 To MaxIndex
FOR Index ← 1 TO MaxIndex:
IF TheList [Index] > TheList [Index + 1]
Temp ← TheList [Index]
TheList [Index] ← TheList [Index + 1]
TheList [Index + 1] ← Temp
ENDIF
NEXT Index
NEXT Index
ENDPROCEDURE
Why not efficient?
# Does not reduce the size of the array after exit of inner loop
# The outer loop does not terminate even after the array is sorted
INSERTION SORT 1
DECLARE TheList: ARRAY OF INTEGER
PROCEDURE InsertionSort
DECLARE ValueToInsert, HolePosition, Index: INTEGER
FOR Index ← 2 To MaxIndex
ValueToInsert ← TheList [Index]
HolePosition ← Index – 1
WHILE HolePosition >= 1 AND TheList [HolePosition] > ValueToInsert DO
TheList [HolePosition + 1] ← TheList [HolePosition]
HolePosition ← HolePosition – 1
ENDWHILE
TheList [HolePosition + 1] ← ValueToInsert
NEXT Index
ENDPROCEDURE
INSERTION SORT 2
DECLARE TheList: ARRAY OF INTEGER
PROCEDURE InsertionSort
DECLARE ValueToInsert, HolePosition, Index: INTEGER
FOR Index ← 2 To MaxIndex
ValueToInsert ← TheList [Index]
HolePosition ← Index # Notice the difference from above
WHILE HolePosition > 1 AND TheList [HolePosition - 1] > ValueToInsert DO
TheList [HolePosition] ← TheList [HolePosition - 1]
HolePosition ← HolePosition – 1
ENDWHILE
TheList [HolePosition] ← ValueToInsert
NEXT Index
ENDPROCEDURE
Sample code 1: BUBBLE SORT
# Efficient bubble sort
def BubbleSort(arr):
Swaps = True
Top = len(arr) - 1
while Swaps and Top > 0:
Swaps = False
for i in range(Top):
if arr[i] > arr[i + 1]:
Temp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = Temp
Swaps = True
Top = Top - 1
return arr
# inefficient bubble sort
def InefficientBubbleSort(arr):
size = len(arr)
for i in range(size):
for j in range(size - 1):
if arr[j] > arr[j + 1]:
Temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = Temp
return arr
# improved but still not efficient
def ImprovedBubbleSort(arr):
size = len(arr)
for i in range(size):
for j in range(size - i - 1):
if arr[j] > arr[j + 1]:
Temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = Temp
return arr
if __name__ == '__main__':
print(InefficientBubbleSort([1, 2, 3, 4, 5, 6, 9, 8, 7]))
print(ImprovedBubbleSort([1, 2, 3, 4, 5, 6, 9, 8, 7]))
print(BubbleSort([1, 2, 3, 4, 5, 6, 9, 8, 7]))
Sample code 2: INSERTION SORT
def Sort(arr):
for Index in range(1, len(arr)):
ValueToInsert = arr[Index]
HolePosition = Index - 1
while HolePosition >= 0 and arr[HolePosition] > ValueToInsert:
arr[HolePosition + 1] = arr[HolePosition]
HolePosition = HolePosition - 1
arr[HolePosition + 1] = ValueToInsert
return arr
def Sort2(arr):
for Index in range(1, len(arr)):
ValueToInsert = arr[Index]
HolePosition = Index
while HolePosition > 0 and arr[HolePosition - 1] > ValueToInsert:
arr[HolePosition] = arr[HolePosition - 1]
HolePosition = HolePosition - 1
arr[HolePosition] = ValueToInsert
return arr
if __name__ == '__main__':
array = [9, 7, 5, 1, 2, 3, 6, 4]
print(Sort(array))