Sorting

Question 1

Bubble Sort

Answer 1

In bubble sort, in every iteration the next greater element bubbles up to its correct position.

So we need to iterate as follows:

for i from 0 to n-1:
for j from 0 to n-i-1:
if arr[j] > arr[j+1]: swap

Question 2

Insertion Sort

Answer 2

for (int i = 1; i < n; i++){
    int key = arr[i];
    int j =i;
    while(j > 0 &amp;&amp; arr[j-1] > key){
        arr[j] = arr[j-1];
        j--;
    }
    arr[j] = key; 
}

Question 3

Count Inversions in a Sorted Array

Answer 3

In a sorted array, 2 elements form an inversion if a[i] > a[j] and i < j.

def merge_modified(a,n,l,r):
    count = 0
    if l>=r: return count
    count += merge_modified(a,n,l,mid)
    count += merge_modified(a,n,mid+1,r)
    count += merge(a,n,l,mid,r)

At any step in merge(), if a[i] is greater than a[j], then there are (mid – i) inversions.

i=l
j = mid+1
while i<= mid and j <= r:
        if a[i] > a[j]:
            count += mid-i+1

Question 4

Count Possible Triangles in Unsorted Array

Answer 4

Method 1: Sort the array. Take i =0, j= i+1 and find greatest k such that a[k] < a[i] + a[j}. Then we know no of triangles form by i, j as 2 sides are k-j-1.
Then increment j by 1 and now use previous value of k

Method 2: Sort the array. Take i=n-1, l=0, r= i-1 and while l