Home MembershipSpecial Interest GroupsSIGCT (Computing Teachers)JCSE Online - Journal of Computer Science EducationPast Issues2003-2004 January 2004

Ordering Patterns and List Inversions

David Ginat
Tel-Aviv University
Dan Garcia
University of California, Berkeley

Ordering patterns, which involve sorting schemes and assertions, are fundamental in computer science (CS). This paper broadens the perspective of these patterns, through the rather unfamiliar notion of list inversions. Inversions are usually not introduced in the CS curriculum. However, they yield enriching algorithmic tasks, two of which are presented and solved in this paper. Each task is approached in several ways. The various approaches involve the recognition of underlying assertional patterns and the utilization of sorting design patterns. The recognition and utilization of these patterns illuminate novel considerations of element ordering, and may enrich CS tutors’ scientific and pedagogical repertoires.

1. Introduction

We regard ordering patterns as any design schemes and assertions that involve the notion of ordered elements. These include smaller/larger and before/after relations, algorithmic schemes (design patterns) of sorting computations, and assertions related to the relative ordering of elements. Ordering patterns are fundamental in computer science. In CS1, students learn basic sorting schemes (e.g., bubble-sort). In CS2 and the course of Introduction-to-Algorithms students become familiar with a variety of more involved sorting schemes.

Sorting schemes are examined with respect to various considerations, such as comparisons, exchange operations, and stability characteristics. Most, but not all, sorting algorithms are based on element comparisons, and the lower bound for sorting by comparisons is O(NlogN). Many, but not all, sorting algorithms are based on element exchanges. Some of the sorting algorithms are stable, in the sense that they preserve the initial ordering of duplicates (Cormen, Leiserson, & Rivest, 1990).

The examination of diverse considerations of sorting schemes facilitates their comprehension and assimilation. An additional element that facilitates their understanding is the design of algorithms for related computations, such as order statistics (Cormen, Leiserson, & Rivest, 1990). The objective of this paper is to shed light on non-illuminated considerations related to sorting. Our illumination may facilitate the enhancement and elaboration of core, familiar, and unfamiliar ordering patterns.

The considerations that we illuminate involve the notion of list inversions. An inversion in a list L of elements is a pair <x,y> of distinct elements, such that x<y and x appears after y in L (Knuth, 1973). In examining an unordered list, one may enquire about the number of inversions in L, or about the widest inversion in L (the two unordered elements that are furthest from one another). The former may be a parameter for measuring the amount of "disorder" in L. The latter indicates the largest interval, or "period" of values in which the first value is larger than the last one.

Inversions are not mentioned by CS2 and introduction-to-algorithms textbooks. Knuth (1973) is an exception. He introduces and discusses inversions, primarily with respect to combinatorial properties of permutations. In this paper we examine inversions from a rather different point of view–as a means for illuminating and practicing assertional and operational ordering patterns.

We reveal novel ordering patterns, some of which are invariants, and utilize familiar sorting scheme components in solving unfamiliar tasks. Patterns, including invariants are significant means for analyzing and devising algorithms and computer-programs (Dijkstra, 1976; Gries, 1981). The utilization of familiar schemes in the solution of unfamiliar tasks is an essential element in problem-solving transfer and computer program design (Meyer & Wittrock, 1996; Soloway, 1986; Linn & Clancy,1992, 1999).

The tasks in this paper involve the two inversion computations mentioned above, of the number of inversions in a list and the widest inversion in a list. The first task is mentioned (but not solved) by Knuth (1973), with respect to permutations. The second task is novel. Both tasks require stimulating recognition and utilization of ordering patterns.

In the next two sections we specify and solve the two tasks, one in each section. For each task we display several solution approaches, based on diverse inversion properties and ordering patterns. In the last, concluding section we reflect on the tasks and their solution approaches, and underline their scientific and pedagogical values for algorithmic problem solving in general and the study of sorting in particular.

2 Inversion Counting

Our first task requires counting of the number of inversions in a list (see figure 1). The number of inversions may be one way of measuring the amount of "disorder" in the list. Such a measure may be relevant, for example, for a chain of physical objects in which object reordering may be performed only between adjacent objects. In such a chain, each reordering operation may reduce the number of inversions by exactly 1. Thus, the amount of "disorder" indicates the amount of work that needs to be done for ordering the chain.

