## IBM Interview Question

Software Engineer in Tests**Country:**India

**Interview Type:**Written Test

yea

```
void sortN( int * x, int N ) {
int i = 0;
int j = N-1;
int pivot = 0;
while( i <= j )
{
while ( x[i] < pivot && i < N ) i++;
while ( x[j] >= pivot && j >= 0) j--;
if ( i < j ) swap( x[i], x[j] );
}
}
void swap( int & x, int &y ){
int temp = x;
x = y;
y = temp;
}
```

The dynamically created array is language dependent and seems targeted towards knowledge of C/C++.

Apart from that the algorithm seems fairly simple.

Set current_index as 0.

Now run through the array looking for negative numbers.

If a negative number is found, swap it with number at location current_index and increment current_index by 1

A sample run through (taking integers only for simplicity)

input 1 -4 -2 3 4 6 -3 -4 6

-4 1 -2 3 4 6 -3 -4 6 (swapped 1 and -4)

-4 -2 1 3 4 6 -3 -4 6 (swapped 1 and -2)

-4 -2 -3 3 4 6 1 -4 6 (swapped 1 and -3)

-4 -2 -3 -4 4 6 1 3 6 (swapped 3 and -4)

Should work with 0 too.

Also need separate code for menu creation and random array creation.

```
int i = 0;
int j = 0;
for (j = 0; j < N; j++)
{
if (arr[j] < 0)
{
swap(i, j);
i++;
}
}
```

this makes the output semi-correct :-5 -8 -20 -100 -51 10 30 0 100 21

There will be max two more passes to put the 0 in the right position if it exists

I am not sure...but this can be done in one pass: see below example

-1, 4, 6, 7, -9, 5, - 3, -4, -7, 8, -6

one variable will store the index of first positive number in the list

if index is a variable:

-1, 4, 6, 7, -9, 5, - 3, -4, -7, 8, -6

while traversing index = 4

as soon as we encounter a negative number we swap it with index and make index ++

we can do index ++ because there is two possibilities of a number next to index number either number is -ve: then in the pass we must have swapped it with +ve number in that case also index++

or number is +ve: then we find the -ve number and swap it with that number and still index ++

-1, 4, 6, 7, -9, 5, - 3, -4, -7, 8, -6

index =1

in for loop now we encounter -9 then swap it with 4 and index++

-1 -9 6 7 4 5 -3 -4 -7 8 -6

index = 2 now we encounter -3 the swap it with 6 and index++

-1 -9 -3 7 4 5 6 -4 -7 8 6

index = 3 now we encounter -4 then swap it with 7 and index++

-1 -9 -3 -4 4 5 6 7 -7 8 6

index=4 now we encounter -7 then swap it with 4

-1 -9 -3 -4 -7 5 6 7 4 8 6

now till the end we did not encounter any -ve number so this is it

I hope we need not the list to be sorted!!

please correct me if i am doing wrong somewhere

```
var arr = [-1, 4, 6, 7, -9, 5, -3, -4, -7, 8, -6];
console.log(arr);
for(var i = 0,j = arr.length;i < j;i++){
if(arr[i] >= 0){
var last = arr[j];
if(last < 0){
arr[j] = arr[i];
arr[i] = last;
console.log(arr);
}else{
i--;
}
j--;
}
}
console.log(arr);
```

[-1, 4, 6, 7, -9, 5, -3, -4, -7, 8, -6]

[-1, -6, 6, 7, -9, 5, -3, -4, -7, 8, 4]

[-1, -6, -7, 7, -9, 5, -3, -4, 6, 8, 4]

[-1, -6, -7, -4, -9, 5, -3, 7, 6, 8, 4]

[-1, -6, -7, -4, -9, -3, 5, 7, 6, 8, 4]

```
we can try like this.Please comment me if I am wrong,
first check number of -ve numbers(1 pass).say x.take two indices one from 0 another from x.check a[0] and a[x].
case 0: + and - ---> swap them and move both indices one step ahead
case 1: - and - --->move the first index till a + is found and swap them and then move both one step ahead
case 2: + and - viceversa of case 2
```

Isn't it a one loop of quick sort separated by zero?

- chenlc626 February 25, 2013