A bubble sort repeatedly goes through a list, comparing neighbouring values and swapping them if they are out of order.<\/p>\n
After each pass through the list, the highest remaining value has “bubbled” through the list to its correct location, so the size of the remaining list to be sorted is reduced by 1.<\/p>\n
If no swaps are carried out on a pass, then the sorting can stop.<\/p>\n
DECLARE n INITIALLY length(list)\nDECLARE swapped INITIALLY TRUE\n \nWHILE swapped AND n >= 0\n \n SET swapped TO False\n FOR i = 0 to n-2 DO\n IF list[i] > list[i+1] THEN\n SET temp TO list[i]\n SET list[i] TO list[i+1]\n SET list[i+1] TO temp\n SET swapped TO TRUE\n END IF\n END FOR \n \n SET n TO n - 1\nEND WHILE<\/pre>\n\r\nlistsize = length(list)\r\nswapped = True\r\n \r\n# as long as previous loop had a swap, and unsorted part of list is not empty\r\nWHILE swapped AND listsize >= 0:\r\n \r\n # new iteration, so reset swaps\r\n swapped = False\r\n # go through the unsorted part of the list\r\n for i in range(listsize-1):\r\n #if current value is bigger than next value\r\n if list[i] > list[i+1]:\r\n #swap the values\r\n temp = list[i]\r\n list[i] = list[i+1]\r\n list[i+1] = temp\r\n swapped = True\r\n \r\n #the unsorted part of the list is now smaller\r\n listsize -= 1\r\n<\/pre>\nSwapping List Values<\/h2>\n
Most languages need the use of a temporary variable to swap two values. This is part of the AH course.<\/p>\n
\r\ntemp = list[i]\r\nlist[i] = list[i+1]\r\nlist[i+1] = temp\r\n<\/pre>\nPython can do this in one command:<\/p>\n
\r\nlist[i], list[i+1] = list[i+1], list[i]\r\n<\/pre>\nIn programmer interviews, one task might be to swap two numbers without the use of a temporary variable. This solution works, but requires several calculations:<\/p>\n
\r\nx = 3\r\ny = 5\r\n \r\nx = x + y # x = 3 + 5 = 8\r\ny = x - y # y = 8 - 5 = 3\r\nx = x - y # x = 8 - 3 = 5\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"A bubble sort repeatedly goes through a list, comparing neighbouring values and swapping them if they are out of order. After each pass through the list, the highest remaining value has “bubbled” through the list to its correct location, so the size of the remaining list to be sorted is reduced by 1. If no swaps are carried out on a pass, then the sorting can stop. General Algorithm DECLARE<\/p>\n