QuickSort.c

Go to the documentation of this file.

 
#include "BaseLibInternals.h"
 
VOID
EFIAPI
QuickSort (
  IN OUT VOID                 *BufferToSort,
  IN CONST UINTN              Count,
  IN CONST UINTN              ElementSize,
  IN       BASE_SORT_COMPARE  CompareFunction,
  OUT VOID                    *BufferOneElement
  )
{
  VOID   *Pivot;
  UINTN  LoopCount;
  UINTN  NextSwapLocation;
 
  ASSERT (BufferToSort     != NULL);
  ASSERT (CompareFunction  != NULL);
  ASSERT (BufferOneElement != NULL);
  ASSERT (ElementSize      >= 1);
 
  if (Count < 2) {
    return;
  }
 
  NextSwapLocation = 0;
 
  //
  // pick a pivot (we choose last element)
  //
  Pivot = ((UINT8 *)BufferToSort + ((Count - 1) * ElementSize));
 
  //
  // Now get the pivot such that all on "left" are below it
  // and everything "right" are above it
  //
  for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {
    //
    // if the element is less than or equal to the pivot
    //
    if (CompareFunction ((VOID *)((UINT8 *)BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0) {
      //
      // swap
      //
      CopyMem (BufferOneElement, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
      CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), (UINT8 *)BufferToSort + ((LoopCount) * ElementSize), ElementSize);
      CopyMem ((UINT8 *)BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, ElementSize);
 
      //
      // increment NextSwapLocation
      //
      NextSwapLocation++;
    }
  }
 
  //
  // swap pivot to it's final position (NextSwapLocation)
  //
  CopyMem (BufferOneElement, Pivot, ElementSize);
  CopyMem (Pivot, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
  CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), BufferOneElement, ElementSize);
 
  //
  // Now recurse on 2 partial lists.  neither of these will have the 'pivot' element
  // IE list is sorted left half, pivot element, sorted right half...
  //
  if (NextSwapLocation >= 2) {
    QuickSort (
      BufferToSort,
      NextSwapLocation,
      ElementSize,
      CompareFunction,
      BufferOneElement
      );
  }
 
  if ((Count - NextSwapLocation - 1) >= 2) {
    QuickSort (
      (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
      Count - NextSwapLocation - 1,
      ElementSize,
      CompareFunction,
      BufferOneElement
      );
  }
}