CODEWITHSUNDEEP
cbubble-sort
user994559
user994559

Reputation: 11

Optimizing a bubble sort in C that will decrease the number of swaps needed to sort a list of numbers in ascending order

To my understanding, the bubble sort (inefficient version) will do as follows:

2 3 8 6 23 14 16 1 123 90  (10 elements)
  1. Compare element [0] and element [1]
  2. If [0] is bigger than [1], then a swap is completed.
  3. If [1] is bigger than [0], then no swap is complete.

Then the bubble sort will move onto comparing elements [1] and [2] and so forth, creating a total of 9 swaps.

However, could there be a way to guarantee that on the first pass, the highest number will be in its proper place at [9], and that on a second pass, the two highest numbers will be in their proper places at [7] and [8]?

Upvotes: 1

Views: 2088

Answers (4)

Ganondox
Ganondox

Reputation: 1

Two things can be done to optimize bubble-sort. First, keep track if any swaps occurred during a single pass. If none occurred, then the list must have been completely sorted by that point, so you don't have to make any additional passes. Also, decrease the range of the loop each pass, as one more element should be in the correct position after each pass.

Upvotes: 0

ams
ams

Reputation: 25599

If you've implemented the bubble sort algorithm correctly, the highest number must always be in the right place at the end of the first pass.

The optimization is simply to go one step less at the end of the second pass:

let n equal top_element - 1
while n is greater than or equal to zero
  for i = 0 to n
    if element i is greater than element i+1 then swap
  subtract 1 from n

Upvotes: 1

Jan
Jan

Reputation: 11726

Don't use bubble sort. Consider superior algorithms, such as

Encountering a question How do I optimise bubble sort my answer is optimise it as long as it isn't Timsort yet.

Upvotes: 3

FireJade
FireJade

Reputation: 31

Bubble sort is a specific algorithm -- it doesn't really make sense to ask if it can be optimized to have the property you want. It also has O(n^2) complexity, which is why it is rarely used.

There are other sorting algorithms, like selection sort, which will have a property closer to what you want. Selection sort will guarantee that on the i'th pass, the minimum i elements are in the correct positions. However, selection sort is also O(n^2), and should be avoided if you anticipate sorting a decent amount of data.

Like Basile and Jan, I recommend learning a more efficient and standard sorting algorithm, quicksort. Quicksort is very widely used, and is available in the C standard library. Wikipedia's description of the algorithm is relatively concise; a search on Google will also give many animated versions of quicksort, which can be quite helpful for learning the algorithm.

Upvotes: 3

Related Questions