This task may be approached in various ways, based on different sorting schemes. We display the various approaches from the less efficient to the more efficient one. As it sometimes occurs in problem solving, one of the approaches yields valuable insight and some progress, but falls short in yielding the final desired outcome.

2.1 Approach-1 — Naïve Counting

The simplest way to approach the task is by counting separately for each list element x the number of elements smaller than x that follow it in the list. The time complexity is O(N²). The basic design pattern here is naïve counting. While this solution yields the desired result, it does not capitalize on core task characteristics. Inversion is tied to ordering, thus it may be beneficial to seek patterns that evolve from sorting schemes.

2.2 Approach-2 — Adjacency Exchanges

Some sorting schemes are based on element exchanges. In some of these schemes the exchanges are between adjacent elements (e.g., bubble-sort), and in others the exchanges are between not-necessarily adjacent elements (e.g., quick-sort). An exchange between two unordered adjacent elements reduces the number of inversions by 1. We may execute a sorting algorithm based on adjacency exchanges and count the number of exchanges. However, the total number of inversions may be of O(N²), therefore no adjacency-exchanges scheme may improve the time complexity of naïve counting.

2.3 Approach-3 — Non-adjacency Exchanges

In order to obtain insight into the characteristics of non-adjacency exchanges, we may try to first examine a single exchange. Let the exchange be between the two elements x and y, and let z be an element in-between them. Before the exchange, the order is ..x..z..y.. and after — it is ..y..z..x... The swap between x and y contributes -1 or +1 to the change in the total number of inversions. The modification of the relative ordering of both x and y with respect to z contributes -2, 0, or +2. The latter holds for any z between x and y. For example, let the list be: 4 5 3 1. An exchange between 4 and 1 yields the following changes in the number of inversions: -1 due to reordering of 4 and 1 (deletion of the inversion <4,1>); 0 due to the new order of 1 and 4 with respect to 5 (creation of <5,4>, but deletion of <5,1>); and -2, due the new order of 1 and 4 with respect to 3 (deletion of <4,3> and <3,1>). The latter observations yield the invariant illustrated in figure 2.

While the invariant indeed illuminates an inversion-modification characteristic, it does not reveal an exact reduction in the number of inversions. In fact, there may be cases where a single non-adjacency exchange will decrease the total number of inversions, and there may be cases where an exchange may increase this number. It is not clear how to effectively compute the exact number of modifications for each exchange without some exhaustive counting.

Quick-sort is an efficient non-adjacency exchanges scheme. However, following the above discussion, it is not clear whether it can be utilized for an improved computation time. heap-sort is another scheme based on non-adjacency-exchanges. However, the utilization of heap-sort for counting inversions seems more complex than that of quick-sort, as heap-sort involves not only non-adjacency exchanges but also an initial stage of building a heap. Perhaps we should try a sorting scheme that is not based on exchanges.

2.4 Approach-4 — Merging Skips

Two non-exchanges sorting schemes that we may consider are radix-sort and merge-sort (Cormen, Leiserson, & Rivest, 1990). In Radix-sort, elements are processed by their "pieces" (digits), a characteristic that seems to complicate the analysis for inversion calculations. merge-sort looks more promising. We may obtain valuable insight by examining a single merge of two sub-lists.

In merge-sort, a list L is sorted by merging its ordered left half and its ordered right half. We call the two halves Left-L and Right-L. When an element from Left-L is chosen to be put in the ordered, merged list, it is the leftmost among all the (Left-L and Right-L) elements that are not yet merged. When an element x from Right-L is chosen, it is to the right of all the current (not-yet-merged) Left-L elements. The selection of x for the merged list reduces the total number of inversions by the size of the remaining Left-L, since x is put in the merged list before all the elements remaining in Left-L. The latter observation yields the assertional pattern show in figure 3.

For example, let the list 3 7 9 4 8 10 be a list to be ordered, by merging its two already-ordered halves 3 7 9 (Left-L) and 4 8 10 (Right-L). First, 3 is chosen to be the leftmost in the merged list; then 4 is chosen to be next in the merged list, and therefore "skipped over" the remaining Left-L, which is composed of the two elements 7 9; then, 7 is chosen; then 8 is chosen and "skipped over" the remaining Left-L, which is the single element 9; and finally the 9 and the 10 are chosen. The total length of the "skip intervals" is 2+1=3, which is exactly the number of inversions in the initial list (<7,4>, <9,4>, <9,8>).

