[Week One] Programming Contest - Sorting Arrays

General Discussion Off Topic
1

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!

2

Is Arrays.sort(numbers) allowed?

3

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

1 Like
4

So what about ā€œjava.utils.Arrays.sort()ā€ no imports there, just a fully-qualified class name :slight_smile:

1 Like
5

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

6

##Python:

def s(l):return sorted(l)

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

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 :slight_smile:

7

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
8

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.

9

OK thatā€™s great :slight_smile: Iā€™ll keep my post updated with any shorter solutions I can come up with.

10

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
11

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

12

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.

13

Yes

14

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
15

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 ĀÆ_(惄)_/ĀÆ

16

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)

17

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

18

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;
}
19

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