Interview Question

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.