Problem Description
Implement the bubble sort algorithm to sort the given integer array in ascending order.
Bubble sort works by comparing two adjacent elements and sorting them.
Repeat through all elements in the array, comparing each element with the next one and
repeatedly moving larger values to the back. This process continues until the array is sorted.
Example Input and Output
Input
[64, 34, 25, 12, 22, 11, 90]
Output
[11, 12, 22, 25, 34, 64, 90]
Bubble Sort Algorithm
Steps of the Algorithm
1. Let the length of the given array be n, and repeat n-1 times.
2. In each iteration, compare two adjacent elements.
3. If the current element is greater than the next element, swap their positions.
4. After comparing all elements, the largest number will be positioned at the end of the array.
5. Repeat this process until the array is sorted.
Swift Code Implementation
func bubbleSort(array: inout [Int]) {
let n = array.count
for i in 0.. array[j+1] {
// Swap
let temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
}
}
}
}
var arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(array: &arr)
print("Sorted array: \(arr)")
Code Explanation
In the code above, the bubbleSort function sorts the array passed as an argument.
The inout keyword allows the function to modify the array directly,
and the for loop iterates through all elements of the array. In each inner loop,
adjacent numbers are compared to change their order.
Efficiency Analysis
The time complexity of the bubble sort algorithm is O(n^2) in the worst case.
This arises from the nested loops, while the space complexity is O(1), using only constant space.
Therefore, it can be inefficient for large datasets.
However, bubble sort is often used for educational purposes due to its simplicity and ease of understanding.
Expected Benefits
Through bubble sort, students can learn the basic concepts of arrays, loops, and conditionals.
This algorithm serves as a good starting point for a fundamental understanding of other sorting algorithms
and can be used as foundational knowledge when learning more complex data structures and algorithms.
Conclusion
In this lecture, we learned how to implement the bubble sort algorithm in Swift.
It is a simple algorithm, but it plays an important role in learning the basic concepts of programming.
In the next lecture, we will explore more efficient sorting algorithms.