Interview Question for Software QA Engineer Intern at Salesforce.com:

Apr 13, 2012

void QuickSort(int[] arr, int low, int high)
 {
     while (low < high)
     {
         int pivot = (low+high)/2;
         int partition = Partition(arr, low, high, pivot);
         QuickSort(arr, low, partition);
         QuickSort(arr, partition+1, high);
     }
 }

 void Partition(int[] arr, int low, int high, int pivot)
 {
     // take pivot element to end
     swap(arr[pivot], arr[high]);

     int pivotElement = arr[high];
     int finalPosition = 0;

     for (int i = low; i < high - 1; ++i)
     {
         if (arr[i] < pivotElement)
         {
             swap(arr[i],arr[finalPosition]);
             finalPosition++;
         }
     }

     // put pivot element in its "final position"
     swap(arr[finalPosition],arr[high-1]);
 }