Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n^2) algorithm.
Key Idea
Each iteration the largest element will be bubbled to the top.
Debug
Why this implementation is wrong? hint: what do you know for sure after each iteration in the outer loop?
def sortIntegers(self, A: List[int]) -> None:
"""
Bubbling up the current element to the end of the list is also an option.
"""
n = len(A)
for i in range(n):
for j in range(i, n-1):
if A[j] > A[j+1]:
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
Code
public void bubbleSort(int[] arr) {
// each outer loop guarantees the largest element
// is bubbled to the right place
for (int i = 0; i < arr.length - 1; i++)
for (int j = 1; j < arr.length - i; j++)
if (arr[j-1] > arr[j]) swap(arr, j-1, j);
}
private void swap(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
func sortIntegers (A *[]int) {
arr := *A
if arr == nil || len(arr) == 0 {
return
}
// for each element swap the smallest value to the front
for i := 0; i < len(arr); i++ {
for j := i; j > 0; j-- {
if arr[j-1] > arr[j] {
swap(A, j-1, j)
}
}
}
}
func swap (A *[]int, i, j int) {
arr := *A
temp := arr[i]
arr[i] = arr[j]
arr[j] = temp
}
def bubbleSort(A: List[int]) -> None:
"""
Bubbling the largest element to the end of the list
"""
n = len(A)
for i in range(n):
for j in range(n-i-1):
if A[j] > A[j+1]:
swap(A, j, j+1)
def swap(A: List[Any], i: int, j: int) -> None:
temp = A[i]
A[i] = A[j]
A[j] = temp
Time & Space Complexity
Optimization
We can add a flag to check if the inner loop has 0 swaps. That will improve the best case to O(n).
Bubble sort has quite a few nice properties. Since it only involves swapping elements, it is in-place. The finishing order is also stable. The time complexity can be calculated with a simple summation i=0∑n−1i=n2.
