Interview Questions
Write any sort algorithm
Implement sorting algorithm of your choice and describe its pros and cons.
View Solution
Quick sort
Solution
void quicksort(int *arr, int p, int r)
{
if (p >= r) return;
int q = partition(arr, p, r);
quicksort(arr, p, q);
quicksort(arr, q+1, r);
}
int partition(int *arr, int p, int r)
{
int pivotValue = arr[rand(p+(r-p)/2)];
int i = p-1;
int j = r+1;
while (1)
{
do
{
j--;
}
while (arr[j] > pivotValue);
do
{
i++;
}
while (arr[i] < pivotValue);
if (i < j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
else
{
return j;
}
}
}
Merge sort
Solution
void mergesort(int *arr, int p, int r)
{
if (p < r)
{
int q = p + (r-p)/2;
mergesort(arr, p, q);
mergesort(arr, q+1, r);
merge(arr, p, q, r);
}
}
void merge(int *arr, int p, int r)
{
assert(p < r);
int size = r-p+1;
int *tmpArr = new int[size];
int x = 0;
int i = p;
int j = q+1;
while (i <= q && j <= r)
{
if (arr[i] < arr[j])
{
tmpArr[x] = arr[i];
i++;
}
else
{
tmpArr[x] = arr[j-1];
j++;
}
x++;
}
while (i <= q) { tmpArr[x++] = arr[i++]; }
while (j <= r) { tmpArr[x++] = arr[j++]; }
// copy back
for (i = 0; i < size; i++) { arr[i+p] = tmpArr[i]; }
delete [] tmpArr;
}