This was given to me in a recent programming interview. I am given an unsorted array of integers with negative and positive values, and required to sort them but only for the positive values. I was wondering what some of your solutions might be without using Google.

After getting home I found **Arrays.sort()** sorts the array in ascending order but I am not sure how to output to new array with only the positive values, as this was a requirement. I am able to print them by just printing if they are greater than -1, but how would I input them into new array without having to loop through the array and count the number of positive values to get the size of the new array, instantiate new array, then loop again to add them to new array.. This solution seems not optimal, is there a better way ?

*the output needs to be a new array with only positive values, that is sorted*

**Below is what I have so far:**

```
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] unsorted = {
-3, 95, -4, 20, 5, 6, 8
};
int[] sorted = unsorted;
Arrays.sort(sorted);
for (int s: sorted) {
if (s > -1)
System.out.println(s);
}
}
}
```

In Java, the Collection.sort must be stable, so if you have use a comparator that says that all negative numbers are equal, but for positive numbers does what you'd expect, you'd have what you need.

You could try putting the data in a `PriorityQueue`

, making sure to only deal with the positive values:

```
int[] unsorted = { -3, 95, -4, 20, 5, 6, 8 };
PriorityQueue<Integer> q = new PriorityQueue<>(unsorted.length);
for (int a : unsorted) {
if (a > 0)
q.add(a);
}
while (!q.isEmpty()) {
System.out.println(q.poll());
}
```

5 6 8 20 95

This approach will be *O(nlog(n))* where *n* is the number of positive integers in the array. Sorting the entire array, by contrast, will be *O(nlog(n))* where *n* is the length of the entire array.

- Iterate the array
- For each positive value, store the position and value into two arrays
- Sort the value array

What if you performed a binary search for `0`

on your sorted array, and then only printed values from that point on? `Arrays.binarySearch()`

returns the index that `0`

WOULD be at if it doesn't find `0`

in your array.

```
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] unsorted = {
-3, 95, -4, 20, 5, 6, 8
};
int[] sorted = unsorted;
Arrays.sort(sorted);
int breakingPoint = Arrays.binarySearch(sorted, 0);
for (int i = breakingPoint; i < sorted.length; i++) {
System.out.println(sorted[i]);
}
}
}
```

You should make your own sorting algorithm. I would use a modified quicksort in an interview:

1-pick 0 to be the pivot for the first recursive call and put all numbers that are equal or bigger than 0 on the right array

2-Only call quicksort on the right array for the first recursive call,for the other recursive calls,use a random pivot.

3- When concatenating,remove the first 0 you find.

Fast(nlogN),and you can do it even in the same array,or return a new one.

Creating a list just for the dynamic aspect would mean potentially resizing the array multiple times during the removal process.

I elected instead to use `Arrays.copyOf`

to resize the array after I knew how big it needed to be.

The first thing I did was filter out the negatives:

```
int[] unsorted = {
-3, 95, -4, 20, 5, 6, 8
};
int[] positives = new int[unsorted.length]; //It can only be as big as unsorted.
int i = 0, j = 0;
for (; i < unsorted.length; i++) {
if (unsorted[i] >= 0)
positives[j++] = unsorted[i];
}
```

Then, I resize the array:

```
positives = Arrays.copyOf(positives, j);
```

Finally, I sort it:

```
Arrays.sort(positives);
```

Here is an IDEOne.com demo

simple separate the positive numbers - it needs one copy

```
List<Integer> positives = new ArrayList<Integer>();
for (Integer number: unsorted) {
if (number > 0) {
positives.add(number);
}
}
```

and then sort them.

```
Collections.sort(positives);
```

Similar Questions

