[go: up one dir, main page]
Scribd
Upload
5 views4 pages

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order, making it inefficient for large data sets due to its O(n²) time complexity. The algorithm sorts an array through multiple passes, moving the largest unsorted elements to their correct positions. While it is easy to implement and requires no additional memory, its performance is hindered by its comparison-based nature.

Uploaded by

mnirmalkumarmech
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views4 pages

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order, making it inefficient for large data sets due to its O(n²) time complexity. The algorithm sorts an array through multiple passes, moving the largest unsorted elements to their correct positions. While it is easy to implement and requires no additional memory, its performance is hindered by its comparison-based nature.

Uploaded by

mnirmalkumarmech
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Bubble Sort Algorithm

••
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the
adjacent elements if they are in the wrong order. This algorithm is not suitable for
large data sets as its average and worst-case time complexity are quite high.
• We sort the array using multiple passes. After the first pass, the maximum
element goes to end (its correct position). Same way, after second pass, the
second largest element goes to second last position and so on.
• In every pass, we process only those elements that have already not moved
to correct position. After k passes, the largest k elements must have been
moved to the last k positions.
• In a pass, we consider remaining elements and compare all adjacent and
swap if larger element is before a smaller element. If we keep doing this,
we get the largest (among the remaining elements) at its correct position.
How does Bubble Sort Work?
Below is the implementation of the bubble sort. It can be optimized by
stopping the algorithm if the inner loop didn’t cause any swap.
# Optimized Python program for implementation of Bubble Sort

Def bubbleSort(arr):

N = len(arr)

# Traverse through all array elements

For I in range(n):

Swapped = False

# Last I elements are already in place

For j in range(0, n-i-1):

# Traverse the array from 0 to n-i-1

# Swap if the element found is greater

# than the next element

If arr[j] > arr[j+1]:

Arr[j], arr[j+1] = arr[j+1], arr[j]

Swapped = True

If (swapped == False):

Break

# Driver code to test above

If __name__ == “__main__”:

Arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)
print(“Sorted array:”)

for I in range(len(arr)):

print(“%d” % arr[i], end=” “)

Output

Sorted array:

11 12 22 25 34 64 90

Complexity Analysis of Bubble Sort:

Time Complexity: O(n2)

Auxiliary Space: O(1)

Advantages of Bubble Sort:

Bubble sort is easy to understand and implement.

It does not require any additional memory space.

It is a stable sorting algorithm, meaning that elements with the same key value maintain
their relative order in the sorted output.

Disadvantages of Bubble Sort:

Bubble sort has a time complexity of O(n2) which makes it very slow for large data sets.

Bubble sort is a comparison-based sorting algorithm, which means that it requires a


comparison operator to determine the relative order of elements in the input data set. It
can limit the efficiency of the algorithm in certain cases.

You might also like