Bubble Sort in Data Structure

Mentor: Shailendra Chauhan
Duration : 00:03:00

What is Sorting in Data Structures?

Sorting refers to the arrangement of data in a specific format. Sorting algorithms in data structures are methods for arranging data in a specific order, most commonly numerical or lexicographical order.

Sorting Algorithms in Data Structure

• Quick Sort
• Bubble Sort
• Merge Sort
• Insertion Sort
• Selection Sort
• Heap Sort
• Bucket Sort

What is Bubble Sort?

Bubble Sort is the most basic sorting algorithm, which operates by continually exchanging adjacent elements that are in the wrong order. This approach is unsuitable for huge data sets since its average and worst-case time complexity are relatively high.

Working of Bubble Sort

• Begin by comparing adjacent elements from the first index.
• Swap elements if the first is greater than the second.
• Continue to compare and swap adjacent elements until you reach the end of the array.
• Repeat the process for the remaining iterations, placing the largest unsorted piece at the end.
• The array has been sorted when no further swaps are required, indicating that all elements are in the correct order.

Complexity Analysis of Bubble Sort Algorithm

Time Complexity

Best Case Complexity

This occurs when no sorting is necessary, implying that the array is already sorted. The best-case time complexity for bubble sort is O(n).

Average Case Complexity

This arises when the array elements are jumbled and do not appropriately climb or descend. The average case time complexity for bubble sort is O(n2).

Worst Case Complexity

This occurs when array members must be sorted in reverse order. That is, assume you need to sort the array elements in ascending order but the elements are in descending order. The worst-case time complexity for bubble sort is O(n2).

Space Complexity

• Simple bubble sort has a space complexity of O(1) since it relies on a set amount of variables, such as loop counters and a temporary variable for swapping.
• The space complexity of optimized bubble sort is O(2) because it adds a new variable,'swapped', to the swapping variable 'temp'.