Minimizing waiting time – Greedy Algorithms – 2

Question.We are given n requests which need to be serviced. Assume that all requests are given to us at time t=0. It takes time, t [i] to service request i.

The waiting time of request , denoted by W[i] is defined as :

. (where the summation is over all requests serviced prior to servicing request i.)

We want to service the requests such that the total waiting i.e. the sum of the waiting times of the n requests, is minimized.

Solution.

This is a simple application of the greedy paradigm.

As is intuitively clear, we would like to service shorter requests first, before moving on to requests with a larger t [i] value.

We make the intuition concrete as follows:

——–

Sort the n requests in non-decreasing order of t[i] values.

Service the requests in this order.

——–

Intuitive proof of correctness of algorithm:

Consider what happens when you have to decide which request to service, and there are more than one requests. Consider any 2 such requests. If you schedule the request with the larger t[i], it would mean that the other request would have to wait for that larger amount of time before being serviced, thus adding that large quantity to the total waiting time. On the other hand, in case you service the smaller request first, the addition to the total waiting time would only be equal to the t[i] value of the smaller request. Hence, whenever you have a choice, go for the request with the smaller t[i] value.

This directly translates to the above algorithm.

——–

Scheduling Tutors – Greedy Algorithms – 1

Question.We are a tutor-scheduling organization. We have at our disposal an infinite number of tutors using whom we service the tutoring requests that come our way.

Consider any particular day. We get a certain number of tutoring requests. Each request has a specified starting time, and the duration of the tutoring session is exactly 30 minutes. Each tutor can work for any continuous period of 2 hours in a day. (The tutor need not actually be tutoring for the whole of the 2 hours; it is just that he/she will certainly not tutor outside of that 2 hour period.) We are the ones who decide the starting time of the 2 hour working period for each tutor.

We also need to remember that a tutor cannot service more than one request simultaneously.

Our aim is to service the tutoring requests using a minimum number of tutors. How can we achieve that?

Solution.

We can tackle this problem greedily.

We order the requests in non-descending order on the basis of their starting times. Take the first request. Schedule a tutor to start his/her 2 hour period at exactly the starting time of the 1st request. Now, look at the 2nd request. Ask yourself the following question: Can the 1st tutor (i.e. the one who has already been scheduled to work) also service this request? If yes, let him/her do so. If not, schedule a 2nd tutor to start his/her 2 hour period at exactly the starting time of this new request. Continue in the same manner for the succeeding requests. i.e. Do the following: For each new request, check if that request can be serviced by any of the tutors already scheduled to work. If yes, schedule the tutor who has the shortest time remaining in his/her 2 hr period, to service this request. If not, schedule a new tutor to start his/her 2 hour period at exactly the starting time of this new request.

——-

In pseudo code form, we would have:

Sort the requests in non-decreasing order of starting times.

count = 0; // this is the # of tutors assigned thus far.

flag = UNSERVICED. // an indicator for whether a particular request has been serviced or //not.

While (one or more requests remain to be serviced)

Remove the 1st request from our sorted list.

For ( each of the tutors scheduled thus far )

//Note: we iterate through the already assigned tutors in the order in which they were

// assigned (so as to be able to schedule the tutor with the least remaining time in

// his/her 2 hr period.

If ( that tutor can service this request )

Schedule him/her to service this request.

Come out of the For loop.

Set: flag = SERVICED.

If (flag == UNSERVICED)

// means that no already scheduled tutor was able to service the new request.

// We need a new tutor.

Assign a new tutor to start his/ her 2 hr period at the starting time of the new request.

Set: flag = UNSERVICED.

count ++ ;

End of While loop.

End.

———-

Analysis of running time:

- Say there are n requests. Sorting them will take O(n log n) time.

- In the worst case, we might need to schedule n tutors to service n requests.In such a scenario, the time required for assigning tutors will be (this is because of the fact that before we assign a new tutor we check with each of the already assigned tutors as to whether they can service the new request).

