Sorting Algorithm
This week’s portfolio activity is to write your python assignment on implementation of a sorting algorithm for the LinkedList implementation for world countries and their populations available on the assessment page. Make sure you sort the data in descending order from largest to smallest values, printing out both the values and the text labels. Annotate your code with comments explaining why you have chosen this algorithm, how the code works, and its complexity. The program must print out the LinkedList both before and after it has been sorted.
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 = 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),("Ethiopia",98665000),("Suriname",581372),("Turkmenistan",6031187),("American Samoa (US)",56700),("French Polynesia (France)",275918),("Equatorial Guinea",1358276),("Solomon Islands",680806),("Burundi",10953317),("Abkhazia",244832),("Rwanda",12374397),("Iceland",364260),("Monaco",38300),("Namibia",2458936),("United States",329532925),("Brazil",211402908),("Finland",5527573),("Armenia",2957500),("Wallis and Futuna (France)",11700),("Cuba",11209628),("Guyana",782766),("Oman",4664790),("Aruba (Netherlands)",112309),("Nauru",11000),("Sri Lanka",21803000),("Myanmar",54339766),("United Arab Emirates",9890400),("Hungary",9772756),("Norfolk Island (Australia)",1756),("Cambodia",15288489),("Fiji",884887),("Benin",11733059),("Egypt",100264508),("Northern Cyprus",351965),("Angola",31127674),("Barbados",287025),("Trinidad and Tobago",1363985),("Colombia",49395678),("Turks and Caicos Islands (UK)",41369),("Norway",5367580),("Kiribati",120100),("Kosovo",1795666),("Azerbaijan",10067108),("Romania",19405156),("Kyrgyzstan",6533500),("Peru",32131400),("Australia",25680766),("Faroe Islands (Denmark)",52124),("Turkey",83154997),("Georgia",3723464),("Singapore",5703600),("Eswatini",1093238),("Saint Vincent and the Grenadines",110608),("East Timor",1387149),("Tuvalu",10200),("Pakistan",219313520),("Bahrain",1543300),("Paraguay",7152703),("Jersey (UK)",106800),("Slovakia",5456362),("Mongolia",3313049),("Argentina",44938712),("Jordan",10660256),("Saint Barthélemy (France)",9793),("Andorra",77543),("Bangladesh",168456310),("Saint Martin (France)",35746),("FS Micronesia",104468),("South Sudan",12778250),("Artsakh",148000),("Slovenia",2094060),("Senegal",16209125),("Ivory Coast",25823071),("Syria",17500657),("Montserrat (UK)",4989),("Philippines",108505959),("Laos",7123205),("Gibraltar (UK)",33701),("Iran",83371987),("Bahamas",385340),("Mauritania",4077347),("Portugal",10276617),("Madagascar",26251309),("Malawi",19129952),("Central African Republic",5496011),("Saint Kitts and Nevis",52823),("Ghana",30280811),("Honduras",9158345),("Belarus",9408400),("India",1361140893),("Estonia",1328360),("Nicaragua",6460411),("Mali",20250833),("Zambia",17885422),("S\u00e3o Tom\u00e9 and Pr\u00edncipe",201784),("Cura\u00e7ao (Netherlands)",158665),("Jamaica",2726667),("Northern Mariana Islands (US)",56200),("Vanuatu",304500),("Kuwait",4420110),("Cameroon",26545864),("Netherlands",17456281),("Saudi Arabia",34218169),("Dominican Republic",10358320),("Japan",125950000),("Djibouti",1078373),("Antigua and Barbuda",96453),("Morocco",35871167),("Nigeria",206139587),("Iraq",39127900),("South Korea",51780579),("Pitcairn Islands (UK)",50),("US Virgin Islands (US)",104578),("Ireland",4921500),("Sierra Leone",7901454),("Cyprus",875900),("Palestine",4976684),("Luxembourg",626108),("Falkland Islands (UK)",3198),("France",67076000),("Bolivia",11469896),("Panama",4218808),("Seychelles",97625),("Guinea-Bissau",1604528),("Puerto Rico (US)",3193694),("Anguilla (UK)",14869),("Macau (China)",679600),("North Macedonia",2077132),("Saint Helena, Ascension",5633),("Sweden",10338368),("Kazakhstan",18683712),("China",1402247960),("Italy",60238522),("Israel",9186750),("Uzbekistan",34131625),("Guam (US)",172400),("Dominica",71808),("Malaysia",32752760),("New Zealand",4978784),("Cape Verde",550483),("Uruguay",3518552),("Belgium",11524454),("Kenya",47564296),("Saint Pierre and Miquelon (France)",6008),("Uganda",40299300),("Yemen",29825968),("Nepal",29996478),("Switzerland",8603899),("Sint Maarten (Netherlands)",40614),("Tonga",100651),("Algeria",43000000),("Haiti",11577779),("Zimbabwe",15159624),("North Korea",25450000),("Congo",5518092),("Belize",408487),("Czech Republic",10693939),("Poland",38379000),("San Marino",33574),("Tanzania",55890747),("Tokelau (NZ)",1400),("Saint Lucia",178696),("Cook Islands (NZ)",15200),("Mozambique",30066648),("Indonesia",266911900),("Grenada",112003),("Burkina Faso",20870060),("Western Sahara",582463),("New Caledonia (France)",282200),("Albania",2845955),("Greece",10724599),("Bosnia and Herzegovina",3301000),("Montenegro",622359),("Russia",146745098),("Samoa",200874),("Comoros",873724),("United Kingdom",66435550),("Taiwan",23604265),("Vatican City",799),("Austria",8902600),("Lebanon",6825442),("Latvia",1906800),("Mexico",126577691),("Venezuela",32219521),("Papua New Guinea",8935000),("Chad",16244513),("Canada",37996639),("Maldives",374775),("Denmark",5822763),("Tajikistan",9127000),("Isle of Man (UK)",83314),("Afghanistan",32225560),("Germany",83149300),("Vietnam",96208984),("Eritrea",3497117),("Spain",47100396),("Costa Rica",5058007),("Cayman Islands (UK)",65813),("Niger",22314743),("Liechtenstein",38749),("Gambia",2347706),("Hong Kong (China)",7500700),("Sudan",42432665),("Tunisia",11722038),("\u00c5land Islands (Finland)",29885),("DR Congo",89561404),("Bulgaria",6951482),("Liberia",4475353),("Botswana",2338851),("Palau",17900),("Niue (NZ)",1520),("Thailand",66494417),("South Africa",58775022),("Lithuania",2793471),("Gabon",2172579),("Libya",6871287),("Transnistria",469000),("Moldova",2681735),("South Ossetia",53532),("Guinea",12218357),("El Salvador",6486201),("Croatia",4076246),("Qatar",2747282),("Serbia",6963764),("Togo",7538000),("Ecuador",17466864),("Cocos (Keeling) Islands (Australia)",538),("Chile",19107216),("Bermuda (UK)",64027),("Somalia",15893219),("Bhutan",741672),("Marshall Islands",55500)])
Solution:
# Insertion Sort
# A. Time Complexity
# - Worst case complexity: O(n^2)
# - Best case complexity: O(n)
# B. Reason
# - Since the linked list has limitation for data access in sequential order and cannot access
# randomly, so that insertion sort is a better solution as it can take the linear access order
# to search for the maximum value from the sub-list and then use O(1) time complexity for data
# swapping.
# Sort the data in descending order from largest to smallest values
def sort_list(head):
# First copy the head Node to the result Linked List variable
result = head
# Declare the pointer node variable, ptrNode to be None to indicate it is the start for the
# sorting operation
ptrNode = None
# We then use the do-while loop to iterate down the linked list until the end
while True:
# First assign None to the max node and its previous and next node variables
maxPrevNode = None
maxNode = None
maxNextNode = None
# Set the previous Node to be the pointer Node
prevNode = ptrNode
# If the previous Node is None, which means it is the beginning of the Linked List, so
# that assign the current Node to be the head of the linked list; otherwise, the current
# node to be the next of the pointer node
if prevNode == None:
currNode = result
else:
currNode = prevNode.tail
# Set the next node
nextNode = currNode.tail
# Set the initial maximum value to be the current node value
maxVal = currNode.value
# Use the while loop to find the maximum value node
while currNode != None:
# If the current node value is larger than the recorded maximum value
if currNode.value > maxVal:
# Update the temporary maximum value and node, including previous and next
maxVal = currNode.value
maxPrevNode = prevNode
maxNode = currNode
maxNextNode = currNode.tail
# Advance the current node, including update the previous node and next node
prevNode = currNode
currNode = currNode.tail
# If the current node is None, then assign the next node to be None; otherwise
# assign the next node to be the next to the current node
if currNode == None:
nextNode = None
else:
nextNode = currNode.tail
# If the previous node of the max node is not Node
if maxPrevNode != None:
# Skip the maximum node by assigning the next of the Previous Max Node to be the Next
# Max Node
maxPrevNode.tail = maxNextNode
# If the pointer node is None, it means it is the start of the linked list
if ptrNode == None:
# Assign the head of the result list to the next of the maximum node
maxNode.tail = result
# Move the maximum node to be the head of the result list
result = maxNode
else:
# Otherwise, assign the next of the pointer node to the next of the maximum node
maxNode.tail = ptrNode.tail
# and assign the next of the pointer node to be the maximum node
ptrNode.tail = maxNode
# If the pointer node is None, it means it is the start of the linked list
if ptrNode == None:
# then assign the pointer node to be the head of the result list
ptrNode = result
else:
# otherwise, advance the pointer node to be the next
ptrNode = ptrNode.tail
# If it is the end of the linked list, exit the loop
if ptrNode.tail == None:
break
# Return the result sorted linked list
return result
def print_list(head):
# Declare the variable, current, to store the current Linked List node
current = head
# Declare the variable, i, to count and indicate the country ID based on its popluation value
i = 1
# Using the while-loop to iterate the linked list
# If it is the end of the linked list, then the current pointer should be None
while current != None:
print( "%3d: %35s - %10d" % ( i, current.label, current.value ) )
# Increment the country ID by 1
i += 1
# Update the linked list pointer to the next node by assigning the variable, current, with
# current.tail
current = current.tail
def main():
# Call the sort_list function to sort the countries list
sorted_countries = sort_list( countries )
# Print the sorted countries list
print_list( sorted_countries )
if __name__ == "__main__":
main()