Sorting

SORTING

BUBBLE SORT

Total comparisons   f(n) = O(n²)

SELECTION SORT

Total comparisons   f(n) = O(n²)

INSERTION SORT

QUICK SORT

Efficiency of QUICK SORT

T(n) =       a                                               n=1

Cn + T(n/2) + T(n/2)                 else

Where,

Cn            –       time required to partition array

T(n/2)       –       time required to sort left subarray

T(n/2)       –       time required to sort right subarray

=> worst case complexity         =      O(n²)

---

This algorithm sorts the array A with N elements Step1.        Initialization Set I = 0 Step2.        Repeat steps 3 to 5 until I < N Step3.        Set J = 0 Step4.        Repeat step 5 until J < N – I – 1 Step5.        If A[J] > A[J+1] Set temp = A[J] Set a[J] = A[J+1] Set A[j+1} = temp End if Step6.        Exit