- Hence, the algorithm will run in time.

———-

Intuitive proof of correctness of the algorithm:

- Consider the 1st request (in sorted order). Obviously, since no tutors have been assigned thus far, we need to schedule a new tutor for this request. Now, consider the choice we have wrt when to schedule this new tutor. Certainly, we cannot schedule him/her to start his/her 2 hr period after the starting time of the 1st request. If we schedule him/her to start working before the starting time of the 1st request, the time that elapses between the moment the tutor’s 2 hr period starts and the starting time of the 1st request would be effectively wasted. Hence, the best thing would be to schedule the 1st tutor to start his/her 2 hr period at exactly the starting time of the 1st request.

- Similarly, one can argue that for each newly assigned tutor, the algorithm chooses exactly the right time for him/her to start their working period.

- Also, we observe that the algorithm does not assign any new tutors unless there is a need to do so.

- And finally, the algorithm always schedules a tutor with the least remaining time in their schedule to service a new request (when selecting among already assigned tutors). This results in maximum number of requests being serviced by already assigned tutors without having the need to assign a new one.

————–

Dynamic Programming – 6 : Optimum sum of tree nodes

Optimum sum of tree nodes

We are given a rooted tree with root . Each node has a real value associated with it. We are to find a subset of nodes of the tree, such the sum of the values of the selected nodes is maximized, subject to the condition that if we choose a node , we cannot choose any of its children or its parent.

Solution.

Notation. Let denote the optimum value on a sub-tree rooted at node . Let denote the optimum value on a sub-tree rooted at node subject to the condition that is selected as part of the optimal subset. Let denote the optimum value on a sub-tree rooted at subject to the condition that is not selected as part of the optimal subset.

Then, we have that:

.

(where the summation is over all children of .)

(where the summation is over all children of .)

—

Also, if is a leaf, then , and .

Pseudocode for computing OPT(root)

We can compute OPT(root) in a bottom up fashion starting from the leaves. The recurrence equations for a node involve the OPT values for its children. Thus, before computing the value for node , we compute the values for its children.

Let the nodes of the tree be arranged in levels from Level 0 till Level L such that the root is at Level 0.

For i going from L downto 0:

For all nodes x in Level i:

Compute OPT[1,x], OPT[0,x] and OPT[x] using the above recurrence.

Set Soln[x] = 1 if OPT[1,x] >= OPT [0,x]. Else, set Soln[x] = 0.

End.

—-

The above code has a running time of where represents the number of nodes in the tree. [ We compute OPT values for n nodes. For each node, we compute the OPT values by summing up the OPT values over all of its children. Aggregating over all nodes, and observing the each node can have at most one parent, we find that the summing up operation costs O(n). Therefore, the total cost is O(n+n) which is O(n). Another way to look at it is that the aggregate cost of the summing up operations over all nodes is O(m) [where m represents the number of edges in the tree], which for a tree is O(n). ]

—-

Computing the optimal subset:

We do so using the Soln[x] values.

Function: Print_Solution (x)

If (Soln[x] == 1)

Print x.

For all grand-children y of x:

Print_Solution (y);

Else

For all children y of x:

Print_Solution (y);

End.

—-

Print_Solution(root) has a running time of .

—-

Dynamic Programming – 5 : Matrix chain multiplication

Matrix chain mnultiplication

We are given a sequence of matrices , such that matrix has dimensions . Our task is to compute an optimal parenthesization of this sequence of matrices such that the sequence is fully parenthesized.

Terminology: A sequence of matrices is fully parenthesized if the sequence is either a single matrix or a product of 2 fully parenthesized sequences.

Optimality here refers to minimization of the number of scalar multiplications involved in computing the product of the matrix sequence.

—

Note 1:

// C code for multiplying A (m x n) with B (n x p). Product is C (m x p).

for (i=0; i < m; i++)

for (j=0; j < p; j++)

