Interview Question

Interview Mountain View, CA

Should able to write code of Quick Sort in limited time.

Answer

Interview Answer

1 Answer

0

/* sort a[low]...v[high] into increasing order 80 15 30 60 55 65 40 35 45 70 => 15 30 35 40 45 55 60 65 70 80 */ void Swap(int a[], int low, int high) { int t = *(a+low); *(a+low) = *(a+high); *(a+high) = t; } void QuickSort(int a[], int low, int high) { if (low >= high) return; if (low+1 == high) { if (a[low] > a[high]) Swap(a, low, high); else return; } int mid = (low+high)/2; int pivot = a[mid]; Swap(a, low, mid); // Pointers to scan from the left and right int left = low+1; int right = high; do { while (a[left] <= pivot && left <= right) ++left; while (a[right] > pivot) --right; if (left < right) Swap(a, left, right); } while (left < right); Swap(a, low, right); QuickSort(a, low, right-1); QuickSort(a, right+1, high); }

Peter on Jul 21, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.