Sorting

Question 1

Selection Sort

Sort the array in ascending or descending order.

TC – O(N2)
SC – O(N)

Answer 1

Pseudo code:

1. We will take two for loop.
2. Outer loop will start from 0 to array length -1. (I th)
3. Inner loop will start from outer loop index plus one. (J th)
4. Compare outer loop indexth element to inner loop indexth element and if it’s greater than swap them.

Question 2

Bubble Sort

Sort the array in ascending or descending order.

TC – O(N2)
SC – O(N)

Answer 2

Pseudo code:

1. We will take two for loop.
2. Outer loop will start from 0 to array length -1. (I th)
3. Initialize Boolean variable swap.
4. Inner loop will start from array length -1 and j grater than outer loop indexth element. Let’s assume variable name is j. Compare adjacent element.
5. Compare j and j-1th element, if it’s small than swap.
6. If swapping any element then update Boolean variable to true.
7. After inner loop end, check if swap variable is false, means there is no element to sort, list is sorted now, break outer loop.

Takeaway: Point 7 is making bubble sort better than selection sort.