{

C[i][j] = 0;

for (k=0; k<n; k++)

C[i][j] + = A[i][k] * B[k][j];

}

//End of code.

—

Note 2: From the above, we can see that multiplying an (m x n) matrix with a (n x p) matrix requires m x n x p scalar multiplications.

Note 3: Matrix multiplication is associative. So, we can parenthesize the given sequence of matrices whichever way we want as long as we do not disturb the sequence itself.

—-

Solution.

If n > 1, we know that the required parenthesization divides the matrix sequence into 2 smaller fully parenthesized sequences.

Let this division occur at matrix , i.e. the number of scalar multiplications in equals the sum of the number of scalar multiplications in and plus the value .

Notation: Let denote the number of scalar multiplications in the optimal parenthesization of the sequence .

From the above, we have that:

.

Generalizing this, we can say that, for :

Further, for all possible .

—-

Pseudocode for computing optimum number of scalar multiplications:

For i from 1 to n:

For j from 1 to (n-i):

Compute OPT [i,j] according to the above recurrence.

Set Soln[i,j] = k; // k is the index that optimizes OPT[i,j] in the recurrence.

End of algorithm.

—

The above code will take to find (in the process, computing the OPT[i,j] and Soln[i,j] table values).

—

Computing the optimal solution i.e. parenthesization

We can do so using the Soln [i,j] table.

Function: Print_Solution (i, j)

If ( i == j)

Print

Else

Print (

Print_Solution (i, Soln[i,j] );

Print_Solution ( Soln[i,j] + 1, j);

Print )

End.

—-

This function takes time for the call Print_Solution (1, n).

—

Dynamic Programming – 4 : Sequence Alignment

Sequence Alignment

We are given 2 sequences and . Our task is to produce a valid matching of the elements of and such that the cost of the matching is minimized.

Terminology:

A valid matching denotes a one-to-one correspondence of (some subset of) elements of and with the added condition that there should be no crossing in the matching.i.e. if is matched to , and is matched to , then implies .

e.g.

X = < e l e p h a n t >

Y = < m o n k e y >

The matching refers to the valid matching where we match and and . Note that there are no crossings in .

—

Cost of a matching is the sum of:

(1) matching cost for each .

(2) gap cost for each element of or which is not part of .

—

Solution.

Given and , we have 2 choices: either include in the optimum matching, or exclude it from the optimum matching.

Case 1:

If is part of optimum matching, then the optimum cost would be plus the optimum cost of matching the sequences and .

Notation: Let denote the optimum cost of matching and .

Therefore, we have:

–

Case 2:

If is not part of the optimum matching, then one of the following should hold true (because of the no crossing condition):

(1) is not part of the optimum matching.

or, (2) is not part of the optimum matching.

Therefore, we have:

—-

Generalizing the above recurrence, we have, for and :

Also, we have the base conditions that:

for all ; and analogously for .

—-

Pseudocode for computing optimum value:

Initialize OPT [i, 0] and OPT [0,j] as given above.

For i from 1 to m:

For j from 1 to n:

Compute OPT [i,j] using the given recurrence.

End of algorithm.

—-

The above algorithm computes the optimum value in time.

—-

Computing the optimum solution using OPT [i,j] values:

Let us denote :

(1) by Expr1.

(2) by Expr2.

(3) by Expr3.

Function: OPT_Solution (i,j)

If (i = = 0) OR ( j = = 0)

Return;

If Expr1 <= both Expr2 and Expr3

OPT_Solution (i-1, j-1);

Print: Index i of X is matched to Index j of Y.

Else if: Expr2 <= both Expr1 and Expr3

OPT_Solution (i, j-1);

Else:

OPT_Solution (i-1, j);

End of function.

—-

What we want to compute is OPT_Solution (m, n). The above function computes that in time .

—-

Dynamic Programming – 3 : Subset Sum

Subset Sum

