1

I have an array in Java

int num[] = {5, -3, 0, -18, 1, 2, 0};

I want to make it look like these

{-3, -18, 0, 0, 5, 1, 2}

What I have right now is this

for (int i=0; i<num.length;i++)
    {
        for (int j=1; j<num.length-1;j++)
        {
            if (num[j]<0)
            {
                temp=num[j];
                c=num[j-1];
                num[j-1]=temp;
                num[j]=c;
            } 
        }  
    }

But this sort just negative numbers, and I can't find solution how to sort zeros. Can you help me, please?

8
  • 9
    I don't understand the sorting logic, could you expand a bit?
    – Tunaki
    Oct 19, 2015 at 16:36
  • I need to have negative numbers at begging of array, followed by zeros, and the positive numbers at the end.
    – John Greg
    Oct 19, 2015 at 16:37
  • 2
    @Tunaki turn an unsorted array into another unsorted array...? Oct 19, 2015 at 16:37
  • OK, but should there be any sorting rule regarding positive numbers together?
    – Tunaki
    Oct 19, 2015 at 16:38
  • The reason it is only sorting negatives is because in your loop you are only comparing to 0. Oct 19, 2015 at 16:39

7 Answers 7

5

You can use Arrays.sort() with a custom comparator, which will preserve the order of the numbers with equal sign:

Integer[] num = {5, -3, 0, -18, 1, 2, 0};
Arrays.sort(num, (a, b) -> Integer.signum(a) - Integer.signum(b));
System.out.println(Arrays.toString(num)); // [-3, -18, 0, 0, 5, 1, 2]

EDIT: Since it turns out that OP just wanted an ordinary sort, that would be

Arrays.sort(num);
2
  • 1
    Integer.signum might be a better choice.
    – Bubletan
    Oct 19, 2015 at 16:51
  • plus one lambdas the cleanest approach in my view
    – singhakash
    Oct 19, 2015 at 16:54
4

The main idea is to have 2 pointers iterating inwards from the head and tail of the int[] until they meet, and swap them on the way if a positive and negative are misplaced. This will work:

public class Solution {
    public void sortNumbers(int[] A) {
        int a = 0;
        int b = A.length - 1;
        for (int i = 0; i < A.length && i <= b; i++) {
            int cur = A[i];
            if (cur < 0) {
                this.swap(A, i, a);
                a++;
            } else if (cur > 0) {
                this.swap(A, i, b);
                b--;
                i--;
            }
        }
    }

    private void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

The runtime is O(n), where n is the length of int[]

1
  • I think loop termination condition i < A.length && i <= b; can be simplified jst as i <= b Mar 14, 2019 at 12:29
4

Time Complexity: O(n) and Space Complexity: O(1)

public void sortNumbers(int[] nums) {
    int start = 0;
    int end = nums.length - 1;
    int index = 0;

    while (start < end && index <= end) {
        if (nums[index] < 0) {
            int temp = nums[index];
            nums[index] = nums[start];
            nums[start] = temp;
            start++;
            index++;

        } else if (nums[index] > 0) {
            int temp = nums[index];
            nums[index] = nums[end];
            nums[end] = temp;
            end--;
        } else {
            index++;
        }
    }
    System.out.println(Arrays.toString(nums));

}
2

If you have 2 D array, sorting it based on each array's first element or second element can be done as follows:

For example, we want to sort
arr= [[-2147483646,-2147483645],[2147483646,2147483647]] based on each arrays second element. We do it like in latest Java 8

Arrays.sort(arr, Comparator.comparingInt(a -> a[1]));

This takes care of positive and negative integers.

1

Here is an easy implentation using a boolean with a do...while loop and a for inner loop :

public static void main(String[] args) {
    int num[] = {5, -3, 0, -18, 1, 2, 0};

    int temp = 0;
    boolean finished = false;

    do{
        finished = true; // This will stay true if nothing needs to be changed in your array.
        for (int i = 0 ; i < num.length - 1 ; i++){
            if (num[i] > num[i+1]){
                finished = false; // Can not go off the loop if it is not sorted yet.
                temp = num[i]; // Interchanging of array's indexes
                num[i] = num[i+1];
                num[i+1] = temp;
            }
        }
    } while(!finished);

    System.out.println(Arrays.toString(num));
}

Output

[-18, -3, 0, 0, 1, 2, 5]
4
  • How is this different than using Arrays.sort()?
    – dguay
    Oct 19, 2015 at 16:46
  • @dguay The algorithm my friend. Sort() ain't no fun. Oct 19, 2015 at 16:49
  • @dguay Arrays.sort() is implemented very differently Oct 19, 2015 at 16:51
  • @SashaSalauyou Maybe but Arrays.sort() output the same thing. Why the need to implement a new sort algorithm if he simply wants to sort an array? Just like @Cinnam answer...
    – dguay
    Oct 19, 2015 at 16:55
1

You can use a simple bubble sort, comparing signs of neighboring elements and swapping those who stand wrong (i. e. i-th has "bigger sign" than (i+1)-th):

for (int j = num.length - 1; j >= 0; j--) {
    for (int i = 0; i < j; i++) {
        if (Integer.signum(num[i]) > Integer.signum(num[i+1])) {  // comparing signs
            int temp = num[i];
            num[i] = num[i+1];
            num[i+1] = temp;               
        } 
    }  
}

Bubble sort is stable, so "equal" elements (here, equal elements are considered those who have the same sign) never change their order, giving you desired result. Being not very effective, this simple algorithm still helps to understand how sorting method, that doesn't require extra space and operates only on initial array, can be implemented.

1
  • First I misunderstood your question, I've just edited my answer to follow actual requirements Oct 20, 2015 at 21:01
0

There are many different sorts which can be used to sort an array of integers from a simple bubble sort to a slightly more complicated heap sort. Some sorts are quicker than each other, for example the heap sort is quicker than the bubble sort, however this mainly affects large arrays. This is due to the amounts of swaps and comparisons between the numbers.

Bubble Sort

public class BubbleSort 
{
    public void sortArray(int[] a)
    {       
        int c, d, swap;

        for(c = 1; c < a.length; c++)
        {
            for (d = 0; d < a.length - c; d++) 
            {
                if (a[d] > a[d+1])
                {
                    swap = a[d];
                    a[d] = a[d+1];
                    a[d+1] = swap;
                }
            }
        }

        for(int i=0;i<a.length;i++)
        {
            int correctNumber = i+1;
            System.out.println("Value "+correctNumber+" of the sorted array which was sorted via the Bubble Sort is: "+a[i]);
        }
    }
}

Heap Sort

public class HeapSort 
{
    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;


    public static void buildheap(int []a)
    {
        n=a.length-1;
        for(int i=n/2;i>=0;i--)
        {
            maxheap(a,i);
        }
    }

    public static void maxheap(int[] a, int i)
    { 
        left=2*i;
        right=2*i+1;
        if(left <= n && a[left] > a[i])
        {
            largest=left;
        }
        else
        {
            largest=i;
        }

        if(right <= n && a[right] > a[largest])
        {
            largest=right;
        }

        if(largest!=i)
        {
            exchange(i,largest);
            maxheap(a, largest);
        }
    }

    public static void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t; 
    }

    public static void sort(int[] a0)
    {
        a=a0;
        buildheap(a);

        for(int i=n;i>0;i--)
        {
            exchange(0, i);
            n=n-1;
            maxheap(a, 0);
        }

        for(int i=0;i<a.length;i++)
        {
            int correctNumber = i+1;
            System.out.println("Value "+correctNumber+" of the sorted array which was sorted via the Heap Sort is: "+a[i]);
        }
    }
}

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.