hello, could someone help me understand bubble sort logic, I'm a beginning programmer. Also I would like to understand some pseudocode: The city of Cary is holding a special census. The census takers collect one record for each resident. Each record contains a resident’s age, gender, marital status, and voting district. The voting district field contains a number from 1 to 22. Design a program that accepts data fro each resident until all have been entered and then produce a list of all 22 districts and the number of residents in each.
Thank you

Are you receiving any errors? Does this code not work that way you intended it? When asking for help there are a couple items that are vital in order for someone to properly help you:

• Post the code you're having problems with
• Post the exact error you're receiving, if you are receiving one
• If no error explain what the code is doing versus what you want it to do
• Post your question in the body of your post, not the description field

Bubblesort is the easiest to learn sorting algorithm, but also the most inefficient. The basic idea is that you have a list of things to sort, and you compare each item with the item next to it. The bigger (or smaller) items "bubble" to the top of the list and your list eventually becomes sorted. The reason this is so inefficient is that, for n items, you have to do this n^2 times before the list is sorted - usually with a FOR loop inside of a FOR loop.

As for your pseudo code, it sounds like you need to design a program that continually prompts the user to create new residents until you want to print out the district summary. Every time your user agrees to create a resident, the user is prompted to enter the resident's age, gender, marital status, and voting district. Your program will store this information somewhere in an array or list. When the user is done creating residents, your program should at some point in time offer the user an option to view the district summary. When the user selects that option, your program will print a list of the districts and their corresponding count of its residents.

There are of course many other ways to design this program (i.e. you can create a file with resident data and read the data into your program instead).

It's only inefficient if you actually have to sort the data! Or if you have a large amount of data. Other than that we're looking at a best case complexity of O(n) !!

Thanks, I'd meant to respond to that.

Put another way, if your list is mostly in order, with a handful of data points out of place, bubble sort can be the most effective. Most sorts are exhaustive, needing to do at least size*size compares. The humble bubble sort, for all it's simplicity, can beat a quick sort given best case data.

This post has been edited by baavgai: 20 May, 2009 - 02:02 PM

Or given a small enough data set.

There's a common misconception that big-O notation describes run time, but it does not. It describes how run time increases as the data set grows, but there is also a constant multiplier involved. In this case, that constant primarily reflects the amount of effort that goes into actually performing each comparison.

For example, let's consider a bubble sort (average-case complexity O(n^2), taking 1 unit of time to perform each comparison) vs. a quicksort (average-case O(n log n), taking 100 units of time to perform each comparison). So, on average, the bubble sort will require n^2 time units to complete, while the quicksort will take 100n log n. Solving for n, we find that the bubble sort is faster for n < 237 (assuming base 10 log) or n < 647 (assuming natural log).

I the real world, I wouldn't expect the constant to be a 100-to-1 difference, but the constant factor is lower for bubble sort than any other.