The computation of the number of inversions in the original list can be combined in merge-sort — in each merging phase, the counter of the total number of inversions will be incremented by every "skip" of a Right-L element "over" Left-L elements. The incrementing value will be the length of the "skip interval" (the size of Left-L). Since the time complexity of merge-sort is O(NlogN), the computation of the number of inversions will be done in time O(NlogN).

3 Inversion Finding

Our second task requires finding the "width" of the widest inversion (see figure 4). Thus, it involves a maximum computation. Such a computation may be necessary, for example in examining the "behavior" of a stock in the stock market, where each input value represents a stock value on a different day, and one is interested in finding the longest interval of days in which the initial stock value was larger than the final one.

Like the previous task, this task may be approached in various ways, which vary efficiency-wise. However, here one has to be more careful, as some ideas may seem promising at a first glance but yield incorrect outcomes. We display the various solution approaches from the less efficient, through an erroneous one, to the more efficient.

3.1 Approach-1–Repeated Linear Search

The simplest way to approach this task is similar to the naïve counting in the previous task. For each input element x, the input list will be scanned, as in linear search, and the distance between x and the furthest element smaller than x will be computed. The time complexity is O(N²). Although correct, this solution is inefficient. It may be possible to do better by turning to some sorting scheme, or sub-scheme, as the task involves the notion of ordering.

3.2 Approach-2–Rolling Distance

Two basic sorting algorithms, insertion-sort and bubble-sort, are based on "rolling" each element to its final destination, by sequences of adjacency exchanges. It may be beneficial to capitalize on rolling. We may record rolling distances during sorting execution, attach these distances to the sorted elements, and calculate inversion widths. (One has to be careful though with combining rolling distances of different elements.) While this idea seems relevant, it may not yield an improvement of the time complexity O(N²), as the "rolling"-based sorting algorithms are of time complexity O(N²).

3.3 Approach-3–Left-Right Progress

It may seem appealing to adopt the quick-sort sub-scheme of concurrently "advancing" two pointers from both ends of the list towards one another. An initial thought may be to move both pointers concurrently "inwards", one position at a time, until they point at an unordered pair. This idea indeed "works" with the example in the problem definition; i.e., for the input: 2 5 1 9 4 7, the two pointers will initially point at 2 and 7. As these two elements are properly ordered, the pointers will be advanced to point at 5 and 4, and the widest inversion, <5,4> of width 3, will be discovered.

Unfortunately, the above idea does not always "work". For example, for: 2 8 1 9 4 7, it will recognize the widest inversion as <8,4>, when the widest inversion is <8,7>. One may try (some students indeed try) to "fix" the above scheme and redirect the pointers "outwards", and advance them in stages, one after the other, in order to solve cases like the above. At first glance such "patching" may seem promising, but, further examples show that the widest inversion may involve an element that is not at all reached by one of the pointers. For example, for the input: 7 2 4 17 8 9 6 13 10 18 19, the advancement of the pointers will be halted at the integers 17 (the left pointer) and 13 (the right pointer), but the widest pair is <7,6>, and the 6 is an element not yet reached by any of the pointers. It is not clear whether "patching" variants of the Quick-Sort sub-scheme may yield the desired result.

3.4 Approach-4–Candidate Lists

The previous approach was focused on immediately seeking at least one of the ends of the widest inversion. However, as we all know in computer science, sometimes, a preliminary computation, which does not directly yield the final result may be very effective. One example is the construction of a heap in the first stage of Heap-Sort; another example is the preliminary construction of look-up tables, or look-up chains, in various computations (Cormen, Leiserson, and Rivest, 1990).

What kind of preliminary computation may be effective here? One may initially think of computing for each element x its rightmost "inversion match" and its leftmost "inversion match". A separate computation for each x is too costly (O(N²) time) and we do not know of a combined, efficient way. However, we may follow a different direction. Rather than computing rightmost and leftmost matches, we may first compute for each element whether it can at all be a right end or a left end of the widest inversion. This idea yields the pattern of figure 5.

