You are given a sorted array containing both negative and positive values. Resort the array taking absolute value of negative numbers. Your complexity should be O(n)
Sample Input
[-8, -5, -3, -1, 3, 6, 9]
Expected Output
[ -1, -3, 3, -5, 6, -8, 9 ]
I have done this till now, but output is not correct.
function sortMe(input) {
var newArr = [];
for (var i = 0; i < input.length; i++) {
var value = Math.abs(input[i]);
newArr.push(value);
}
var c = newArr.sort()
}
and it is giving output
[ 1, 3, 3, 5, 6, 8, 9 ]
You are given a sorted array containing both negative and positive values. Resort the array taking absolute value of negative numbers. Your complexity should be O(n)
Sample Input
[-8, -5, -3, -1, 3, 6, 9]
Expected Output
[ -1, -3, 3, -5, 6, -8, 9 ]
I have done this till now, but output is not correct.
function sortMe(input) {
var newArr = [];
for (var i = 0; i < input.length; i++) {
var value = Math.abs(input[i]);
newArr.push(value);
}
var c = newArr.sort()
}
and it is giving output
[ 1, 3, 3, 5, 6, 8, 9 ]
11 Answers
Reset to default 9Split the array in to two halves, one with negative numbers and the other with positive numbers.
Reverse the negative numbers array.
Then, run merging algorithm with the absolute value of both the arrays.
Overall runtime complexity is still O(n).
function sortMe(sortedArray) {
var idx = -1, negs, pos, result = [], nIdx = 0, pIdx = 0;
if (sortedArray.length === 0)
return result;
// Find the index where positive elements begin
while (idx < sortedArray.length && sortedArray[++idx] < 0);
// Get elements till the index and reverse the array
negs = sortedArray.slice(0, idx).reverse();
// Get elements from the index till the end
pos = sortedArray.slice(idx);
// Merging algorithm implementation which merges `negs` and `pos`
while (nIdx < negs.length || pIdx < pos.length)
{
if (nIdx < negs.length && pIdx < pos.length)
{
if (Math.abs(negs[nIdx]) <= pos[pIdx])
result.push(negs[nIdx++]);
else
result.push(pos[pIdx++]);
}
else if (nIdx < negs.length)
result.push(negs[nIdx++]);
else
result.push(pos[pIdx++]);
}
return result;
}
console.log(sortMe([-8, -5, -3, -1, 3, 6, 9]));
// [ -1, -3, 3, -5, 6, -8, 9 ]
function sortMe(sortedArray) {
var idx = -1, negs, pos, result = [], nIdx = 0, pIdx = 0;
if (sortedArray.length === 0)
return result;
// Find the index where positive elements begin
while (idx < sortedArray.length && sortedArray[++idx] < 0);
// Get elements till the index and reverse the array
negs = sortedArray.slice(0, idx).reverse();
// Get elements from the index till the end
pos = sortedArray.slice(idx);
// Merging algorithm implementation which merges `negs` and `pos`
while (nIdx < negs.length || pIdx < pos.length)
{
if (nIdx < negs.length && pIdx < pos.length)
{
if (Math.abs(negs[nIdx]) <= pos[pIdx])
result.push(negs[nIdx++]);
else
result.push(pos[pIdx++]);
}
else if (nIdx < negs.length)
result.push(negs[nIdx++]);
else
result.push(pos[pIdx++]);
}
return result;
}
function getElement(id) {
return document.getElementById(id);
}
function sorter() {
var data = getElement("numbers").value.split(" ").map(Number);
getElement("result").innerHTML = "[" + sortMe(data).join(", ") + "]";
}<input id="numbers" value="-8 -5 -3 -1 3 6 9" />
<input type="button" onclick="sorter()" value="Click here to Sort" />
<pre id="result" />Can be done by taking in mind 3 cases:
a. All positive numbers : leave the array as is
b. All negative numbers : reverse the array
c. Positive as well as negative numbers : find last negative number in input array and then use left and right to compare.
import java.util.Arrays;
public class SortAbsoluteValue {
// all positive; all negative; postive & negative
public static void main(String[] args) {
int[] num = new int[] { -8, -5, -3, -1, 3, 6, 9 };
int[] result = sortAbsolute(num);
for (int i = 0; i < num.length; i++) {
System.out.println(result[i]);
}
}
private static int[] sortAbsolute(int[] num) {
int size = num.length;
// all positive : leave as is
if (num[0] >= 0)
return num;
// all negative : reverse array
if (num[size-1] < 0) {
int[] temp = Arrays.copyOf(num, num.length);
Arrays.sort(temp);
return temp;
}
int[] result = new int[size];
int i = 0;
for (i = 0; i < size - 1; i++) {
if (num[i] < 0 && num[i + 1] >= 0) {
break;
}
}
int left = i - 1;
int right = i + 1;
result[0] = num[i];
int k = 0;
while (left >= 0 && right < size) {
if (Math.abs(num[left]) < num[right]) {
result[++k] = num[left];
left--;
} else {
result[++k] = num[right];
right++;
}
}
// remaining left elements, if any
while(left>=0) {
result[++k] = num[left--];
}
// remaining right elements, if any
while(right<size) {
result[++k] = num[right++];
}
return result;
}
}
@thefourtheye, your solution is very good, but it does not correct process number sequences where numbers(positive and negative ones) are mixed. You can check your solution with the next sequence, for example: [-2 -5 3 8 -10] and it will give you wrong result : [3, -5, -2, 8, -10].
This is because:
1) You rely that negative and positive numbers should go in the sorted order.
2) Find indexes of positive and negative numbers despite the fact that they can go inconsistently.
I've corrected your code and now it can process any mixed positive/negative number sequences and correctly sort them by absolute values. Code is below:
function sortArrayByAbsValues(sortedArray) {
var negs = [], pos = [], result = [], nIdx = 0, pIdx = 0;
if (sortedArray.length === 0)
return result;
//prepare negative/positive number sequences.
for (var i = 0; i < sortedArray.length; i++) {
var value = sortedArray[i];
if (value < 0) {
negs.push(value);
} else {
pos.push(value);
}
}
// sort positive/negative numbers
pos = pos.sort();
negs = negs.sort();
// Merging algorithm implementation which merges `negs` and `pos`
while (nIdx < negs.length || pIdx < pos.length) {
if (nIdx < negs.length && pIdx < pos.length) {
if (Math.abs(negs[nIdx]) <= pos[pIdx])
result.push(negs[nIdx++]);
else
result.push(pos[pIdx++]);
}
else if (nIdx < negs.length)
result.push(negs[nIdx++]);
else
result.push(pos[pIdx++]);
}
return result;
}
You can simply achieve this using Bubble sort
var array= new Array(2,-2,3,5,-3,1);
function absoluteSortin(array){
var inputArray= array.slice(0);
var temp;
for(var i=0;i< inputArray.length;i++){
for(j=i+1; j<inputArray.length;j++){
if(Math.abs(inputArray[i]) > Math.abs(inputArray[j])){
temp= inputArray[j];
inputArray[j] = inputArray[i];
inputArray[i] = temp;
}
}
}
return inputArray;
}
absoluteSortin(array);
<?php
$a = array(-2,-3,0,5,4,1,6,9,7,-9,-1,3);
for($i=0;$i<count($a)-1;$i++) {
for($j=0;$j<count($a)-1;$j++){
$data1=abs($a[$j]);
$data2=abs($a[$j+1]);
if($data1>$data2) {
$temp = $a[$j];
$a[$j] = $a[$j+1];
$a[$j+1] = $temp;
}
}
}
echo "<pre>";
print_R($a);
?>
Here is the code in Python
def sorted_array(list1):
list_negative=[]
list_positive=[]
for i in list1:
if i<0:
list_negative.append(i)
else:
list_positive.append(i)
list_negative.reverse()
for i in list_negative:
for j in range(0, len(list_positive)):
if abs(i)<=list_positive[j]:
list_positive.insert(j,i)
break
print(list_positive)
list1=[-8,-5,-3,-1,3,6,9,-4]
sorted_array(list1)
two pointer approach.
void resort(vector<int> &a){
int par ; // partition index (when +ve elements starts)
// lets find where positive elements starts
for(int i = 0; i < a.size(); i++){
if(a[i] >= 0) {
par = i;
break;
}
}
int l = par-1; // left of par
int r = par; // right side
vector<int> b; // extra array for answer
// compare left and right side element
// if any of them is lesser push that element in extra array i.e 'b'
while(l >= 0 and r < a.size()) {
if(abs(a[l]) > a[r]) {
b.push_back(a[r]);
r++;
}
else if(abs(a[l]) < a[r]){
b.push_back(a[l]);
l--;
}
else{
b.push_back(a[l]);
l--;
}
}
// push remaing element from both side
// like merge sort
while(l >= 0) {
b.push_back(a[l]);
l--;
}
while(r < a.size()) {
b.push_back(a[r]);
r++;
}
// print modified answer
for(auto x:b) {
cout<<x<<" ";
}
}
Time Compl. O(N)
Space Compl. O(N)
int[] arr = new int[] { -8, -5, -3, -1, 3, 6, 9 };
for(int i = 0; i < arr.length; i++) {
int pos = 0;
for (int j = 0; j < arr.length; j++) {
if (Math.abs(arr[pos]) > Math.abs(arr[j])) {
int temp;
temp = arr[pos];
arr[pos] = arr[j];
arr[j] = temp;
pos++;
}
}
}
You can do with one line in Python
nums = [-8, -5, -3, -1, 3, 6, 9]
print(sorted(nums,key=abs))
The output will be
[-1, -3, 3, -5, 6, -8, 9]
here is a quick solution
break list in two part first part negative and second list will contains positive number
apply merge algorithm to merge both list example in c#-.
List<int> neg = arr.Where(x => x < 0).Reverse().ToList(); List<int> pos = arr.Where(x => x > 0).ToList(); var res=merge(neg,pos); private static List<int> merge(List<int> left, List<int> right) { List<int> result = new List<int>(); while (left.Count > 0 || right.Count > 0) { if (left.Count > 0 && right.Count > 0) { if (Math.Abs(left.First()) <= right.First()) { result.Add(left.First()); left.Remove(left.First()); } else { result.Add(right.First()); right.Remove(right.First()); } } else if (left.Count > 0) { result.Add(left.First()); left.Remove(left.First()); } else if (right.Count > 0) { result.Add(right.First()); right.Remove(right.First()); } } return result; }
inputArray.sort(function(a,b) {
return Math.abs(a) - Math.abs(b);
});
Might not be O(n) but worked well for me