Procedure:
- If ar[j] > ar[j+1] then swap those elements
- When doing this, we'll observe that the largest element is going to the last of the array after every iteration. So there are n-i-1 elements that get sorted at the end of the array after each iteration.
- i.e if i=0(1st iteration) and n=3 (n-i-1 = 3-0-1 = 2), it means that the last element is
already in the sorted position.
- i.e if i=0(1st iteration) and n=3 (n-i-1 = 3-0-1 = 2), it means that the last element is
- the no.of times we do the above operation is n-1, i.e no.of iterations = n-1, we do not do it for n times because, in the n-1th iteration the array will already be in the sorted order.
int n = arr.length;
for (int i = 0; i < n - 1; i++){
for (int j = 0; j < n - i - 1; j++){
if (arr[j] > arr[j + 1]) {
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
-> As you see there are two loops, one is iterating for n-1 times and the inner loop is iterating for n-i-1 times, so the complexity is
n-1 * (n-i-1) -> the highest degree when we multiply these two is n^2
so Time complexity -> O(n^2)
Space Complexity -> O(1)