Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A16 notes

CSE1303 Computer Science
Semester 2 2003
Part A
Lecture A16 notes: Advanced Sorting

In this lecture

• Kruse 7.6 - 7.8
• Standish 13.4
• Langsam 6.2, 6.4
• Sedgewick 9, 12

• Takes O(n log(n)) time.
• For arrays it needs more space than the other sorts.
• Useful for linked lists.

• Care must be taken in choosing a pivot.
• Most of the work is done in partitioning the array into two parts.
• Takes O(n log(n)) time in the best and average cases, and O(n²) in the worst case.
• In the worst case quicksort generally performs worse than insertion sort.
• For random contiguous arrays it performs better than any other sort.

Code for this lecture

/* Merges two sorted arrays of floats into array tmp. */
void mergeArrays(float a[], int aSize, float b[], int bSize, float tmp[])
{
  int k;
  int i = 0;
  int j = 0;

  for (k = 0; k < aSize + bSize; k++)
  {
    if (i == aSize)
    {
       tmp[k] = b[j];
       j++;
    }
    else if (j == bSize)
    {
       tmp[k] = a[i];
       i++;
    }
    else if (a[i] <= b[j])
    {
       tmp[k] = a[i];
       i++;
    }
    else
    {
       tmp[k] = b[j];
       j++;
    }
  }
}

/* Recursively merge sort an array of floats */
void mergeSortRec(float array[], int size, float tmp[])
{
  int  i;
  int  mid = size/2;

  if (size > 1)
  {
    mergeSortRec(array, mid, tmp);
    mergeSortRec(array+mid, size-mid, tmp);
    mergeArrays(array, mid, array+mid, size-mid, tmp);

    for (i = 0; i < size; i++)
    {
       array[i] = tmp[i];  /* copy arrays */
    }
  }
}

/* Sort an array of floats into increasing order. */
void mergeSort(float array[], int size)
{
  int* tmpArrayPtr = (int*)malloc(size*sizeof(int));

  if (tmpArrayPtr != NULL)
  {
    mergerSortRec(array, size, tmpArrayPtr);
  }
  else
  {
    fprintf(stderr, "Not enough memory to sort array.\n");
    exit(1);
  }
  free(tmpArrayPtr);
}

/*  Swap two floats */
void swap(float* a, float* b)
{
 int tmp = *a;
 *a = *b;
 *b = tmp;
}

/*  Partition an array of floats, and return the index  of the pivot.  */
int partition(float array[], int size)
{
 int k;
 int mid = size/2;
 int index = 0;

 /* Move pivot to the front of the array */
 swap(array, array+mid);

 for (k = 1; k < size; k++)
 {
   /* Is array[k] is less than the pivot? */
   if (array[k] < array[0])
   {
      index++;
      swap(array+k, array+index);
   }
 }
 /* Move the pivot into its correct position */
 swap(array, array+index);
 return index;
}

/*  Sort an array of floats into increasing order.  */
void quickSort(float array[], int size)
{
 int index;

 if (size > 1)
 {
    index = partition(array, size);
    quickSort(array, index);
    quickSort(array+index+1, size-index-1);
 }
}

[ Top | Home ]
Last Updated: Thursday 26 June 2003 11:06:04