We are given items , each having non-negative integral weight . We are also given a non-negative integral weight bound . Our task is to find a valid subset of items which maximizes the total weight of the items in the subset.

Terminology: A valid subset is one such that the total weight of items in is at most .

Solution.

For item , we have 2 choices : either to include it in the optimum solution, or to not include it.(Note that if , then we have just one choice  — exclude from the optimum solution.)

Case 1:

If is included in the optimum solution, the optimum solution would be plus the optimum solution obtained from the set of items with the weight bound as .

Notation: Let OPT (i, w) denote the value of the optimum solution obtained on the set with weight bound .The original task, then, is to compute .

We have that, if is included in the optimum solution,

.

Case 2:

If is not included in the optimum solution, then we have that:

.

—-

Generalizing the above, we have that, for and :

[if ]

Else,

—-

Also, for all .

—-

Pseudocode for computing the optimum value:

Based on the above recurrence, we can construct an algorithm.

For i from 1 to n:

For w from 0 to W:

Compute OPT[i,w] using the above recurrence.

End.

—-

The above code runs in time [since O(1) time is spent for computing each OPT[i,w] value].

—-

Computing the Optimum solution:

We can compute the optimum solution recursively given the table of OPT[i,w] values.

Function: Print_OPT (k, w)

If

Return;  //Breaking the recursion. We can also have the condition as OR

If

Print_OPT (k-1, w);

Else if

Print_OPT (k-1, w- w_k);

Print

Else

Print_OPT (k-1, w);

End of function.

—

The optimum solution is printed on calling Print_OPT (n, W). The time taken is O(n).

—-

Dynamic Programming – 2 : Longest Common Subsequence

Longest Common Subsequence (LCS)

We are given 2 sequences and . Our task is to find the LCS of X and Y.

Terminology: A subsequence of X is a set of elements that can be obtained from the elements of X such that no 2 two elements of the subsequence are out of order wrt the ordering defined by X. e.g. if X = < E L E P H A N T >, then < E P H T>, < E E A > etc are subsequences of X.

A common subsequence of X and Y is a sequence Z that is a subsequence of both X and Y. The longest such Z is an LCS.

—

Solution.

Let OPT (m, n) denote the length of an LCS of X and Y. (Note that there may be more than one LCS’s, each of them having the same optimum length.)

Either of these 2 cases is true : either or .

Case 1:

If then we can certainly include that element in the LCS and proceed to finding the LCS of and .

Notation: Let denote . is defined analogously.

Notation: Let denote the length of the LCS of and .

Therefore, we have that:

(if )

Case 2:

If , then we have that:

.

—–

Generalizing the above, we have that, for and :