The correctness of the candidate pattern for every x is rather obvious. If there is an element y smaller than x to the right of x, then y is always a better choice than x for the right end of the widest inversion. Similarly, if there is an element z larger than x to the left of x, then z is always a better choice than x for the left end of the widest inversion.

The Candidate Pattern implies that we may perform a preliminary computation of all the candidates, and then capitalize on this computation for finding the widest inversion. Can we efficiently perform the preliminary stage; and can we efficiently capitalize on it later? In what follows, we address the challenge.

For the preliminary stage we utilize two boolean arrays — R-ends and L-ends, both of size N (the length of L). The array R-ends can be rather simply built by scanning L once from right to left, setting an entry to ‘1’ according to the following rule: R-ends[i]=1 if and only if L[i] is smaller than all the elements on its right in L (i.e., L[i]<L[k], for every k larger than i). Analogously, L-ends will be built by scanning L once from left to right, setting an entry to ‘1’ according to the following rule: L-ends[i]=1 if and only if L[i] is larger than all the elements on its left in L (i.e., L[i]>L[k], for every k smaller than i). See figure 6 for an example.

In examining the order of the L elements that correspond to the 1’s in each of the boolean arrays, we notice the following interesting seen if figure 7.

The Increasing-Order Invariant directly derives from the definition of a ‘1’ entry in each of the boolean arrays. In the R-ends array, there will not be a ‘1’ in entry i if there is some k, such that k>i and L[i]³ L[k]. Similarly, in the L-ends array, there will not be a ‘1’ in entry i if there is some k, such that k<i and L[i]£ L[k].

We may effectively capitalize on the increasing-order invariant, by advancing with two pointers concurrently through both of the boolean arrays, from left to right. The principle underlying this progress is that for each left end candidate c in L (for which L-ends[c]=1), the right end with which it yields the widest inversion is the rightmost element in L that is smaller than c and its corresponding R-ends value is ‘1’. (It may occur that c will have no right end match. In such a special case, c will be viewed as "matching" itself, and will not form an actual inversion.)

The above advancement is somewhat similar to the merge-sort sub-scheme of concurrently "running" through two sub-lists from left to right. In merge-sort the sub-list are merged. Here, the two arrays, L-end and R-end are scanned, for finding the widest inversion. Initially, the L-end pointer, which we call lp, will point at the first element in L-end (this first element will always be marked with a ‘1’). The R-end pointer, rp, will be advanced to point at the rightmost ‘1’ entry in R-end whose corresponding L element is smaller than L[lp] (If no such element, then rp will be set to the value of lp.)

The two pointers mark the first, "leftmost" candidate for the widest inversion. Then, lp will be advanced to point at the next ‘1’ in L-ends, and rp will again be advanced to point at the rightmost ‘1’ in R-end whose corresponding L element is smaller than L[lp] (and if no such element, then rp will be set to the value of lp). These "pointer stops" will yield the next candidate for the widest inversion. Then, the "pointer advancement" will continue, and yield the next candidate, etc. This process will terminate upon reaching the right end of R-ends.

In the example above, the first "stops" of lp and rp will be in locations 1 and 7, respectively, and an inversion of width 6 will be discovered; then, lp and rp will be advanced to the locations 4 and 9, respectively (and an inversion of width 5 will be discovered); then, they will be advanced to locations 10 and 10; and finally to locations 11 and 11 (respectively). The outcome of this computation will be the output 6.

The correctness of the above scheme stems from the characteristic that it finds the widest inversion for each of the left end candidates and selects the maximal one.

All in all, the above scheme involves two stages, each of time complexity and space complexity O(N) — a considerable improvement of the previous O(N²) schemes. The first stage involves two scans of L — one from right to left, and one from left to right — in building the two boolean arrays of candidates R-ends and L-ends. The second stage involves a combined scan of both of the boolean arrays, from left to right, similar to that of Merge-Sort.

4 Conclusion

The two inversion tasks presented in this paper broaden the perspective of ordering patterns and searching schemes. The notion of inversion is unfamiliar to many CS tutors and students, and the two tasks reveal new ordering questions and considerations. Each task was approached in several ways, which involved the recognition of novel assertions and the utilization of sorting schemes. The utilized schemes yielded solutions of diverse correctness and efficiency characteristics. In reflection on the various approaches and the solutions they yielded, we underline several scientific and pedagogical observations:

