::GameDeveloperPlayground::

----------------------------------------------------------------------

Hello, i am GameDeveloperPlayground.

I am a Korean student and I post it for English practise.

I would appreciate pointing out grammar or typos.

----------------------------------------------------------------------

In this posting in about bubble sort.

Bubble Sort 

Bubble Sort is a simple sorting algorithm that compares two adjacent numbers and sends them back a large number.

Time complexity is O(N²). The speed is slow, but the code is simple.

Said that the movement of the element is called bubble sort because the bubble appears to be rising to the suface of the water.

Sorting process

Show an example of simple bubble sorting.

Let's say have 5 numbers given below. Sort by Bubble Sort.

9 5 1 3 7

First, compare the first index with the second index.

9, 5 . 9 is larger change the place of two numbers.

Before the change : 9 5 1 3 7

After change : 5 9 1 3 7

Increase the next index by one and compare the second and third indexes.

9 is larger, thery change the place of two numbers.

Before the change : 5 9 1 3 7

After change : 5 1 9 3 7

Continue to increase the Index, complare the values, and change the position.

Before the change : 5 1 9 3 7

After change : 5 1 3 9 7

Before the change : 5 1 3 9 7

After change : 5 1 3 7 9

Onetime tour is over. As the tour of the circle was over, the biggest number 9 went to the spot.

So in the next tour, you do not need to visit the last element.

Fix the last element 9, Let's proceed with the remaining elements.

Before the change : 5 1 3 8 9

After change : 1 5 3 7 9

Before the change : 1 5 3 7 9

After change : 1 3 5 7 9

Before the change : 1 3 5 7 9

After change : 1 3 5 7 9

The Second tour is over. As an example, a few random numbers are completedd in just two iterations

This is Bubble Sort!! HaHA

Example Code

It's a simple.

Algorithm analysis

Sorting algorithms need to be analyzed.

I Wrote down the time complextiy as O (N²), but need to know how to get it.

Number of comparisons

Bubble Sort is reduced by one each time you complete a tour.

Total number of elements is n, the sorting is completed when the total n-1.

If sort the five element arrays, you will compare 4+3+2+1 = 10 times.

Formulate this.

(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 = ( n-1 ) * n / 2 = n(n-1)/2

Number of Exchanges

In the best case, not be a swap during the sorting process.

In the worst case, since every time compare elements, the number of excahnges will be equal to the number of comparisons.

Best Case Replacement count : 0

Tho Worst case number of Exchanges :  : n(n-1)/2

Adding the number of comparisions and The number of exchanges gives n²-n.

There fore time complexity is O(N²) in BiG O notation.

Below is the data i found when I searched for bubble sorting data.

Example video of Bubble Sort

Source )유투브 동영상(클릭) )

Thank You.