Subversion Repositories programming

Rev

Rev 86 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 86 Rev 87
Line 35... Line 35...
35 
 
 35 
 
36 
/* swap -- O(1) */
 36 
/* swap -- O(1) */
37 
void swap (int *left, int *right);
 37 
void swap (int *left, int *right);
38 
 
 38 
 
39 
/* partition -- O(n) way to move an array around a pivot
 39 
/* partition -- O(n) way to move an array around a pivot
40 
 *           -- comes from quicksort() (but is not used here)
 40 
 *           -- comes from quicksort() (but is not used here) */
41 
 */
 - 
 
42 
int partition (int array[], unsigned long left, unsigned long right);
 41 
int partition (int array[], unsigned long left, unsigned long right);
43 
 
 42 
 
44 
/* ---------- BEGIN QUICKSORT ---------- */
 43 
/* ---------- BEGIN QUICKSORT ---------- */
45 
 
 44 
 
46 
/* compare function for stdlib's qsort() */
 45 
/* compare function for stdlib's qsort() */
Line 69... Line 68...
69 
 
 68 
 
70 
/* Mergesort an array
 69 
/* Mergesort an array
71 
 * Sets up the correct parameters and hands off the work to
 70 
 * Sets up the correct parameters and hands off the work to
72 
 * mergesort_rec()
 71 
 * mergesort_rec()
73 
 *
72 
 *
74 
 * Complexity: O(n*lgn)
 73 
 * Complexity: O(n*lgn) */
75 
 */
 - 
 
76 
void mergesort (int array[], unsigned long size)
 74 
void mergesort (int array[], unsigned long size)
77 
{
 75 
{
78 
    mergesort_rec (array, 0, size-1);
 76 
    mergesort_rec (array, 0, size-1);
79 
}
 77 
}
80 
 
 78 
 
Line 93... Line 91...
93 
    merge (A+min, lowerCount, A+mid+1, upperCount);
 91 
    merge (A+min, lowerCount, A+mid+1, upperCount);
94 
}
 92 
}
95 
 
 93 
 
96 
/* merge two arrays together
 94 
/* merge two arrays together
97 
 *
 95 
 *
98 
 * Complexity: O(n)
 96 
 * Complexity: O(n) */
99 
 */
 - 
 
100 
void merge(int A[], unsigned long asize, int B[], unsigned long bsize)
 97 
void merge(int A[], unsigned long asize, int B[], unsigned long bsize)
101 
{
 98 
{
102 
    unsigned long ai, bi, ci, i;
 99 
    unsigned long ai, bi, ci, i;
103 
    int *C;
 100 
    int *C;
104 
    unsigned long csize = asize+bsize;
 101 
    unsigned long csize = asize+bsize;
Line 203... Line 200...
203 
 * which is found in array[left].
 200 
 * which is found in array[left].
204 
 *
 201 
 *
205 
 * All values less than the pivot are on the left
 202 
 * All values less than the pivot are on the left
206 
 * All values more than the pivot are on the right
 203 
 * All values more than the pivot are on the right
207 
 *
 204 
 *
208 
 * Complexity: O(n)
 205 
 * Complexity: O(n) */
209 
 */
 - 
 
210 
int partition (int array[], unsigned long left, unsigned long right)
 206 
int partition (int array[], unsigned long left, unsigned long right)
211 
{
 207 
{
212 
    unsigned long i, last, pivot;
 208 
    unsigned long i, last, pivot;
213 
 
 209 
 
214 
    pivot = array[left];
 210 
    pivot = array[left];