Changes between Version 2 and Version 3 of Proposal1.2


Ignore:
Timestamp:
Jun 15, 2010, 3:49:57 PM (7 years ago)
Author:
sacerdot
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Proposal1.2

    v2 v3  
    2424
    2525'''Figure 2:''' Quicksort
     26[[Image(img3.png)]]
    2627
    27 ||  ||
    2828
    2929As a simple example, consider the quicksort program of Fig.�[[#code|2]]. This algorithm performs in-place sorting of input array img3.png whose bounds are img4.png and img5.png; initially img4.png is expected to be zero, while img5.png is the length of the array minus one. The outermost conditional terminates when the bounds of the array are illegal. (Sorting an empty array will end the recursive behaviour of the algorithm.) The variable img6.png is the so called pivot: a selected element of the array that will be compared with all other elements. Bigger elements will be moved (by the swap function) to the end of the array (the upper part), while smaller elements are placed at the beginning of the array (the lower part). Then the pivot is placed between the lower and the upper part of the array, in position img7.png, its position in the resulting sorted array; all elements before the pivot are smaller and all elements following it are bigger. The algorithm completes the sorting with recursive calls on the lower and on the upper parts of the array.