IMPLEMENTATIONS
public class jumpsort {
public int[] sortArray(int[] nums) {
int n = nums.length;
// Separate into negatives and non-negatives
int[] negatives = new int[n];
int[] nonNegatives = new int[n];
int negCount = 0, posCount = 0;
for (int num : nums) {
if (num < 0) {
negatives[negCount++] = num;
} else {
nonNegatives[posCount++] = num;
}
}
// Handle negatives (bucketed using abs)
int maxAbsNeg = 0;
for (int i = 0; i < negCount; i++) {
int absVal = Math.abs(negatives[i]);
if (absVal > maxAbsNeg) {
maxAbsNeg = absVal;
}
}
int[][] negBuckets = new int[maxAbsNeg][];
int[] negBucketCounts = new int[maxAbsNeg];
for (int i = 0; i < negCount; i++) {
int index = Math.abs(negatives[i]) - 1;
negBucketCounts[index]++;
}
for (int i = 0; i < maxAbsNeg; i++) {
negBuckets[i] = new int[negBucketCounts[i]];
negBucketCounts[i] = 0;
}
for (int i = 0; i < negCount; i++) {
int index = Math.abs(negatives[i]) - 1;
negBuckets[index][negBucketCounts[index]++] = negatives[i];
}
// Flatten reversed negatives
int[] sortedNegatives = new int[negCount];
int indexNeg = 0;
for (int i = maxAbsNeg - 1; i >= 0; i--) {
for (int val : negBuckets[i]) {
sortedNegatives[indexNeg++] = val;
}
}
// Handle non-negatives (bucketed by value)
int maxPos = 0;
for (int i = 0; i < posCount; i++) {
if (nonNegatives[i] > maxPos) {
maxPos = nonNegatives[i];
}
}
int[][] posBuckets = new int[maxPos + 1][];
int[] posBucketCounts = new int[maxPos + 1];
for (int i = 0; i < posCount; i++) {
posBucketCounts[nonNegatives[i]]++;
}
for (int i = 0; i <= maxPos; i++) {
posBuckets[i] = new int[posBucketCounts[i]];
posBucketCounts[i] = 0;
}
for (int i = 0; i < posCount; i++) {
int val = nonNegatives[i];
posBuckets[val][posBucketCounts[val]++] = val;
}
int[] result = new int[n];
int index = 0;
for (int i = 0; i < negCount; i++) {
result[index++] = sortedNegatives[i];
}
for (int i = 0; i <= maxPos; i++) {
for (int val : posBuckets[i]) {
result[index++] = val;
}
}
return result;
}
}
class jumpsort(object):
def sortArray(self, nums):
# Separate negatives and non-negatives
negatives = [x for x in nums if x < 0]
non_negatives = [x for x in nums if x >= 0]
# Prepare negative side using counts
if negatives:
max_neg = abs(min(negatives))
neg_counts = [0] * max_neg
for num in negatives:
index = abs(num) - 1
neg_counts[index] += 1
neg_list = []
for i in reversed(range(max_neg)):
neg_list.extend([-i - 1] * neg_counts[i])
else:
neg_list = []
# Prepare non-negative side using counts
if non_negatives:
max_nonneg = max(non_negatives)
pos_counts = [0] * (max_nonneg + 1)
for num in non_negatives:
pos_counts[num] += 1
pos_list = []
for i in range(max_nonneg + 1):
pos_list.extend([i] * pos_counts[i])
else:
pos_list = []
return neg_list + pos_list