(if

and

(if )

—–

We can use the above recurrence to compute the optimum length in a bottom up fashion.

Pseudocode for computing the optimum length:

Initialize OPT (0, i) and OPT (j, 0) to be 0 for all 1 <= i <= n, and 1 <= j <= m.

For i from 1 to m:

For j from 1 to n:

Compute OPT (i,j) and OPT (j,i) using the above recurrence.

End of algorithm.

—-

What we want is the length of OPT (m,n). The above algorithm computes OPT(m,n) in O(mn) time.

—-

Using the table of OPT (i,j) values, we can compute the LCS recursively.

Function: OPT_Solution (i,j) :=

If (i == 0) OR ( j == o)

// Exit; Break recursion.

Return;

If

OPT_Solution (i-1, j-1);

Print

Else if

OPT_Solution (i-1, j);

Else

OPT_Solution (i, j-1);

End of algorithm.
—-
The above code for printing the LCS runs in O(m+n) time.

—–

Dynamic Programming – 1 : Weighted Interval Scheduling

In general, problems on dynamic programming can be solved by first expressing the required optimum solution in a recursive fashion, and then solving the recurrence in a bottom-up fashion.

Weighted Interval Scheduling

We are given intervals, with each interval having start time , finish time and non-negative weight ( for from 1 to ).

Our task is to find a compatible subset   of these intervals so as to maximize for the intervals in .

(A compatible subset is one where no two intervals ever overlap. )

—-

Solution.

Let us assume that the intervals are sorted in the order of their finish times. Let this ordered list of intervals be .

Let OPT (n) denote the value of optimum solution. (i.e. the sum of weights of intervals in an optimum solution.)

Consider interval .

The optimum solution may either include or not include .

If the optimum solution does not include , then we have:

.

Notation: Here, denotes the optimum value computed from the set of intervals .

If the optimum solution does includes , then, apart from , the optimum solution can only include those intervals which do not overlap with it, i.e. only those intervals, for which .

Notation Let denote the index of the interval, for which (1) , and (2) . Also, if all intervals have finish times , then .

Thus, we have that, if the optimum solution includes , then:

.

Therefore,

Generalizing, we have that, for :

and that, .

—–

Using the above recurrence, we can write an algorithm to solve it in a bottom-up fashion:

/* Assuming that intervals are sorted according to values we have values for all intervals. */

OPT (0) = 0;

For i from 1 to n:

Compute OPT(i) using the above recurrence.

Return OPT (n).
End.

—–

The above algorithm takes O(n) time.

Sorting the intervals by values takes (using merge sort or quick sort), following which we can compute values for all intervals in time (by calling a slightly modified binary search routine times).

Therefore, the algorithm will run in time.

——

Computing the optimal solution from the optimal value:

Once we have the OPT values, we can compute the optimal solution (i.e. the sets of intervals, not just the value) recursively as follows:

Function: OPT_Solution ( k ) :=

If ( k == 0 )

//Do nothing. Break recursion.

Return;

For i decreasing from k to 1:

If [ OPT ( p(k) ) + W_k >= OPT (k-1) ]

OPT_Solution ( p(k) );

// Include interval k in Optimum solution

Print k.

Else

OPT_Solution (k-1);

End of function.

—-

The function OPT_Solution (n) has a worst-case running time of O(n) [because there can be at most n recursive calls (since the argument passed to the function calls strictly decreases), and the time taken to process the non-recursive part of each call is O(1) ).

—-

 

Matching parentheses

We will look at an interesting problem of evaluating whether a sequence of left and right parentheses is balanced.

Firstly, we need to know what is meant by the sequence being balanced. What we basically mean is that for every left parenthesis, there exists a corresponding right parenthesis, and also that, for every right parenthesis there exists a matching left parenthesis.

Let’s consider a few examples:

( )  : This simple sequence is balanced. i.e. There is only one left parenthesis in this sequence, and it has a matching right parenthesis. Also, there is only one right parenthesis in this sequence, and that has a matching left parenthesis.

( ( ) ) : This sequence is also balanced.

For clarity, let us index the elements of this sequence using the indices 1, 2, 3, 4 as we would do in the case of an array. (i.e. “(” ( ( ) — the highlighted “(” is Seq [1]. Similarly,  in ( ( “)” ), the highlighted “)” is Seq [3].)

Now, in the sequence ( ( ) ), we need to observe 2 things in order to ascertain whether or not it is balanced:

1. Every left parenthesis has a matching right parenthesis.

This can be seen to be true. Seq [1] has Seq [4] as its match, and Seq [2] has Seq [3] as its match.

2. Every right parenthesis has a matching left parenthesis.

Again, this is easily seen to be true. Seq [3] has Seq [2] as its match, and Seq [4] jas Seq [1] as its match.

Thus,  ( ( ) ) is balanced.

Now consider this example:

(  (  (  )  )  (  ) )

This sequence is also balanced because:

1. Every left parenthesis has a matching right parenthesis.

Seq [1] has Seq [8]; Seq [2] has Seq [5]; Seq [3] has Seq [4]; Seq [6] has Seq [7].

2. Every right parenthesis has a corresponding left one. This can be easily verified.

—

To see why both of the above requirements need to be satisfied in order for a sequence to be balanced, consider the following two examples:

( ) )

Here,

(1) Every left parenthesis has a matching right parenthesis. (Seq [1], the only left parenthesis in our sequence, can be matched to Seq [2].)

(2) Every right parenthesis does not have a matching left parenthesis. Seq [2] has Seq [1] as its match, but Seq [3] does not have any match.

Therefore, ( ) ) is not balanced, which also seems correct from what one would intuitively understand from the word “balanced”.

Similarly, it can be easily verified that ( ( ) is not balanced.

—

To develop a method for determining whether or not a sequence is balanced, let’s first look a bit more at what is meant a matching parenthesis.

Consider :

(         (           )            (             (            )           )            )

[1]    [2]      [3]         [4]          [5]       [6]        [7]         [8]

As can be seen, the matching left parenthesis for :

Seq [3] is Seq [2],

Seq [6] is Seq [5],

Seq [7] is Seq [4],

Seq [8] is Seq [1].

Intuitively, one can understand the method by which the brain works out which left parenthesis is the match for a given right parenthesis.

Read  the input from left to right. As soon as you encounter a right parenthesis (we know that its matching left parenthesis should have occurred earlier, and our intuitive definition of matching parenthesis tells us  that this matching left parenthesis is the one nearest to the right one that we read), the matching left parenthesis is the one that is exactly one index before it.

[In our example, this would translate to reading the input left to right from Seq [1] to Seq [3]. At Seq [3], we encounter a right parenthesis, and decide that its matching left parenthesis is Seq [2]. )

Now, since we’ve matched a left and right parenthesis, we don’t care about them anymore. So we assume that they have been removed from the sequence.

[ In our example, this would mean removing Seq [2] and Seq [3] from our sequence.]

We continue reading the input from left to right, and as soon as we encounter a right parenthesis, we decide that its matching left parenthesis based on the facts that the left parenthesis that we are finding (1) occurs before it, and (2) is the one closest to the right parenthesis under consideration (from among all the left parenthesis that we have not yet removed from consideration).

[In our example, this would translate to reading : Seq [4] , Seq [5] and Seq [6]. We encounter a right parenthesis at Seq [6], and search for its matching left parenthesis. We see that Seq [5] is a left parenthesis that has not yet been matched (i.e. is still part of the sequence), occurs before Seq [6], and is the closest such left parenthesis to Seq [6].

Once, we’ve done that, we remove Seq [5] and Seq [6] from our sequence. ]

We continue in the same vein — reading the input from left to right from the point where we left off, stopping at a right parenthesis, searching for its matching left parenthesis, and, on finding such a match, removing both of the matched parentheses from the sequence, and continuing the same process again.

[In our example, this becomes:

Read Seq [7]. Now, since, Seq [5] has already been matched (i.e. no longer part of our sequence), the correct match for Seq [7] becomes Seq [4].

Remove both Seq [7] and Seq [4] from the sequence.

Read Seq [8]. Stop, and search for its match.

We see that Seq [1] is the match (all other left parentheses have been removed).

We match Seq [1] and Seq [8], and remove both from the sequence.

We now find that the sequence is empty, and the input is also over, which means that we have matched all parentheses and that the sequence is balanced. Of course, if the sequence weren’t balanced, this wouldn’t be the case.]

—-

Now, that we have understood the idea, it should be easy enough to understand the method used to determine whether or not a sequence a balanced.

1. Scan the input from left to right, and while doing so, perform the following actions:

(i)  if you encounter a left parenthesis, push it into a stack. (This stack is initially empty.)

(ii) If you encounter a right parenthesis, pop the top-most left parenthesis (if it exists) from the stack.

2. If there are no more symbols to be read from the input :

(i) and the stack is empty, the sequence is balanced; end the algorithm.

(ii) and the stack is not not empty (i.e. contains some left parentheses), the sequence is not balanced; end the algorithm.

3. If you encounter a right parenthesis, and the stack is empty, then the sequence is not balanced; end the algorithm.

—

The above algorithm using stacks is based exactly on the approach we saw earlier, and helps us to decide whether or not a sequence is balanced.

Quick Sort

As the name suggests, quick sort is indeed a quick sorting technique.

Suppose that you have to sort an array of n integers. The method used in quick sort is to choose a pivot element, traverse the array and rearrange the elements such that all elements less than (or equal to) the pivot element are placed to the left of the pivot element, and those that are greater than the pivot element are placed to its right.

What we can observe here is that the pivot element has been placed in its correct final position (i.e. the position where it would be after the array is completely sorted).

So, now we need to only concentrate on rearranging the elements to the left and to the right of the pivot element. And to do so, we perform quick sort separately on the left-elements and on the right-elements.

Let’s look at an example.

Suppose the array we want to sort is: 23   12   3   43    26     18     95     6    34     11.

1. We observe first of all that if an array has just one element, or has no elements, the array is trivially sorted.

2. First, we select a pivot element. Let’s say it is 23.

3. We traverse the array once from left to right, and divide the elements into two parts (those less than, and those greater than, the pivot).

We compare 12 to 23, and find that 12 < 23 and hence, 12 would occur to the left of 23 at the end of this stage. We then compare 3 to 23, and again finding that 3 < 23, place 3 to the left of 23. Next, we compare 43 to 23. We find that 43 > 23, and hence place 43 to the right of 23. We similarly go through each of the remaining elements of the array, and place them either to the left or to the right of the pivot element.

At the end of this step, the array that we have is as follows:

12   3    18      6      11     23 43      26      95      34.

—-

Before proceeding to the next step, we observe an important point: at the end of Step 3, we find that the pivot element 23 is placed in position # 6, which is also its rightful position in the completely sorted array.

—-

4. We now look to sorting two smaller arrays — the ones to the left and to the right of the pivot element.

We resort to recursion in order to sort the arrays (12, 3, 18, 6, 11) and (43, 26, 95, 34).

[In order to sort the array on the left, we select a pivot (let's say 12) and repeat Step 3 and Step 4 for this array. Similarly, we sort the array on the right of the pivot element. While doing so, we keep in mind the observation in Step 1.]

—–

Running time of Quick Sort algorithm (best-case scenario) :

1. Let’s say we always select the first element of the array as the pivot element. So, it takes O(!) time to select the pivot element.

2. Now, we use the pivot element to divide the array into elements less than (or equal to) and greater than the pivot element. This division of the array takes O(n) time (where n refers to the size of the array).

3. In our best-case scenario, we assume that the array gets divided into 2 (almost) equal halves. (i.e. the pivot element always divides the array as equally (in size) as possible).

Thus, we get the following recurrence relation:

T(n) <= 2 T(n/2) + kn.

Here, T(n) refers to the running time of the algorithm on an array of size n, and k is a constant.

We also have, T(1) = T(0) = O(1)  [this is another way of writing what we wrote earlier in Step 1.]

Thus, we get T(n) is O(n log n).

—-

Now, let’s look at the worst-case running time of Quick Sort.

To look for the worst-case scenario, we’ll assume that the pivot element always divides the array as unequally as possible.

Consider the following array:

2    5     9     14     45      56     89.

If we always use the first element as the pivot element, we find that the array gets divided in a totally lop-sided manner.

The recurrence that we get is as follows:

T(n) <= T(n-1) + kn.

This means that T(n) is O(n^2).

—-

A final note: Always selecting the first element as pivot can lead us into trouble (as we saw above in the worst-case scenario). A way of somewhat circumventing this problem is to pick the pivot element randomly from among the elements of the array. This is what is known as randomized quick sort.

Sorting things out with Selection

Not  long after you’ve been introduced to writing programs would a typical programming instructor teach you how to sort a list of elements. Despite our stated (or, is it unstated) aversion to the instructional approach generally employed, let us go ahead and expound a bit on sorting.

You are given an array of n elements. We assume that we know how to compare any two elements of the array with one another (in other words, you wouldn’t be asked to compare apples and oranges). Let us assume that the array is one of n integers. We wish to sort the elements such that the smallest element occurs first, followed by successively larger elements.

1. Selection Sort

As the name suggests, we sort by performing some “selection”.

Take an arbitrary array of 5 elements – 23, 11, 54, 34, 27.

Now, we know that the sorted order is: 11, 23, 27, 34, 54.

As is clearly seen, 11 is the minimum element in this array, and occurs first in the sorted list. If we remove this 11 from the array, we find that 23 is the minimum element from among the ones remaining. Hence, 23 occurs in the sorted list just after 11. Similarly, on removing 23 also from the array, we find that 27 is the minimum from among the remaining elements, and unsurprisingly, occurs right after 23 in the sorted order.

So, we can see our modus operandi — Select (and remove) the minimum element in the array, and add it to the sorted list.

–

We’ll digress here for a bit to figure out how exactly we find the minimum element in an array.

Let’s take the following array — 23, 54, 15, 11, 46. We know that the 4th element of the array – 11 is the minimum.

Let’s assume that we read the elements of the array one by one from left to right.

We begin by reading 23. Since it is the only element that we have read so far, and we have no other element to compare it with, 23 is the least element we have encountered thus far. So, our current minimum is 23.

We next read 54. We compare it with the current minimum, which is 23. Now, 54 >23, and hence, the minimum encountered thus far remains 23.

Now, we come across 15. We compare it with the current minimum (23) and find that, voila, 15 is smaller than 23, and hence, 15 is smaller than any element we have encountered so far. So, we naturally set our current minimum to 15, and proceed.

We next read 11, and compare it with the current minimum (which is 15). Now, 11 < 15, and so, we set the current minimum to 11.

We proceed to read the next element, which is 46, and compare it with our current minimum (11). Since, 46 > 11, we let 11 remain as the minimum element encountered thus far.

We now realize that we have run out of elements in the array. Hence, the minimum element encountered thus far, 11, is also the minimum element of the array.

—–

Let us look at pseudo-code for computing the minimum in an array of n elements. This should be simple enough to understand.

Input: Array A having n elements: A[1], A[2], …., A[n].

Output: The index of the minimum element in A.

Pseudo-code:

min_index 1. (Comment: min_index (the index of the least element encountered so far) is a variable, initialized to 1.)

For index i going from 2 till n:

{

If  ( A[i} < A[min_index])

then, min_index i.

}

Return min_index.

—–

For those familiar with the big-O notation, it should be clear that this procedure for finding the minimum in an n-element array takes O(n) steps.

—–

Let’s say that our function for finding the minimum index, Find_Min_Index takes 3 arguments – an array, a starting index, and an ending index.

eg. The function call Find_Min_Index(Z, 4, 9) will find find the index of minimum element from among Z[4], Z[5],…, Z[9].

Now, back to sorting by successive selection of minimum elements.

From what we’ve seen so far, we can write a procedure for sorting an n-element array.

Input: Array A of n elements: A[1], A[2], …, A[n].

Output: A re-ordering of the elements of A such that the elements are sorted in increasing (or, to be more precise, non-decreasing) order.

—–

For i going from 1 to n

{

index Find_Min_Index (A, i, n)

Swap A[i] and A[index].

}

—-

That wasn’t very difficult. Again, for those familiar with asymptotic notation, the selection sort algorithm takes time. (It is easy to see why  —- The first element of the sorted array is obtained by finding the minimum element from among n elements. This takes kn time (where, k is some constant). Similarly, the 2nd element of the sorted array is obtained by finding the minimum element from among n-1 elements. This takes k(n-1) time. Proceeding in the same manner, we find that the time needed to sort the array is .)