I was trying to use bubble sort in sorting a linked list in descending order. My code prints out a list in alphabetical order instead. I wanted to print out the second element and sort it from highest to lowest value instead of alphabetical order.
What am I missing here? If someone can point this out, I would entirely be grateful thanks.
class LinkedList:
def __init__(self, data):
self.label = data[0][0]
self.value = data[0][1]
self.tail = None if (len(data) == 1) else LinkedList(data[1:])
countries = [("Ukraine",41879904),("Brunei",442400),("Christmas Island (Australia)",1928),("Mauritius",1265985),("Lesotho",2007201),("Guatemala",16604026),("British Virgin Islands (UK)",30030),("Malta",493559),("Greenland (Denmark)",56081),("Guernsey (UK)",62792)]
# BUBBLE SORT
def bubbleSort(countries):
for passnum in range(len(countries)-1,0,-1):
for i in range (passnum):
for j in range(0, len(countries)-i,-1)
if (countries[j][1] > countries[j+1][1]):
temp = countries[j]
countries[j] = countries[j+1]
countries[j+1] = temp
return countries
print("Bubble Sort")
print("The Unsorted List: ", countries)
print('\n' * 1)
bubbleSort(countries)
print("The Original Sorted List: ", countries)
print('\n' * 1)
countries.reverse()
print("The Updated List in Descending Order: ", countries)
A bubble sort on a linked list progresses through the list swapping consecutive elements pairs that are in the wrong order, repeating the process until no more swaps are made.
You can implement it by swapping element contents or by rearranging the links.
Swapping content
class LinkedList:
def __init__(self, data=None,*more):
self.label, self.value = data or [None,None]
self.link = LinkedList(*more) if more else None
def bubbleSort(L):
swapping = True
while swapping: # go through list as many times as needed
swapping = False
a,b = L,L.link # compare successive element pairs
while a and b:
if a.value<b.value: # swap if in wrong order
a.value,b.value = b.value,a.value
a.label,b.label = b.label,a.label
swapping = True
a,b = b,b.link # advance in linked list
Sample use:
countries = LinkedList(("Ukraine",41879904),("Brunei",442400),
("Christmas Island (Australia)",1928), ("Mauritius",1265985),
("Lesotho",2007201),("Guatemala",16604026),
("British Virgin Islands (UK)",30030),("Malta",493559),
("Greenland (Denmark)",56081),("Guernsey (UK)",62792))
print("linked list")
e = countries
while e:
print(e.label,e.value,end=" --> ")
e = e.link
print("END")
bubbleSort(countries)
print("sorted list")
e = countries
while e:
print(e.label,e.value,end=" --> ")
e = e.link
print("END")
Output:
linked list
Ukraine 41879904 --> Brunei 442400 --> Christmas Island (Australia) 1928 --> Mauritius 1265985 --> Lesotho 2007201 --> Guatemala 16604026 --> British Virgin Islands (UK) 30030 --> Malta 493559 --> Greenland (Denmark) 56081 --> Guernsey (UK) 62792 --> END
sorted list
Ukraine 41879904 --> Guatemala 16604026 --> Lesotho 2007201 --> Mauritius 1265985 --> Malta 493559 --> Brunei 442400 --> Guernsey (UK) 62792 --> Greenland (Denmark) 56081 --> British Virgin Islands (UK) 30030 --> Christmas Island (Australia) 1928 --> END
Rearranging links
A bubble sort that manipulates the links will need to return a new head because the original one may no longer be first in the list after sorting:
def bubbleSort(L):
head = LinkedList() # need pointer to head
head.link = L # to track if it is swapped
swapping = True
while swapping: # go through list as many times as needed
swapping = False
prev,a,b = head,L,L.link # process needs predecessor of a
while a and b:
if a.value<b.value: # swap if in wrong order
prev.link,b.link,a.link = b,a,b.link # rearrange links
prev,a,b = b,a,a.link # avance through list
swapping = True
else:
prev,a,b = a,b,b.link # avance through list
return head.link # return new head
Usage:
countries = LinkedList(("Ukraine",41879904),("Brunei",442400),
("Christmas Island (Australia)",1928), ("Mauritius",1265985),
("Lesotho",2007201),("Guatemala",16604026),
("British Virgin Islands (UK)",30030),("Malta",493559),
("Greenland (Denmark)",56081),("Guernsey (UK)",62792))
countries = bubbleSort(countries) # returns new head of the (sorted) list