# [Week One] Programming Contest - Sorting Arrays

This is week one of the programming golf contests. The rules and other information are posted here: Weekly Programming Contest

This weeks challenge: is to write a method that takes in a non-empty primitive integer array and returns an int array with the numbers in order from lowest to highest.

Examples:
sort(new int[] { 21, 3, 10, 4 }) returns {3, 4, 10, 21}
sort(new int[] { 6, -32, 73, 9, 17, -100, -199 }) returns {-199, -100, -32, 6, 9, 17, 73}

Be sure to remember:

• This is CODE GOLF! Efficiency is irrelevant! Shorten it as much as possible!
• Imports are not allowed or the use of any classes outside of java.lang
• Methods must be public and static

Challenge Closes: Sunday 11/8/15

EDIT:
The original array parameter may be modified in the method. The only thing that matters is that a sorted version of the array is returned

Good luck!

Is `Arrays.sort(numbers)` allowed?

You would have to import `java.util.Arrays` and imports are not allowed

1 Like

So what about ājava.utils.Arrays.sort()ā no imports there, just a fully-qualified class name

1 Like

lol nice try. I imaging anything outside of `java.lang` is prohibited.

##Python:

``````def s(l):return sorted(l)
``````

Which is 25 characters. However, that feels a bit like cheating

``````def s(l):
k,i=len(l),0
while i<k:
for j in range(k-1):
if l[j]>l[j+1]:l[j],l[j+1]=l[j+1],l[j]
i+=1
return l
``````

Thatās 123 with a good old bubble sort

Beware this may be a little insane

``````public static int[]s(int[]n){for(int i=1,p,a,b;i<n.length;)for(p=i++;p>0;){a=n[p--];b=n[p];a=a<b?(n[p+1]=b)+(n[p]=a):0;}return n;}
``````

Character count: 130

Tested using random number generator making int arrays of 10000 positive/negative integers. Tested using comparison to output of `Arrays.sort`. Ran test 1000 times, 100% success

Based off an insert sort I wrote ages ago in VB.

Hereās the expanded version:

``````public static int[] sort(int[] array) {
for (int iUp = 1; iUp < array.length; iUp++) {
for (int iDown = iUp; iDown > 0; iDown--) {
int thisNum = array[iDown];
int prevNum = array[iDown - 1];
if (thisNum < prevNum) {
array[iDown] = prevNum;
array[iDown - 1] = thisNum;
}
}
}
return array;
}
``````

*Edited some derp extra characters
*Edit again; add expanded version
*Edit now I know we can modify the input array, reduce code further

1 Like

You are allowed to modify the array. The only thing that matters is that a sorted version of the array is returned. I updated the thread to reflect this.

OK thatās great Iāll keep my post updated with any shorter solutions I can come up with.

Iāll see what I can do with good old standard C? Nah, gonna try python bubble sort first.

My first entry with a codegolf. 159 characters for a simple bubble sort in python. More characters than @Lemonous, but I used a different concept and perhaps it could have been more optimized.

``````def s(a):
n=1
while n:
n=0
for i in range(0,len(a)-1):
if a[i]>a[i+1]:a[i],a[i+1],n=a[i+1],a[i],1
return a
``````

yes, is based off of pseudocode stolen from wikipedia, but it works and I understand it ;-;. Hold up, though. Over the weekend I may try a completely different approach using a complete different sorting function, thatās perhaps a bit more advanced than bubble.

EDIT: removed unnecessary spaces and changed whitespace from 4 spaces to a tab. Reduced to 122 characters.

1 Like

One character fewer and better runtime for non-worst-case. Not bad

Thanks! Tomorrow Iāll try a java solution using a completely different sorting method and recursion (speed and memory consumption donāt matter here). Do I have to take into account negative numbers? Because, if not, I may be able to breach the 100 character line.

Yes

The following solution is slightly iffy on the rules, as it only uses classes within the ājava.langā package, sort ofā¦

``````    public static int[] s(int[] i) throws Throwable {
Class.forName("java.util.Arrays").getMethod("sort", int[].class).invoke(0, i);
return i;
}
``````

Minified version:

``````public static int[]s(int[]i)throws Throwable{Class.forName("java.util.Arrays").getMethod("sort",int[].class).invoke(0,i);return i;}
``````

Character count: 131
I know this character count does not win the competition, but I wanted to propose a clever solution that skirts the rules.

Iāll try and come up with a more legal solution nextā¦

1 Like

I went more for the smallest amount of lines rather than smallest characters using C99:

``````#define NELEMS(x) (sizeof(x) / sizeof(x)[0])
#define EMPTYVALUES(arr) (int count = 0;for(int i = 0; i < NELEMS(arr); ++i) {(arr[i] == 0) ? count++ : count = count;})
#define shiftByOne(newValue, pos, arr) (int *data[pos == NELEMS(arr) ? pos+1 : NELEMS(arr)];for(int i = 0; i < pos; ++i) {data[i] = arr[i];}data[pos] = newValue;for(int j = pos+1; j < NELEMS(data); ++j) {data[j] = arr[j-1];})
#define sort(arr) (int *data[NELEMS(arr)];for(int i = 0, j = 0; i < NELEMS(arr); j=i, ++i) {i == 0 ? data[0] = arr[i] : arr[i] > data[j] ? data[i] = arr[i] : for(int k=i-1;k > -1;k--) {k == 0 ? break : arr[k] > arr[i] ? shiftByOne(arr[i], k, arr) : continue;}}return data;)

int main(int argc, char** argv) {
int * arr = {4, 2, 3, 1, 0};
int *data[] = sort(arr);
}
``````

Also yes Iām aware this doesnāt count, just like Macro Magic. ASM would be too many lines maybe next week ĀÆ_(ć)_/ĀÆ

Copied an ugly āprocedureā from Pascal(Delphi) demos:

``````procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do
inc(i);
while x<a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
``````

This is one of the most efficient sorts. (might be similar to TimSort in Java) It is using recursion.
Java Version: (Hand written, might not compile)

``````static void sort(int[] input) {
sort(input, 1, input.length);
}

static void sort(int[] input, int start, int end) {
int left = start;
int right = end;
int mid = input[(left + right) / 2];
do {
while (input[left] < mid) {
left ++;
}
while (input[right] > mid) {
right --;
}
if (left <= right) {
int t = input[left];
input[left] = input[right];
input[right] = t;
left ++;
right --;
}
} while (left <= right);
if (start < right) {
sort(input, start, right);
}
if (left < end) {
sort(input, left, end);
}
}
``````

Like this much more than bubble. Bubble is hard to write and not efficient, so I never use it.
This sort is more often used in programmings for olympics. (algorithm)

I was talking about radix sort but the specific implementation I was looking at didnāt work in java. It absolutely REQUIRED pointers.

118 Characters

``````public static int[]o(int[]a){int n=0,l;while(++n<a.length)if(a[n-1]>a[n]){l=a[n-1];a[n-1]=a[n];a[n]=l;o(a);}return a;}
``````

Beautified:

``````public static int[] o(int[] a) {
int n = 0, l;
while (++n < a.length)
if (a[n - 1] > a[n]) {
l = a[n - 1];
a[n - 1] = a[n];
a[n] = l;
o(a);
}
return a;
}
``````

Congrats to @jus1in, the first winner of our Weekly Programming Contest! The challenge for week two will be opening shortly.

P.S. I couldnāt help but post my favorite Python solution:

``````import random
def sort(l):
while sorted(l) != l:
random.shuffle(l)``````
4 Likes