Reputation: 152
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
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
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
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
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
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
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
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