Explain concept of divide and conquer algorithm time complexity of quick sort algorithm

Question

Suresh Chand · Accepted Answer

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. Divide: Divide the original problem into a set of subproblems. Conquer: Solve every subproblem individually, recursively. 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; } Time Complexity: Best Case: T(n) = O(nlogn) Worst Case: T(n) = O(n2) Average Case: T(n) = O(nlogn)

Explain concept of divide and conquer algorithm. Hand test quick algorithm with array of numbers (78, 34, 21, 43, 7, 18, 9, 56, 38, 19).sorting What is time complexity of quick sort algorithm?

Leave your Answer:

Hits Counter

Question

Explain concept of divide and conquer algorithm. Hand test quick algorithm with array of numbers (78, 34, 21, 43, 7, 18, 9, 56, 38, 19).sorting What is time complexity of quick sort algorithm?

Leave your Answer: