Question

Write in python:

Go through the visualization of the Selection Sort, Bubble Sort and Insertion Sort.

Write a Pseudo code first for each of these sort methods. After writing the pseudo code write python code from the pseudo code.

Answer 1

Following are the Pseudo Codes:

1) Bubble Sort : We start by comparing the first two elements of the list. If the first element is greater than the second element we swap them. If they are already in order we leave them as it is. We then move to the next pair of elements, compare them and swap as necessary. This process continues to the last pair of items in the list.

procedure bubbleSort( list_items : array of items )
loop = list_items.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */   
if list_items[j] > list_items[j+1] then
/* swap them */
swap( list_items[j], list_items[j+1] )         
swapped = true
end if
end for
/*if no swapping meaning array is sorted now*/
if(not swapped) then
break
end if
end for
end procedure return list_items

2. Selection Sort : In this we consider the leftmost part of the list as the sorted segment. We then search the entire list for the smallest element, and swap it with the first element. Now the first element of the list is sorted, we get the smallest element among the remaining items and swap it with the second element. This iterates until the last item of the list is remaining element to be examined.

procedure selection sort
list_items : array of items
n : size of list

for i = 1 to n - 1
/* setting current element as minimum*/
min = i
/* check the minimum element*/
for j = i+1 to n
if list_items[j] < list_items[min] then
min = j;
end if
end for
/* make current as minimum*/
if indexMin != i then
swap list_items[min] and list_items[i]
end if
end for
end procedure

3) Insertion Sort :We assume first element of the list as sorted. We then go to the next element, we call it x. If x is larger than the first element we leave it as it is. If x is smaller, we copy the value of the first element to the second position and then set the first element to x. As we go to the other elements of the unsorted segment, we continuously move larger elements in the sorted segment up the list until we encounter an element smaller than x or reach the end of the sorted segment, and then place x in it's correct position.

rocedure insertionSort( list_items : array of items )
int holePosition
int valueToInsert
  
for i = 1 to length(list_items) inclusive do:
valueToInsert = list_items[i]
holePosition = i
/*locate hole position for insertionn */
while holePosition > 0 and list_items[holePosition-1] > valueToInsert do:
list_items[holePosition] = list_items[holePosition-1]
holePosition = holePosition -1
end while
/* insert the element */
list_items[holePosition] = valueToInsert
end for
end procedure

IMPLEMENTATION OF THE PSEUDO CODE

1) Bubble Sort :

def bubble_sort(nums):
swapped = True
while swapped:
swapped = False
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
# Swap elements
nums[i], nums[i + 1] = nums[i + 1], nums[i]
# Set flag = true
swapped = True

listOfNumbers = [5, 2, 1, 8, 4, 9, 3, 7]
print("Unsorted List : "+ str(listOfNumbers))
bubble_sort(listOfNumbers)
print("Sorted List : " + str(listOfNumbers))

Output :

2) Selection Sort :

def selection_sort(num):
for i in range(len(num)):
#assume first is smallest
low_value = i
for j in range(i + 1, len(num)):
if num[j] < num[low_value]:
low_value = j
num[i], num[low_value] = num[low_value], num[i]

listOfNumbers = [5, 2, 1, 8, 4, 9, 3, 7]
print("Unsorted List : "+ str(listOfNumbers))
selection_sort(listOfNumbers)
print("Sorted List : " + str(listOfNumbers))

OUTPUT

3) INSERTION SORT

def insertion_sort(nums):
#first element assumed sorted
for i in range(1, len(nums)):
item = nums[i]
j = i - 1
while j >= 0 and nums[j] > item:
nums[j + 1] = nums[j]
j -= 1
# Insert the item
nums[j + 1] = item

listOfNumbers = [15, 2, 11, 8, 14, 9, 23, 7]
print("Unsorted List : "+ str(listOfNumbers))
insertion_sort(listOfNumbers)
print("Sorted List : " + str(listOfNumbers))

OUTPUT

Hope This Helps. :)