Symantec Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
the even position number should start at len(array)//2.
for the first half. for the int at position i, array[0:i] has been sorted. if i is odd, insertion sort array[i] into array[0:i]. if i is even, swap it with an odd position number in the second half and then do the insertion sort.
then insertion sort the second half.
def sort_even_odd(array):
l = len(array)
even_start = l // 2
even_ptr = even_start
if even_ptr % 2 == 0:
even_ptr += 1
for i in range(even_start):
if i % 2 == 0:
assert even_ptr < l, "even_start={0}, even_pr={1}, i = {2}".format(even_start, even_ptr, i)
array[i], array[even_ptr] = array[even_ptr], array[i]
even_ptr += 2
for j in range(i - 1, -1, -1):
if array[j + 1] < array[j]:
array[j + 1], array[j] = array[j], array[j + 1]
else:
break
for i in range(even_start, l):
for j in range(i - 1, even_start - 1, -1):
if array[j + 1] < array[j]:
array[j + 1], array[j] = array[j], array[j + 1]
else:
break
return array
Insertion sort would be very inefficient if the array was very large. Quicksort is better overall; if written iteratively, even better.
// move all odd elements into 1st half, even elements into 2nd half
public static int[] sort(final int[] array) {
int iter = 1;
for (iter = 1; iter < (array.length / 2); iter++) {
if ((iter % 2) > 0) {
swap(array, iter, (array.length / 2) - 1 + iter);
}
}
// Quicksort(in-place), avg nlogn performance provided by Java
Arrays.sort(array, 0, (array.length / 2));
Arrays.sort(array, array.length / 2, array.length);
return array;
}
Total running time: O(n + nlogn)
The fastest we can sort an array of size n is O(nlogn). So in this case also we can sort in O(nlogn) complexity. We can first bring all the odd position array in the first half array and all the even position in the second half of the array. Now the first half a[0..n/2] and second half [n/2+1,n-1] can be independently sorted by two calls to quicksort like given below:
quickSort(a, 0, n/2);
quickSort(a,(n/2)+1, n-1);
void quickSort(int a[], int start, int end)
{
if (start < end)
{
int pivot = start;
int j = partition(a, start, end, pivot);
int temp = a[pivot];
a[pivot] = a[j];
a[j] = temp;
quickSort(a, start, j-1);
quickSort(a, j+1, end);
}
}
int partition(int a[], int start, int end, int pivot)
{
static int numTimes = 0;
while(start < end)
{
while(a[start]<=a[pivot] && start < end)
++start;
while(a[end]>a[pivot])
--end;
if (start < end)
{
int temp = a[start];
a[start]=a[end];
a[end] = temp;
}
}
return end;
}
I would recommend you first put all odd-position ints in the first half, and then run an in-place sort like heapsort on each half separately.
- Anonymous September 05, 2012