Computing Students - Computer Science Degree Notes
Home Contact Shop Notes Questions Programming Links Dictionary Coursework FORUM Tutors
  Recommended Amazon Searches: Computer Science | Computing | Computer Systems | Database | Computing Revision  

Notes > Computation and Algorithms > Bubble Sort and Sorting

The Bubble Sort compares each successive pair of elements in an un-ordered list and inverts the elements if they are not in order. The following example illustrates the bubble sort.

The list "5,4,9,7,2,8" needs to be sorted from lowest to highest. The following steps are carried out:

  • Pass 1
    • First (5) and second (4) elements compared. 4 less than 5 therefore elements inverted.
      • Current list: 4,5,9,7,2,8
    • Second (now 5) and third (9) elements compared. In correct order so no change.
      • Current list: 4,5,9,7,2,8
    • 9 and 7 compared and inverted
      • Current list: 4,5,7,9,2,8
    • 9 and 2 compared and inverted
      • Current list: 4,5,7,2,9,8
    • 9 and 8 compared and inverted
      • Current list: 4,5,7,2,8,9
  • Pass 2
    • Same method used in Pass 1 applied to current list (4,5,7,2,8,9)
    • Resultant list: 4,5,2,7,8,9
  • Pass 3
    • Resultant list: 4,2,5,7,8,9
  • Pass 4
    • Resultant list: 2,4,5,7,8,9
  • Pass 5
    • No changes would be made in this pass therefore the algorithm has reached its termination point and the list is sorted

It is worth noting that at the end of Pass 1 the largest element (9) has been moved to the end of the list. Similarly, in Pass 2, the second largest element (8) has been moved to the second last position in the list and so on. This pattern always occurs in the Bubble Sort.

Related to this point, it is also noteworthy that Pass 2 only needs to deal with n-1 elements (where n is the number of elements in the original list). Pass 3 only needs to deal with n-2 and so on. This is because at the end of each pass, another element has been put in its correct position at the end of the list. This leaves one less element that needs to be sorted for the next pass.

Best and Worst Case Analysis

The worst case for the number of passes is n-1. The best case is 1 pass which would occur if the list was already sorted. The list needs to be checked through at least once to check whether or not any inversions / swaps need to be done.

Search for "Bubble Sort" on: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "Bubble Sort" on the rest of Computing Students: Bubble Sort






Home | Contact | Shop | Notes | Questions | Programming | Links | Dictionary | Coursework | Tutors Sponsored Links: Affiliate Program Articles | Computer Science Definitions | CS Degree Notes
Copyright © 2005-2009 ComputingStudents.com
This site is to be used in accordance with the ComputingStudents.com User Agreement
High Wycombe Web Design