Forums Programming Assignment Help What is Quick Sort?

This topic contains 1 reply, has 1 voice, and was last updated by  aastha 3 years, 8 months ago.

Viewing 2 posts - 1 through 2 (of 2 total)
  • Author
    Posts
  • #15705

    aastha
    Member

    What is Quick Sort?

    #15706

    aastha
    Member

    Quick sort is a sorting algorithm used to sort elements of an array. Quick sort make use of a pivot which is selected using randomized selection or constrained selection and sort the array in reference with the pivot element. All the elements which are smaller in value than pivot element is placed at right of the pivot and all elements greater than pivot are placed at right of pivot hence placing pivot at correct position (position at which pivot element would be present if the array was sorted).

    Quick sort uses divide and conquer approach.

    Selection of pivot: –
    • Last element is selected as pivot.
    • First element is selected as pivot.
    • Pivot is selected at random.
    • Pivot is selected as median of the array.

    Steps involved: –
    Array-A, Size- n, i= iterator to separate element larger and smaller than pivot, j= iterator to travers

    1. Set i= A[0], j= A[1], swap pivot element with first element.
    2. If (A[1]< pivot)
    i++, j++.
    else j++
    3. while (j! = n-1)
    if(A[j]< pivot)
    swap(A[i+1], A[j])
    i++, j++
    else j++
    4. swap(A[0], A[i]) //to move pivot to its exact position.
    5. Recurs Step 1,2,3,4 on subarrays A1 and A2
    Where A1= array of elements on left of pivot.
    A2= array of elements on right of pivot.

    Time Complexity

    1. Best Case
    Best case of quick sort occurs when pivot is selected as the middle element of the array. As problem size is decreased by a factor of 2.
    Therefore,
    T(n)= 2T(n/2) + cn
    So complexity of algorithm is of the order O(nlog(n)) (by Master Method ).

    2. Worst Case
    Worst case of quick sort occurs when pivot is selected as either the smallest or the largest elements in the array. As size of the array will decrease by 1 unit and each recursive call will have n-1 elements to sort.
    So, complexity of algorithm is of the order O(n2).

Viewing 2 posts - 1 through 2 (of 2 total)

You must be logged in to reply to this topic.