answersLogoWhite

0

C Programming
Computer Science
C++ Programming

What is bubble sort?


Top Answer
User Avatar
Wiki User
Answered 2012-05-12 12:42:12

Bubble sort is a sorting algorithm that compares 2 adjacent items at a time, starting from the beginning of a list, and swapping them if they are out of sequence. Each comparison gradually moves the largest item to the end of the list (likened to a bubble making its way to the surface of water). After n*n passes, all the items will be sorted. The big O for a standard bubble sort is therefore O(n*n).

The algorithm can be improved somewhat. Since it is clear that the last item is sorted on each pass, the unsorted set can be reduced by 1 element on each pass. Moreover, since the final swap on each pass indicates that everything from that point on is already sorted, the unsorted set can often be reduced by more than 1 element on each pass. For an already sorted list, the worst case is reduced to O(n), constant time.

For small sets of data, perhaps 10 to 20 items, the bubble sort is reasonably efficient, especially on partially sorted lists. However the insert sort algorithm offers similar or better performance on average. With larger sets, the quick sort algorithm is hard to beat, but is let down by inefficiencies when dealing with partially sorted lists. Hybrid sorts can improve things a little, however, there is no efficient way to check the state of a list to determine the most efficient algorithm to use at any given point.

001
๐Ÿ™
0
๐Ÿคจ
0
๐Ÿ˜ฎ
0
๐Ÿ˜‚
0
User Avatar

Your Answer

Loading...

Still have questions?

Related Questions

What is another name for bubble sort?

Bubble sort is also known as sinking sort.


What are advantages and disadvantages of bubble sort quick sort and merge sort?

what are advantages or disadvantages of bubble sort , quick sort or merge sort


What is cyclomatic complexity of bubble sort?

The cyclomatic complexity of bubble sort is 4.


Is a merge better than a bubble sort?

Virtually any sorting algorithm is better than bubble sort. Bubble sort is an example of how NOT to write an algorithm.


What is bubble sort complexity?

O(n2) The complexity of bubble sort is O(n(square))


Why heap-sort is better than bubble sort?

Heap sort will be much faster in most situations, though bubble sort will be easier to understand the code flow.


When is bubble sort better than quick sort?

Never.


Who invented the bubble sort?

ramesh


Tell me the algorithm and psuedocode of bubble sort?

The algorithm and psuedocode of bubble sort can be set at zero and this is a part of the computer programming protocol.


What is difference between bubble sort and exchange sort?

distinguish between selection sort and exchange sort


Difference between insertion sort and bubble sort?

Dota 2


Is Tree sort more efficient than bubble sort?

Yes


Menu driven program for selection sort bubble sort and insertion sort in c?

Yes.


Bubble sort Extra or in space?

Bubble sort is an "in place" algorithm. Other than a temporary "switch" variable, no extra space is required.


What is the worst case complexity of bubble sort algorithm?

The worst case time-complexity for bubble sort algorithm is O(n*n).


Is bubble sort more efficient technique than insertion sort?

Bubble sort and insertion sort both have the same time complexity (and space complexity) in the best, worst, and average cases. However, these are purely theoretical comparisons. In practical real-world scenarios, insertion sort (or any other sort, for that matter) will almost always be the better choice over a bubble sort.


What are some sorting rules for math?

Binary sort and bubble sort are two.


How do you sort the given contents of an array?

You would sort the given elements of an array by a bubble sort or heap sort code!!


Why quick sort is the best?

Quick Sort is an "average" performing sorting algorithm; there are better algorithms out there, but it is considered the best of the "learner's algorithms" (generally implied to be quick sort, bubble sort, selection sort, and gnome sort). It has a medium-length average sorting time, which is faster than bubble sorting and gnome sorting, but also has a medium-length best-case sorting time, with bubble sorting and gnome sorting beating it speed-wise. It also has a higher memory overhead than in-place swapping algorithms such as bubble sort and gnome sort.


What is the efficient between bubble sort and selection sort?

Both are of the same efficiency... -Manu-


Examples for internal sorting and external sorting?

External sorting: - Merge sort - Two way merge sort. Internal sorting: - Heap sort - Bubble sort - Tree sort - quick sort - shell sort - Insertion sort External sorting: - Merge sort - Two way merge sort. Internal sorting: - Heap sort - Bubble sort - Tree sort - quick sort - shell sort - Insertion sort


What are the advantages for bubble sort?

Bubble sort has no practical applications other than that it is often cited as an example of how not to write an algorithm. Insert sort is the best algorithm for sorting small lists of items and is often used in conjunction with quick sort to sort larger lists. Like insert sort, bubble sort is simple to implement and is a stable sort (equal items remain in the same order they were input). However, insert sort uses copy or move operations rather than swaps (which is actually three operations per swap) and is therefore quicker. The only time a bubble sort will work quicker than insert sort is when the array is already sorted, which renders the entire algorithm redundant. A modified algorithm that specifically tests if an array is sorted or not would be more efficient than a single-pass bubble sort.


Can you modify the bubble sort algorithm to search to sort an array of characters instead of array of integers?

The bubble sort algorithm can be applied to an array of characters. Every character can be translated to an integer equivalent via the ascii table


Time complexity of bubble sort?

O(n^2)


What is the time complexity of bubble sort?

O(n*n)