John Greg
John Greg

Reputation: 152

Sorting an array of zeros, negative and positive numbers

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?

Upvotes: 1

Views: 24458

Answers (7)

SandeepTumati
SandeepTumati

Reputation: 41

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));

}

Upvotes: 4

Afrin Chakure
Afrin Chakure

Reputation: 51

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.

Upvotes: 3

Dan
Dan

Reputation: 7724

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]);
        }
    }
}

Upvotes: 0

Alex Salauyou
Alex Salauyou

Reputation: 14338

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.

Upvotes: 1

Cinnam
Cinnam

Reputation: 1922

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);

Upvotes: 5

Yassin Hajaj
Yassin Hajaj

Reputation: 21975

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]

Upvotes: 1

Ling Zhong
Ling Zhong

Reputation: 1804

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[]

Upvotes: 4

Related Questions