Cookies help us deliver our services. By using our services, you agree to our use of cookies. Click here to learn more

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 10 Jul 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.