Daily Challenge: Sorting Numbers
Another challenge from the daily routine at Kosong Satu Network. Pretty simple and basic — most programming languages provide built-in sorting, but the point here was to exercise the logic by writing the function ourselves. No googling.
The brief: write a function that sorts an array of integers, in any programming language you prefer.
JavaScript
File: sorting.js
function sortInt(payload, direction) {
'use strict';
var isAscending = (direction !== 'desc');
var l = payload.length;
// loop through all items
for (var x = l - 1; x >= 0; x--) {
// original comparator value and position
var origin = payload[x];
var position = x;
// loop through precedents items
for (var y = x - 1; y >= 0; y--) {
var previous = payload[y];
if (( isAscending && previous > origin) ||
(!isAscending && previous < origin)) {
// alright swap comparator
origin = previous;
position = y;
}
}
// need swap? then swap between
if (position !== x) {
var t = payload[position];
payload[position] = payload[x];
payload[x] = t;
}
}
return payload;
}
function sortIntAsc(payload) { return sortInt(payload, "asc"); }
function sortIntDesc(payload) { return sortInt(payload, "desc"); }
exports.sortIntAsc = sortIntAsc;
exports.sortIntDesc = sortIntDesc;
File: test.js
const sorting = require('./sorting');
const assert = require('assert');
describe('SortInt', function () {
describe('#sortIntAsc', function () {
it('should sort array of int in asc order', function () {
var collection = [8, 98, 9, 77, 27, 87, 1];
var expected = [1, 8, 9, 27, 77, 87, 98];
assert.deepEqual(sorting.sortIntAsc(collection), expected);
});
});
describe('#sortIntDesc', function () {
it('should sort array of int in desc order', function () {
var collection = [8, 98, 9, 77, 27, 87, 1];
var expected = [98, 87, 77, 27, 9, 8, 1];
assert.deepEqual(sorting.sortIntDesc(collection), expected);
});
});
});
➜ sort git:(master) ✗ mocha
SortInt
#sortIntAsc
✓ should sort array of int in asc order
#sortIntDesc
✓ should sort array of int in desc order
2 passing (10ms)
Golang
File: sorting.go
package main
const (
ASC = "asc"
DESC = "desc"
)
func SortInt(a []int, d string) []int {
for i := len(a) - 1; i >= 0; i-- {
current := a[i]
position := i
for j := i - 1; j >= 0; j-- {
prev := a[j]
if (d == ASC && current < prev) || (d == DESC && current > prev) {
current = prev
position = j
}
}
if position != i {
t := a[position]
a[position] = a[i]
a[i] = t
}
}
return a
}
func SortIntAsc(a []int) []int { return SortInt(a, ASC) }
func SortIntDesc(a []int) []int { return SortInt(a, DESC) }
File: sorting_test.go
package main
import (
"math/rand"
"reflect"
"strconv"
"strings"
"testing"
)
// generates_random — random array of int based on count and max int
// not used here.
func generates_random(count int, max int) []int {
a := make([]int, count)
for i := count - 1; i >= 0; i-- {
a[i] = rand.Intn(max)
}
return a
}
func int_to_string_arrays(a []int) []string {
r := []string{}
for _, v := range a {
r = append(r, strconv.Itoa(v))
}
return r
}
func TestSorting(t *testing.T) {
collection := []int{8, 98, 9, 77, 27, 87, 1}
expected := []int{1, 8, 9, 27, 77, 87, 98}
if !reflect.DeepEqual(expected, SortIntAsc(collection)) {
t.Errorf("asc orders expected %s got %s",
strings.Join(int_to_string_arrays(expected), ","),
strings.Join(int_to_string_arrays(collection), ","))
}
expected = []int{98, 87, 77, 27, 9, 8, 1}
if !reflect.DeepEqual(expected, SortIntDesc(collection)) {
t.Errorf("desc orders expected %s got %s",
strings.Join(int_to_string_arrays(expected), ","),
strings.Join(int_to_string_arrays(collection), ","))
}
}
➜ sort git:(master) ✗ go test
PASS
ok _/chazuka/challenges/sort 0.006s
The shape of the algorithm — selection-style swap, tracking position and origin — falls out almost identically in both languages. Useful reminder that the language is mostly notation; the structure of the thinking is the same.