Data Structures and Algorithms - Old Questions

Divide-and-conquer algorithm breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem.

Divide and Conquer algorithm consists of the following three steps.

1. Divide: Divide the original problem into a set of subproblems.
2. Conquer: Solve every subproblem individually, recursively.
3. Combine: Put together the solutions of the subproblems to get the solution to the whole problem.

Given array:

78, 34, 21, 43, 7, 18, 9, 56, 38, 19

Sorting using quick sort:

......

Algorithm for Quick sort

QuickSort(A, l, r)

{

    if(l<r)

    {

        p = Partition(A,l,r);

        QuickSort(A,l,p-1);

        QuickSort(A,p+1,r);

    }

}

Partition(A, l, r)

{

    x =l; y =r ; p = A[l];

    while(x<y)

    {

       do {

                x++;

         }while(A[x] <= p);

    do {

                y--;

         } while(A[y] >=p);

    if(x<y)

        swap(A[x],A[y]);

}

A[l] = A[y];

A[y] = p;

return y;     //return position of pivot

}

Time Complexity:

Best Case: T(n) = O(nlogn)

Worst Case: T(n) = O(n²)

Average Case: T(n) = O(nlogn)