I have an unsorted array (of generated die rolls), and I want to select the top N elements of it (which is trivial with sort-and-snip), but mark them while keeping them in order. E.g.: mark([1,2,3,4],

I have run into some trouble trying to concatenate an array of integers into one number. I understand how to do this with single digit numbers (my code below), but what if I was prompting a user to en

Can anyone please tell me how to sort integers/numbers in JQ grid. the regular sorting gives a distorted order. Hi i got it all done when i use loadonce=true and sorttype = 'int'. But i cant use loado

Given the following array: var things = ['sandwich', 17, 'fake@sample.com', 3, 'horse', 'octothorpe', 'anotheremail@sample.com', '!invalid_garbage@sample.com']; Sort the array into three others, one

I'm sorting tuples of 16+16 bits as 32bit integers with SSE2. There are only signed integer instructions for compare and min/max. I don't have a problem with the order for the higher part as its just

I got the next question in a quiz: Let A be an array of n positive integers, It's known that the highest number in the array is k=n^5. Find the best possible sorting of the algorithm. My answer was:

This question already has an answer here: Subscript indices must either be real positive integers or logicals, generic solution 1 answer I have this strange error 'Subscript indices must either

What would be the smallest and largest number of comparisons in an unsorted array that could have duplicate elements as well ? I understand that finding anything in an unsorted array is a O(n) problem

so, my whole point is to print out the sum of positive numbers, and i have it adding and printing just fine, the only issue it is also adding the negative numbers. any ideas on why this could be? i ju

I am reading Mongodb's docs about Aggregation Framework and Mapreduce, but still have no clue where to begin with aggregating columns of integers in array. F.i. having these documents: [{ _id : A

Hos do I pass array of Integers as a params to XSLT?

Right now I have my array sorting (which is better than getting an error) except it is sorting in the reverse than what I want it to sort in. public static void sortDatabase(int numRecords, String[]

If I have an array of data, what is the best option for sorting them so they are displayed in ascending alphabetical order based on key 2 of the second array within each ArrayObject? Data ArrayObject:

I am sorting a array of string numbers using ios inbuilt sorting method but it is giving me wrong output.So I applied bubble sorting for a while,Any body can explaing why it is behaving like that.So t

I have an array of at least 2000 random unique integers, each in range 0 < n < 65000. I have to sort it and then get the index of a random value in the array. Each of these operations have to be

Given an infinite positive integer array or say a stream of positive integers, find out the first five numbers whose sum is twenty. By reading the problem statement, it first seems to be 0-1 Knapsack

Is it possible that for two positive integers i and j, (-i)/j is not equal to -(i/j) ? I can't figure out if this is possible...i thought it would be something regarding bits, or overflow of a char ty

When running the following code I end up getting negative values. I am only using positive numbers so I am really confused. I have tried to see if this negative number was a return code but there dose

I got this array: Array ( [0] => Array ( [MONTH] => April [logs-count] => 14 [log_type] => 0 ) [1] => Array ( [MONTH] => August [logs-count] => 942 [log_type] => 0 ) [2] =>

A partition of a positive integer n is an non-increasing array of positive integers a[1] , a[2] , ... , a[m] satisfying a[1] + a[2] + ... +a[m] = n. m is called the length of this partition. We can l

Afternoon all, http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-9-methods/#_Toc362296455 The website mentioned prior displays the question: 8) Write a method that calcul

How can duplicate integers being added into an integer array be avoided without using any of the collections i.e. Arraylist or Set etc.?

In my Python program I concatenate several integers and an array. It would be intuitive if this would work: x,y,z = 1,2,np.array([3,3,3]) np.concatenate((x,y,z)) However, instead all ints have to be

Quick question: Is it possible to declare one array with integers and floats in Fortran 77? If yes, how? Thanks MW

I have an array, say int[] array = new int[] { 1, 5, 11, 5 }; How can I check (in the most easy and efficient way) that all elements are positive? If at least one number is not a positive integer, t

If an array initialized as: $arr = array(array(141,151,161),2,3,array(101,102,array(303,404,606,555,789,array(1000,22,9999,array(9057,100000),522)))); Then the result should be: 100000 I have writte

Given the sum s and an array of positive integers, find the minimal subset whose elements add up to s. For example, given the array {1,2,3,4,5} and the sum s = 8, the minimal subset would be {3,5}. S

I have this array $array = array( array( start => 2013-12-22, end => 2013-12-25 ), array( start => 2013-12-30, end => 2013-12-31 ), array( start => 2013-11-28, end

I originally had the following callback passed as a parameter to the javascript array sort() function: function sortNumber(a,b) { return a-b; } However this doesn't work when my array contains positi

Possible Duplicate: Find the Smallest Integer Not in a List you have a stream of unsorted positive integers. After you read all the numbers from the stream you have to determine the smallest positiv

I am sorting an array of countries, and each have a data-weight attribute which I use in my custom sort function. At this point, a_weight and b_weight are either 0 or 1 (integer). 'United States of Am

I have the following array and I want to sort the array, by value. ( [bwin] => Array ( [0] => Array ( [bookie] => bwin [id_bookie] => 178537 [value] => 6.00 [bettype] => 3way [line]

An in-place algorithm with O(n) running time that rearranges an unsorted array A[0 . . . n − 1] filled with distinct integers so that, for a given k (1<=k<=n), A[0 . . . k − 1] contains the k sm

Given a set of positive and negative integers group all the positive integers on one side and negative integers on one side. The numbers should be in the same order they appear. Example: Array = {1, -

Possible Duplicate: How to find the kth largest element in an unsorted array of length n in O(n)? Is there any algorithm of finding the middle value of given list without performing the sorting oper

I'm trying to make a function in Python that takes a list of integers as input and returns a greater list containing all positive and negative possibilities of those numbers. Pretend '+' is a positive

I have text field in my application which should accept only positive integers only.(no decimal, no negatives). Basically I want to restrict the user to enter only between 1 to 9999 only. <input ty

As per question title, if the array is of an odd length and the array elements are numbered 1 - 10. Example, 3 6 8 1 3 7 7 9 4 1 I was thinking of using heapsort? Since it is an array, merge sort

An unsorted array is given and we need to find top 5 elements in an efficient way and we cannot sort the list . My solution : Find the max element in the array. O(n) Delete this max element after pro

From two unequal arrays, i need to compare & delete based on the last value of an array. Example: m[0] and n[0] are read form a text file & saved as a array, [0] - their column number in text

i have a file with several rows of 10 integers. i want to copy those integers into several arrays, named line1, line2, line3 etc with numbers from each row in a corresponding array. i am currently u

Since every integer can be represented as a series of bits of some length, it seems like you could sort a bunch of integers in the following way: Insert each integer into a binary trie (a trie where

I've been misguided a bit and so am a bit confused.This is what I have understood as an unsorted priority queue.Can someone please confirm? An unsorted priority queue is one in which we insert at the

PHP multidimensional array sorting is a bit confusing to me. What I have is an array I formed with json_decode() from a .jsonp file. It has several variables in each primary array entry. They include

Let's say I run an ActiveRecord query and it returns 3 results, with a bunch of attributes. I want to add 3 attributes to each record in the Array so I can do sorting at a code-level. These 3 include:

how do i sort this array by the nums... Array( [nums] => Array ( [0] => 34 [1] => 12 [2] => 13 ) [players] => Array ( [0] => Mike [1] => Bob [2] => Mary ) ) ... so that i get

I have a cell array of numbers but the majority of the cell array is empty for example: x = [] [6] [] [4] [] [] [] [1] I have a matching array y y = [1, 3,1,5,7,3,1,5] I want to get the index of the

I'm trying to sort the integers of an array, but I keep getting errors with what I try. I've tried sort(array); array.sort(); Arrays.sort(array); and Arrays.sort(); but nothing works. Help would be ap

I am trying to merge to arrays without sorting (add one then another) using pointer method but its just printing the first array and then garbage values. What i am trying to do is just combine 2 array

I want to send the string to an encryption function which accepts an array of four (32-bit) integers. So how to convert string to array of 32 bit integers in javascript and divide it to send it to fun