The notion of inversions is strongly tied to element exchanges. In particular, an "adjacency exchange" modifies the number of inversions by 1, and any exchange modifies the number of inversions by an odd number. This observation enriches the notion of exchange properties.

Various sorting schemes were relevant as underlying principles for the task solutions. The less efficient, O(N²) schemes, such as Bubble-Sort, could be elegantly utilized, but their costly time complexity did not yield an efficient solution.

Quick-sort was a relevant sorting scheme to consider in both tasks. It yielded valuable insight, particularly in the inversion counting task, but did not yield a final desired outcome. Such a phenomenon, of limited progress, often occurs in the process of problem solving.

Merge-sort was more effective. In both tasks, underlying principles of the efficient solution involved merge-sort sub-schemes. In the inversion counting task, the notion of merging two ordered sub-lists was the core design principle of the 4th approach; and in the Widest Inversion task, the notion of concurrently progressing with two pointers, from left to right, through ordered arrays was also the underlying principle of the 4th approach. Primary schemes, such as merge-sort, may lay the foundations for solutions of other, diverse tasks.

Assertional patterns and invariants were essential means in the solutions of both tasks. In the inversion counting task, the exchange invariant and the merge pattern played a primary, illuminating role. In the widest inversion task, the candidate pattern yielded the insightful 1st stage of the 4th approach, and the increasing-order invariant yielded the efficient 2nd stage. Assertional patterns are fundamental in algorithm design and analysis.

Various design patterns were utilized in attempts and solutions of both tasks. Specifically, the design patterns of merging lists, concurrently "running" pointers through lists, and utilizing a "candidate computation" (see also, the celebrity problem, and the majority problem; Manber, 1989) were all valuable means in the design of solutions of the two tasks. The utilization of common design patterns repeatedly occurs in algorithm design.

All in all, the two list-inversion tasks and their various solutions revealed new considerations of ordering patterns, through the discovery of novel assertional patterns and the original utilization of familiar sorting design patterns. The discovery of novel assertional patterns of algorithms broadens and deepens the values and perspectives of CS problem-solvers. The utilization of familiar design patterns in solving novel tasks promotes the effective, diverse re-use of fundamental solution schemes (Astrachan et al., 1998). The pattern discovery and utilization displayed in this paper may serve as a valuable means for teaching and learning algorithms in general and sorting schemes in particular.

5 References

Astrachan, O. L., Berry, G. C., Cox, L. P., & Mitchener, G. (1998). Design patterns: An essential component of CS curricula. In J. Lewis, J. Prey, & D. Joyce (Eds.), SIGCSE '98: The proceedings of the Twenty-ninth SIGCSE Technical Symposium on Computer Science Education (pp. 153—160). New York: Association for Computing Machinery.

Cormen, T. H., Leiserson, C. E., & Rivest, R. L. (1990). Introduction to Algorithms. Cambridge, MA: MIT Press.

Dijkstra, E. W. (1976). A Discipline of Programming. Englewood Cliffs, NJ: Prentice-Hall.

Gries, D. (1981). The Science of Programming. New York: Springer-Verlag.

Knuth, D. E. (1973). The Art of Computer Programming, Vol. 3. Addison-Wesley.

Linn, M. C. & Clancy, M. J. (1992). The case for case studies of programming problems. Communications of the ACM, 35 (3), 121—132.

Linn, M. C. & Clancy, M. J. (1999). Patterns and pedagogy. In R. E. Noonan, J. Prey, & D. Joyce (Eds.), SIGCSE '99: The Proceedings of the Thirtieth SIGCSE Technical Symposium on Computer Science Education (pp. 37—42). New York: Association for Computing Machinery.

Manber, U. (1989). Introduction to Algorithms — A Creative Approach. Reading, MA: Addison-Wesley.

Meyer, R. E. & Wittrock, M. C. (1996). Problem-solving transfer. In D. C. Berliner & R. C. Calfee (Eds.) Handbook of Educational Psychology (pp. 47—62). New York: Macmillan.

Soloway, E. (1986). Learning to program = learning to construct mechanisms and explanations. Communications of the ACM, 29 (9), 850—857.