Salesforce.com

  www.salesforce.com
  www.salesforce.com

Interview Question

Software QA Engineer Intern Interview San Francisco, CA

Was asked to program quick-sort in Java.

Tags:
java, sorting algorithm
Answer

Interview Answer

1 Answer

0

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]);
 }

Jigargosha on 2012-07-10

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up