1. Problem Definition
Write a function to sort a given integer array in ascending order.
You must implement it using the bubble sort algorithm, which is the most basic sorting method,
and include the process of optimizing the code considering time complexity and space complexity.
Problem: Given an arbitrary integer array, write a Swift function that uses
the bubble sort algorithm to sort this array in ascending order.
2. Overview of Bubble Sort Algorithm
Bubble sort is a simple sorting algorithm that works by comparing two adjacent elements and
swapping them if they are not in the correct order. This process is repeated for all indices of the array,
and in the worst case, it has a time complexity of O(n²) when the size of the array is n.
The main characteristics of bubble sort are as follows:
- Simple and easy to understand algorithm
- Usually easy to implement and useful for small datasets
- Worst case O(n²), average O(n²), best case O(n) (when already sorted)
3. Algorithm Steps
The basic method of using bubble sort is as follows:
- Start by comparing adjacent elements from the first element of the array.
- If the first element is greater than the second element, swap the two elements.
- Repeat this process until the end of the array.
- When you reach the end of the array, the largest element will move to the end of the array.
- Repeat the above steps n-1 times.
This process ensures that the largest element moves towards the end at each step.
Bubble Sort Implementation (Swift Code)
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
swapped = true
}
}
// If no two elements were swapped by inner loop, then break
if !swapped {
break
}
}
}
4. Code Explanation
The above bubbleSort function takes an array as an argument and sorts it in ascending order.
Key Points:
inoutkeyword allows the function to modify the array directly.- The reason for using
n-i-1in the second for loop is that with each iteration the largest element moves to the end of the array.
Therefore, the last element is already sorted and does not need to be checked. - The
swappedvariable checks if the sorting is already completed to reduce unnecessary iterations.
5. Testing and Example
Below is an example that tests the bubbleSort function.
var myArray = [64, 34, 25, 12, 22, 11, 90]
print("Before sorting: \(myArray)")
bubbleSort(&myArray)
print("After sorting: \(myArray)")
Running the above code will display the array before and after sorting.
This will confirm that the bubble sort algorithm has been implemented successfully.
6. Time Complexity and Optimization
The time complexity of bubble sort is O(n²) in the worst case.
Even when the array is already sorted, it can perform at O(n) in the best case.
To optimize this, the swapped variable can be introduced to avoid unnecessary iterations.
In Swift, using bubble sort for large arrays is inefficient.
In this case, it is recommended to use advanced sorting algorithms (e.g., Quick Sort, Merge Sort).
7. Conclusion
In this tutorial, we explored how to implement the bubble sort algorithm in Swift and its process.
Bubble sort is easy to understand and simple to implement, but its performance may degrade in real usage.
Therefore, when dealing with complex datasets, other algorithms should be considered.
In the next tutorial, we will cover the more efficient sorting algorithm called Quick Sort.
8. References
For a deeper understanding of the algorithm, please refer to the materials below: