Page 261 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes T(n) comes out to be:

T(n) = c*n +T(n-1)
= c*n + c*(n-1) + T(n-2)
= 2*c*n - c + T(n-2)
= 2*c*n - c + c*(n-2) + T(n-3)
= 3*c*n - 3*c + T(n-3)
= n*c*n-n*c + T(1)

= n2c-nc+1
2
Therefore T(n) n , hence the order is O(n ).
2
Space Complexity

The average case space complexity is log n, because the space complexity depends on the
2

maximum number of activations that can exist. We find that if we assume that every time the list
gets splitted into approximately two lists of equal size then the maximum number of activations
that will exist simultaneously will be log n.
2
In the worst case, there exist n activations because the depth of the recursion is n. Hence, the
worst case space complexity is O(n).

Algorithms of Quick Sort

The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:
1. Choose a pivot value. We take the value of the middle element as pivot value, but it can be
any value, which is in range of sorted values, even if it doesn’t present in the array.
2. Partition. Rearrange elements in such a way, that all elements which are lesser than the
pivot go to the left part of the array and all elements greater than the pivot, go to the right
part of the array. Values equal to the pivot can stay in any part of the array. Notice, that
array may be divided in non-equal parts.

3. Sort both parts. Apply quicksort algorithm recursively to the left and the right parts.
Partition Algorithm in Detail

There are two indices i and j and at the very beginning of the partition algorithm i points to the
first element in the array and j points to the last one. Then algorithm moves i forward, until an

element with value greater or equal to the pivot is found. Index j is moved backward, until an
element with value lesser or equal to the pivot is found. If i ≤ j then they are swapped and i steps
to the next position (i + 1), j steps to the previous one (j - 1). Algorithm stops, when i becomes
greater than j.
After partition, all values before i-th element are less or equal than the pivot and all values after
j-th element are greater or equal to the pivot.

256 LOVELY PROFESSIONAL UNIVERSITY