Liste der Nummern sortieren [geschlossen]

25

Über Code-Bowling:

Beim Golf versuchen Sie, die niedrigste Punktzahl zu erzielen (kleinste Anwendung, eleganteste usw.). In Bowling versuchen Sie, die höchste Punktzahl zu erzielen. Wenn Sie also folgen, besteht das Ziel einer Code-Bowling-Herausforderung darin, den größten, am meisten verfälschten und am schwierigsten zu verwaltenden Teil des Codes so zu gestalten, dass er die Anforderungen der Herausforderung noch erfüllt. Es macht jedoch keinen Sinn, die Quelle nur deswegen länger zu machen. Es muss so aussehen, als ob die zusätzliche Länge vom Design und nicht nur der Polsterung herrührt.

Die Herausforderung:

Erstellen Sie ein Programm, das eine Liste von Zahlen in aufsteigender Reihenfolge sortiert.

Beispiel:

Eingabe: 1, 4, 7, 2, 5

Ausgabe: 1, 2, 4, 5, 7

Code: Offensichtlich wäre dies keine gute Antwort, da es dort nicht viele WTFs gibt

function doSort(array $input) {
    sort($input);
    return $input;
}

Regeln:

Es gibt keine wirklichen Regeln. Solange das Programm funktioniert, muss es sein!

Denken Sie daran: Dies ist Code-Bowling, nicht Golf. Das Ziel ist es, den schlechtesten und am meisten bastardisierten Code zu erstellen, den Sie können! Bonuspunkte für Code, der gut aussieht, aber tatsächlich trügerisch böse ist ...

ircmaxell
quelle
Ich wünschte, ich hätte noch den Warteschlangencode für den Kalender, den ich einmal geschrieben habe ...
Peter Taylor
14
sort(sort(sort(sort(sort(sort(myarray))))))Garantiert perfekte Sortierung!
Mateen Ulhaq

Antworten:

21

Sortieren nach Benutzereingabe. Was kann schlimmer sein?

function sort(array) {
    newArray = new Array
    notSorted = true;
    while (notSorted) {
        sortfail = false;
        i = -1
        for (;;) {
            if ((++i + 1) == array.length) break;
            if (confirm("is " + array[i] + " less than " + array[i + 1])) {
                newArray[i] = array[i]
                newArray[i + 1] = array[i + 1]
            } else {
                newArray[i] = array[i + 1]
                newArray[i + 1] = array[i]
                array[i] = newArray[i]
                array[i + 1] = newArray[i + 1]
                sortfail = true
            }
        }
        array = newArray;
        if (!sortfail) notSorted = false
    }
    return array
}

console.log(sort([2,1,3]))

Siehe Live- Beispiel

Raynos
quelle
Sie können es besser machen ... :-D
ircmaxell
Besser und trotzdem richtig sortieren? Das ist ein Schmerz. Das ist algorithmisch schrecklich. Ich muss den Code nicht viel schrecklicher machen.
Raynos
5
Benutzereingaben sind oft falsch. Benutzer sind möglicherweise betrunken oder hoch, und es kann auch Gegner geben, die Ihnen absichtlich den falschen Befehl erteilen. Sollte zufällig mischen und erneut fragen, bis Sie eine angemessene Anzahl von Antworten für die gleiche Paarung haben.
Paul
@ Paul der Mangel an Schutz vor Benutzereingaben ist einer der Hauptvorteile dieser Codeschale. Ich denke, eine völlig nutzlose Validierung der Benutzereingaben wäre besser als keine.
Raynos
Ich bin mir nicht sicher über das manuelle Element.
Steve Robbins
16
class Array
  def sort
    self.permutation.min
  end
end

Ah, die Eleganz von Ruby ... self.permutation ergibt einen Enumerator. Noch kein Schaden angerichtet. Die unschuldig aussehende .min saugt diesen Enumerator jedoch in ein Array. Die Größe dieses Arrays explodiert, wenn die Anzahl der Elemente steigt. Ganz zu schweigen davon, dass dies eine bereits existierende Sorte ruiniert.

steenslag
quelle
2
Es ist Code-Bowling, wenn Sie es noch nicht gesehen haben - Sie müssen den längsten Code schreiben ! ;)
nyuszika7h
3
Ich gehe für den Bonus "gut aussehend, aber täuschend böse" :)
Steenslag
3
Ich würde sagen, dass dies für jeden SQL-Programmierer perfekt aussieht. Jetzt muss der Compiler nur noch herausfinden, dass das, was Sie wollten, nur eine einfache Art war.
aaaaaaaaaaa
15

Bogosort!

import random

def is_sorted(seq):
    for x, y in zip(seq[:-1], seq[1:]):
        if x > y:
            return False
    return True

def sort(seq):
    while not is_sorted(seq):
        random.shuffle(seq)
dan04
quelle
verdammt du hast mich geschlagen ...
arrdem
Dies ist Bogosort
Caridorc
Effizienz:O(2n random)
siehe 11.03.15
12

Perl Bubble Sort

push(@m,'0');$a=<>;push(@m,$a);
$a=pop@m;push(@c,$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
$a=pop@c;push(@c,$a);for(1..$a){$a=<>;push(@m,$a);
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;$b=pop@m;$hash{$a}=$b;
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;$b=pop@m;push(@m,$b+$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
}$a=pop@c;push(@m,$a);
push(@m,'2');$a=pop@m;$b=pop@m;for(1..$a){push(@m,$b);};
$a=pop@m;$b=pop@m;push(@m,$b*$a);
$a=pop@m;push(@c,$a);
$a=pop@c;push(@c,$a);for(1..$a){push(@m,'1');$a=pop@m;push(@m,-$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
$a=pop@c;push(@c,$a);for(1..$a){push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;$b=pop@m;push(@m,$b+$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;push(@m,$hash{$a});
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;push(@m,-$a);
$a=pop@m;$b=pop@m;push(@m,$b+$a);
$a=pop@m;push(@m,$hash{$a});
$a=pop@m;$b=pop@m;if($b < $a){push(@c,1)}else{push(@c,0)};
$a=pop@c;push(@c,$a);for(1..$a){push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;push(@m,$hash{$a});
push(@m,'t');$a=pop@m;$b=pop@m;$hash{$a}=$b;
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;push(@m,-$a);
$a=pop@m;$b=pop@m;push(@m,$b+$a);
$a=pop@m;push(@m,$hash{$a});
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;$b=pop@m;$hash{$a}=$b;
push(@m,'t');$a=pop@m;push(@m,$hash{$a});
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;push(@m,-$a);
$a=pop@m;$b=pop@m;push(@m,$b+$a);
$a=pop@m;$b=pop@m;$hash{$a}=$b;
}$a=pop@c;push(@m,$a);
$a=pop@m;
}}push(@m,'0');push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
$a=pop@c;push(@c,$a);for(1..$a){push(@m,'p');$a=pop@m;push(@m,$hash{$a});
$a=pop@m;push(@m,$hash{$a});
$a=pop@m;print$a;
push(@m,'p');$a=pop@m;push(@m,$hash{$a});
push(@m,'1');$a=pop@m;$b=pop@m;push(@m,$b+$a);
push(@m,'p');$a=pop@m;$b=pop@m;$hash{$a}=$b;
}

Ich habe mich für den Look "Jede einzelne Linie sieht aus wie das gleiche Rauschen" entschieden. Die erste Eingabezeile (bei STDIN) teilt dem Programm mit, wie viele Nummern es gibt, während die nächsten N Zeilen eine Nummer enthalten, die sortiert werden muss.

PhiNotPi
quelle
3
Stack-based Perl :)
Daniel Gratzer
Ich hätte gerne eine Erklärung, wie es funktioniert? Ich habe einige Vermutungen
Xavier Combelle
12

Generischer Multithread-Bogosort in Java

46 Sekunden, um 4 Zahlen zu sortieren

Ich dachte, es wäre elegant mit Unterstützung für Generika. Auch Multithreading ist immer schön, also verwende ich das anstelle von Randomisierung: Dieses Programm generiert einen Thread für jede zu sortierende Zahl. Jeder Thread versucht, sein Element in ein Array-Objekt einzufügen. Wenn alle Elemente eingefügt wurden, prüft das Programm, ob das Array sortiert ist. Wenn nicht, versuchen Sie es erneut. Natürlich muss diese Einfügung synchronisiert werden.

ElementInserter

Dies ist die Klasse, die wir für die Threads verwenden. Diese Klasse enthält ein Element und versucht, es in das sortedArrayfolgende einzufügen :

class ElementInserter<E extends Comparable<? super E>> implements Runnable {
    E element;
    SortedArray<? super E> target;

    ElementInserter(E e, SortedArray<? super E> a) {
        element = e;
        target = a;
    }

    @Override
    public void run() {
        target.insert(element);
    }
}

sortiertArray

Sport eine einfache Einfügemethode. Wenn das letzte Element eingefügt wurde, prüft es, ob das Array sortiert ist.

class SortedArray<E extends Comparable<? super E>> {
    boolean sorted; int i = 0; E[] a;

    SortedArray(E[] e) { a = e; }

    synchronized public void insert(E e) {
        while (!sorted) {
            a[i++] = e;

            if (i == a.length) {
                sorted = true;

                for (int j = 1; j < i; ++j)
                    if (a[j-1].compareTo(a[j]) > 0) {
                        sorted = false;
                        i = 0;
                        notifyAll();
                    }

                if (sorted) {
                    for (int j = 0; j < a.length; ++j) System.out.print(a[j]+" ");
                    System.out.println();
                    notifyAll(); // allow all threads to terminate
                }

            } else
                try { wait(); }
                catch(InterruptedException x) { }
        }
    }
}

Hauptmethode

Analysiert Befehlszeilenargumente als Ganzzahlen, erstellt ein neues Array und einen neuen Thread für jede Ganzzahl:

    public static void main (String[] args) {
        Integer[] i = new Integer[args.length];
        SortedArray<Integer> c = new SortedArray<Integer>(i);

        for (String s : args)
            new Thread(new ElementInserter<Integer>(Integer.parseInt(s), c)).start();
    }

Testlauf

Die Ausführungszeit hängt von der ursprünglichen Reihenfolge der Elemente und Ihrer Scheduler-Implementierung ab. Dies ist auf einem Dual-Core-2,9-GHz-Intel i7 MacBook Pro:

$ time java Main 3 1 2 4
1 2 3 4 

real    0m46.307s
user    0m14.629s
sys     0m26.207s
daniero
quelle
1
Haha +1 Ich habe einen Kick aus diesem
Arshajii
10

JavaScript (mit Animation!). 8172 Zeichen. Einige Stunden für 6 Nummern.

Wir mögen Lotto, richtig? Ähnlich wie Bogosort von dan04, aber mit Physik und Animation ...

(function(){var e={},v=!1,G=/abc/.test(function(){abc})?/\b_super\b/:/.*/,H=function(c,a,b){return function(){var l=this._super,s;this._super=b[c];try{s=a.apply(this,arguments)}finally{this._super=l}return s}};e.Class=function(){};e.Class.extend=function a(b){var l=this.prototype;v=!0;var s=new this;v=!1;for(var c in b)s[c]="function"===typeof b[c]&&"function"===typeof l[c]&&G.test(b[c])?H(c,b[c],l):b[c];b=function(){!v&&this.init&&this.init.apply(this,arguments)};b.prototype=s;b.prototype.constructor=
b;b.extend=a;return b};e.Events={};var k=e.Events,z,A,w=Object.prototype.toString,I=document.createEvent,r=Date.now;k.EventListener=e.Class.extend({handleEvent:function(){},init:function(a){this.handleEvent=a}},"EventListener");z=k.EventListener;k.Event=e.Class.extend({timeStamp:0,type:"",target:null,cancelable:!1,defaultPrevented:!1,preventDefault:function(){this.cancelable&&(this.defaultPrevented=!0)},initEvent:function(a,b){this.type=a;this.target=b;this.timeStamp=r()}},"Event");A=k.Event;var t=
Object.create(null);e.createEventType=function(a,b){t[a]=A.extend(b,a);return t[a]};e.createEvent=function(a){return null!=t[a]?(a=new t[a],a.timeStamp=r(),a):I(a)};k.EventTarget=e.Class.extend({_listeners:{},addEventListener:function(a,b,l){var c=this._listeners[a];if(!(null!=c&&function(){for(var a="object"===typeof l?l:null,d,e=0,f=c.length;e<f;e++)if(d=this.listeners[e],d.listener.handleEvent===b&&d.scope===a)return!0;return!1}())){var d={listener:"object"===typeof b&&b.handleEvent?b:new z(b),
scope:"object"===typeof l?l:null};"[object Array]"===w.call(c)?c.push(d):this._listeners[a]=[d]}},removeEventListener:function(a,b,c){a=this._listeners[a];if("[object Array]"===w.call(a)){c="object"===typeof c?c:null;for(var d=0,e=a.length;d<e;d++)if(a[d].listener.handleEvent===b&&a[d].scope===c){a.splice(d,1);break}}},dispatchEvent:function(a){a.target||(a.target=this);var b=0,c=this._listeners[a.type],d=c.length,e;if("[object Array]"===w.call(c))for(;b<d;b++)e=c[b].listener.handleEvent,e.call(c[b].scope,
a);return a.defaultPrevented}},"EventTarget");for(var B=0,k=["ms","moz","webkit","o"],h=0;h<k.length&&!window.requestAnimationFrame;++h)window.requestAnimationFrame=window[k[h]+"RequestAnimationFrame"],window.cancelAnimationFrame=window[k[h]+"CancelAnimationFrame"]||window[k[h]+"CancelRequestAnimationFrame"];window.requestAnimationFrame||(window.requestAnimationFrame=function(a){var b=r(),c=Math.max(0,16-(b-B)),d=window.setTimeout(function(){a(b+c)},c);B=b+c;return d});window.cancelAnimationFrame||
(window.cancelAnimationFrame=function(a){clearTimeout(a)});var x=window.clearInterval,C=window.setInterval,D=e.Class.extend({fn:function(){},args:[],thisArg:window,sleepTime:0,init:function(a,b,c){this.method=a||function(){};this.thisArg=b||window;this.args=c||[]}},"FunctionToCall"),r=Date.now,u=Object.create(null);u.animation=0;u.steady=1;u.as_fast_as_possible=2;e.Timer=e.Events.EventTarget.extend({ANIMATION:0,STEADY:1,AS_FAST_AS_POSSIBLE:2,TimerEvent:e.createEventType("TimerEvent",{FPS:0,targetFPS:0,
delta:0,initEvent:function(a,b){if(null==b.getFPS||null==b.targetFPS||null==b.dt)throw notATimerException;this.FPS=b.getFPS();this.targetFPS=b.targetFPS;this.delta=b.dt;this._super(a,b)}}),_clearIntervalFlag:!1,_recursionCounter:0,_tickHandlersFromMethod:Object.create(null),running:!1,paused:!1,mode:0,autoStartStop:!0,setAutoStartStop:function(a){this.autoStartStop=a},prevTime:0,dt:0,maxDelta:0.05,setMaxDelta:function(a){this.maxDelta=a},sysTimerId:-1,targetFPS:50,setFPS:function(a){this.targetFPS=
a;if(this.running&&this.mode===this.STEADY){x(this.sysTimerId);var b=this;this.sysTimerId=C(function(){b.tick()},1E3/a)}},getFPS:function(){return 1/this.dt},queue:[],addToQueue:function(a,b,c){var d=new D(a,b,c),e;this.queue.push(d);var f=function J(f){0<d.sleepTime?d.sleepTime-=f.delta:(e=a.apply(b,[f].concat(c)),"number"===typeof e&&0<e?d.sleepTime=e:!0!==e&&(this.removeEventListener("tick",J,this),this.queue.splice(this.queue.indexOf(d),1)))};null==this._tickHandlersFromMethod[a]?this._tickHandlersFromMethod[a]=
[f]:this._tickHandlersFromMethod[a].push(f);this.addEventListener("tick",f,this);this.autoStartStop&&!this.running&&this.startLoop()},removeFromQueue:function(a){var b=this._tickHandlersFromMethod[a];a=this.queue.indexOf(a);if(-1!==a){for(var c=0,d=b.length;c<d;c++)this.removeEventListener("tick",b[c],this);return this.queue.splice(a,1)}},getQueue:function(){return this.queue.slice(0)},pause:function(){this._clearIntervalFlag=this.paused=!0;this.dt=0},resume:function(){this.paused=!1;this.startLoop()},
startLoop:function(){this.prevTime=r();this.running=!0;if(this.mode===this.steady){var a=this;this.sysTimerId=C(function(){a.tick()},1E3/this.targetFPS)}else this.tick()},tick:function(){if(this._clearIntervalFlag&&-1!==this.sysTimer)x(this.sysTimerId),this.sysTimerId=-1,this._clearIntervalFlag=!1;else if(!this.paused){var a=r();this.dt=(a-this.prevTime)/1E3;this.dt>this.maxDelta&&(this.dt=this.maxDelta);if(0===this.dt&&4>this._recursionCounter)this._recursionCounter++,this.tick();else{0<this._recursionCounter&&
(this._recursionCounter=0);var b=e.createEvent("TimerEvent");b.initEvent("tick",this);this.dispatchEvent(b);this.prevTime=a;a=!(this.autoStartStop&&0>=this.queue.length);if(this.mode===this.AS_FAST_AS_POSSIBLE&&a){var c=this;setTimeout(function(){c.tick()},0)}if(this.mode===this.ANIMATION&&a){var d=this;requestAnimationFrame(function(){d.tick()})}a||(this.running=!1,this.mode===this.STEADY&&-1!==this.sysTimerId&&(x(this.sysTimerId),this.sysTimerId=-1))}}},init:function(a){this.mode="number"===typeof a?
a:u[a];if(null==this.mode||0>this.mode||2<this.mode)this.mode=0}},"Timer");e.Timer.ANIMATION=0;e.Timer.STEADY=1;e.Timer.AS_FAST_AS_POSSIBLE=2;e.Timer.FunctionToCall=D;var j=[2,3,5,8,4,6],m=new (e.Class.extend({displace:0,velocity:0,drag:0.01,tickInterval:10,update:function(a){this.displace+=this.velocity*a.delta;this.velocity*=1-this.drag},init:function(){}})),q=j.slice(0),k=new e.Timer(0),h=document.createElement("div");h.style.width=23*j.length-28+"px";h.style.height="22px";h.style.overflowX="hidden";
h.style.overflowY="hidden";h.style.border="1px #555 solid";h.style.fontFamily='Consolas, "Courier New"';for(var c=[],f=0;f<j.length;f++)c[f]=document.createElement("div"),c[f].style.width="20px",c[f].style.height="20px",c[f].style.display="inline-block",c[f].style.position="relative",c[f].style.left=f+1===j.length?"-22px":"0px",c[f].style.top=f+1===j.length?"-22px":"0px",c[f].style.border="1px #AAA solid",c[f].style.textAlign="center",c[f].innerHTML=j[f],h.appendChild(c[f]);var g=0,d=1,n,p,E=0,F=
0,y=0;m.velocity=1E3*Math.random()+500;document.getElementsByTagName("body")[0].appendChild(h);k.addToQueue(function(a){if(5>m.velocity)if(0===g){for(a=0;a<c.length;a++)if((m.displace+22+22*a)%(22*j.length)-22<11*c.length&&(m.displace+22+22*a)%(22*j.length)>11*c.length){n=c[a];E=parseFloat(n.style.left);break}for(a=0;a<c.length;a++)if((m.displace+22+22*a)%(22*j.length)<11*c.length&&(m.displace+22+22*a)%(22*j.length)+22>11*c.length){p=c[a];F=parseFloat(p.style.left);break}y=p.offsetLeft-n.offsetLeft;
g=1}else if(1===g)n.style.backgroundColor="rgba(255,255,0,"+Math.round(1-d)+")",p.style.backgroundColor="rgba(255,255,0,"+Math.round(1-d)+")",d-=10*a.delta,0>d&&(g=2);else if(2==g)n.style.backgroundColor="rgba(255,255,0,"+Math.round(1-d)+")",p.style.backgroundColor="rgba(255,255,0,"+Math.round(1-d)+")",d+=10*a.delta,1<d&&(g=3,n.style.backgroundColor="rgba(255,255,255,0)",p.style.backgroundColor="rgba(255,255,255,0)",d=0);else if(3==g)n.style.left=E+d*y+"px",p.style.left=F-d*y+"px",d+=2*a.delta,1<
d&&(g=4);else if(4==g){if(d-=a.delta,0.5>d){a=c.indexOf(n);var b=c.indexOf(p),e;e=n.innerHTML;c[a].innerHTML=p.innerHTML;c[b].innerHTML=e;e=q[a];q.splice(a,1,q[b]);q.splice(b,1,e);b=-1/0;for(a=0;a<q.length;a++){if(q[a]<b){g=5;break}b=q[a]}g=5===g?5:6}}else if(5===g)d=1,m.velocity=1E3*Math.random()+500,g=0;else{if(6===g)return d=1,g=0,document.getElementsByTagName("body")[0].innerHTML+=q,!1}else{m.update(a);for(a=0;a<c.length;a++)b=(m.displace+22+22*a)%(22*j.length),a+1===j.length&&(b+=22*(j.length-
1)),c[a].style.left=b-22*a-22+"px"}return!0})})();​

Allerdings habe ich ein bisschen Google Closure Compiler benutzt, um ... ich weiß es nicht. Aber es sieht hässlicher aus, oder?

Es ist wie eines dieser Glücksräder, und jedes Mal, wenn es anhält, wechselt es zu Zahlen in der Mitte. Sie können hier spielen: http://jsfiddle.net/VkJUE/5/ (um zu verstehen, was ich meine)

Es funktioniert ein bisschen, außer dass es für 6 Nummern Stunden dauern kann. Allerdings habe ich es an 3 Nummern getestet und es funktioniert einwandfrei!

ErnWong
quelle
7

Obwohl ich diesen Java- Code nicht würdigen kann, ist Smoothsort ein gutes Beispiel für den Kompromiss zwischen Lesbarkeit und Leistung:

static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,
  177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,
  35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,
  1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,
  48315633, 78176337, 126491971, 204668309, 331160281, 535828591,
  866988873 // the next number is > 31 bits.
};

public static <C extends Comparable<? super C>> void sort(C[] m,
    int lo, int hi) {
  int head = lo; // the offset of the first element of the prefix into m

  int p = 1; // the bitmap of the current standard concatenation >> pshift
  int pshift = 1;

  while (head < hi) {
    if ((p & 3) == 3) {
      sift(m, pshift, head);
      p >>>= 2;
      pshift += 2;
    } else {
      // adding a new block of length 1
      if (LP[pshift - 1] >= hi - head) {
        // this block is its final size.
        trinkle(m, p, pshift, head, false);
      } else {
        // this block will get merged. Just make it trusty.
        sift(m, pshift, head);
      }

      if (pshift == 1) {
        // LP[1] is being used, so we add use LP[0]
        p <<= 1;
        pshift--;
      } else {
        // shift out to position 1, add LP[1]
        p <<= (pshift - 1);
        pshift = 1;
      }
    }
    p |= 1;
    head++;
  }

  trinkle(m, p, pshift, head, false);

  while (pshift != 1 || p != 1) {
    if (pshift <= 1) {
      // block of length 1. No fiddling needed
      int trail = Integer.numberOfTrailingZeros(p & ~1);
      p >>>= trail;
      pshift += trail;
    } else {
      p <<= 2;
      p ^= 7;
      pshift -= 2;

      trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);
      trinkle(m, p, pshift, head - 1, true);
    }

    head--;
  }
}

private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,
    int head) {   
  C val = m[head];

  while (pshift > 1) {
    int rt = head - 1;
    int lf = head - 1 - LP[pshift - 2];

    if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)
      break;
    if (m[lf].compareTo(m[rt]) >= 0) {
      m[head] = m[lf];
      head = lf;
      pshift -= 1;
    } else {
      m[head] = m[rt];
      head = rt;
      pshift -= 2;
    }
  }  

  m[head] = val;
}

private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,
    int pshift, int head, boolean isTrusty) {

  C val = m[head];

  while (p != 1) {
    int stepson = head - LP[pshift];

    if (m[stepson].compareTo(val) <= 0)
      break; // current node is greater than head. Sift.

    if (!isTrusty && pshift > 1) {
      int rt = head - 1;
      int lf = head - 1 - LP[pshift - 2];
      if (m[rt].compareTo(m[stepson]) >= 0
          || m[lf].compareTo(m[stepson]) >= 0)
        break;
    }

    m[head] = m[stepson];

    head = stepson;
    int trail = Integer.numberOfTrailingZeros(p & ~1);
    p >>>= trail;
    pshift += trail;
    isTrusty = false;
  }

  if (!isTrusty) {
    m[head] = val;
    sift(m, pshift, head);
  }
}

/* insert some basic static void main here... 
   my Java's too rusty to do it from the top of my head 
*/

(Hinweis: Einige Kommentare wurden entfernt, um den Effekt zu verbessern und ihn zu verkürzen. Quelle stammt von der oben verlinkten Wikipedia-Seite.)

Jimmy
quelle
Könnten Sie bitte die Sprache, die Sie für diesen Beitrag verwendet haben, hinzufügen?
Nathan Osman
„Kompromiss zwischen Lesbarkeit und Leistung“ - das muss ich mir merken.
FUZxxl
7

Das F # "Ich hasse funktionale Programmierung":

let numbers = System.Console.ReadLine().Split(',')
let mutable check = 0
let mutable sorted = ""

while not (sorted.Split(',').Length = numbers.Length) do
    for i in [check..check + 1000] do
        for number in numbers do
            if number = i.ToString() then
                if sorted.Length > 0 then
                    sorted <- sorted + "," 
                sorted <- sorted + number
    check <- check + 1000

printfn "%s" sorted
Mongus Pong
quelle
7

Ruby Metasort

#I know Ruby has a built-in method to order an array,
#but I can't remember what it is.  Oh well, metaprogramming to the rescue!
#I'll just try all of the available methods, and see which one works.

#check whether an array is ordered
def is_in_order? arr
  arr.is_a?(Array) && (0...(arr.size-1)).all? {|i| arr[i]<arr[i+1]}
end

Array.instance_methods.each do |meth|
  begin
    possibly_ordered_array = ARGV.map(&:to_i).send(meth)
    #have to check both that the new array is ordered, and that it's still the same size,
    #so that methods that change the array's elements don't create false positives.
    if is_in_order?(possibly_ordered_array) && possibly_ordered_array.size == ARGV.size
      puts possibly_ordered_array.join(", ")
      exit 0 #success!
    end
  rescue
    #method needed an argument or something
  end
end

exit 1 #could not order the array
Histokrat
quelle
6

Ein Cobol-Unterprogramm zum Sortieren einer Tabelle mit ganzen Zahlen, die garantiert eine höhere WTF / Minute als jede andere Sprache haben. Zu Leistungszwecken wird der QuickSort-Algorithmus verwendet:

Identification Division.                                        
Program-ID. QwikSort is recursive.                              
Environment Division.                                           
Data Division.                                                  
Working-Storage Section.                                        
01 QwikSort-Working-Storage.                                    
 05 Swap-Space           Pic X(80) Value spaces.               
 05 Pivot         Binary Pic S9(8).                            
 05 I             Binary Pic S9(8).                            

Local-Storage Section.                                          
01 QwikSort-Local-Storage.                                      
 05 Lo            Binary Pic S9(8) Value 0.                    
 05 Hi            Binary Pic S9(8) Value 0.                    

Linkage Section.                                                

01 The-Table-Area.                                              
 05 The-Table     occurs 0 to 200000 depending on High-Element.
  10 The-Key     Binary Pic S9(8).                            

01 Low-Element     Binary Pic S9(8).                            
01 High-Element    Binary Pic S9(8).                            

Procedure Division using The-Table-Area                         
                         Low-Element                            
                         High-Element.                          

  Compute Lo  = Low-Element                                   
  Compute Hi  = High-Element                                  

  If ( High-Element > Low-Element )                           
     Perform Select-Pivot          

* ----- Loop through table until indices cross                   
       Perform until Hi < Lo                                    

* -------- Locate an item that should not be in less partition    
          Perform varying Lo from Lo by 1                        
            until (( Lo >= High-Element )                        
               or  ( The-Key of The-Table ( Lo ) >= Pivot ))     
          End-Perform                                            


* -------- Locate an item that should not be in greater partition 
          Perform varying Hi from Hi by -1                       
            until (( Hi <= Low-Element )                         
               or  ( The-Key of The-Table ( Hi ) <= Pivot ))     
          End-Perform                                            

* -------- Exchange the two and keep looking                      
          If ( Lo <= Hi )                                        
             Perform Swap-Elements                               
             Compute Lo = Lo + 1                                 
             Compute Hi = Hi - 1                                 
          End-If                                                 

    End-Perform                                               

    Perform Qsort-Less-Partition                              

    Perform Qsort-Greater-Partition                           

 End-If                                                       

 Goback.                                                      

*--------------------------------------------------------------*  
* Select the pivot using median of three rule.                    
*--------------------------------------------------------------*  
 Select-Pivot.                                                    

    Compute Pivot = ( Lo + Hi ) / 2                              
    Compute Pivot = Function Median (                            
            The-Key of The-Table ( Lo )                          
            The-Key of The-Table ( Pivot )                       
            The-Key of The-Table ( Hi )                          
         )                                                       
    End-Compute                                                  

    Exit.                                                        

*--------------------------------------------------------------*  
* Exchange elements in the wrong partition                        
*--------------------------------------------------------------*  
 Swap-Elements.                                                   
    Move The-Table ( Lo ) to Swap-Space                          
    Move The-Table ( Hi ) to The-Table ( Lo )                    
    Move Swap-Space       to The-Table ( Hi )                    
    Exit.                   

*--------------------------------------------------------------*  
* Sort the less sub-partition                                     
*  -- Optimization opportunity for the user: if the partition     
*    size is sufficiently small you might want to apply a simple  
*    sort like insertion or bubble, or perhaps a bose-nelson      
*    network to order the last few and save the overhead of       
*    another recursive call.                                      
*--------------------------------------------------------------*  
 Qsort-Less-Partition.                                            
    If ( Low-Element < Hi )                                      
       Call 'QwikSort' Using                                     
          The-Table-Area                                         
          Low-Element                                            
          Hi                                                     
       End-Call                                                  
    End-If 
    Exit.                                                        

*--------------------------------------------------------------*  
* Sort the greater sub-partition                                  
*  -- Optimization opportunity for the user: same as left part.   
*--------------------------------------------------------------*  
 Qsort-Greater-Partition.                                         
    If ( Lo < High-Element )                                     
       Call 'QwikSort' Using                                     
          The-Table-Area                                         
          Lo                                                     
          High-Element                                           
       End-Call                                                  
    End-If                              
    Exit.                                                        

 End Program QwikSort.
Joe Zitzelberger
quelle
Gibt es einen Grund, warum es QwikSortstattdessen ist QuickSort? (zB Längenbeschränkung oder du kannst den Buchstaben u nicht in einem Namen verwenden?) Weil das noch mehr Spaß machen würde: P
Marinus
@marinus Es ist wahrscheinlich eine Linker-Einschränkung.
Craig Trader
Nicht genug Großbuchstaben später
Xavier Combelle
Es ist "QwikSort" anstelle von "QuickSort", um der Beschränkung der Länge von acht Zeichen zu entsprechen, die ältere Betriebssysteme auferlegen. "QwikSort" passt gut in eine MVS-PDS oder auf eine alte DOS-Maschine.
Joe Zitzelberger
Der Großbuchstabe wird nicht benötigt, Cobol macht Kleinbuchstaben ganz gut, ich gehe gerne bowlen, aber seien wir
ehrlich
4
var inp = [1, 4, 7, 2, 5],
    loops = 0,
    trysort;

while(++loops) {
    trysort = new Array(inp.length);

    for(var i = 0, len = inp.length; i < len; i++) {
        trysort[i] = inp[~~(Math.random()*inp.length)];
    }

    if( trysort.join(',') === '1,2,4,5,7' )
        break;
}
alert('done! Only ' + loops + ' iterations! ' + trysort);

http://www.jsfiddle.net/sAFMC/

Andy
quelle
hart im Array tut tut codiert.
Raynos
Bogosort für den Sieg! \ o /
Chris Jester-Young
nett. ich mag das.
Vaibhav
4

Python-Quicksort mit Lambda

Etwas, das ich in meinem Blog geschrieben habe:

qsort = lambda seq: [] if not seq else qsort(filter(lambda n: n<=seq[0], seq[1:]))+[seq[0]]+qsort(filter(lambda n: n>seq[0], seq[1:]))

Hier ist der aktuelle Blogbeitrag

MrD
quelle
1
Schöne lösung! Der kürzeste bekannte QuickSort in Python ist nur 79 Byte lang (der legendäre kortesische Codegolfer Mark Byers): news.e-scribe.com/314#581
Hallvabo
Das ist eine sehr esoterische Lösung. Hat meinen Horizont erweitert!
MrD
4

Rubin

#get user input from standard input and store it in a variable
var = gets
#make user input into a ruby array in a string
array_string = '[' + var + ']'
#evaluate this ruby array and store the array in a variable
array = eval(array_string)
#convert from strings to integers
#initialize loop variable as 0
i = 0
#loop until the loop variable is no longer small enough
#to be a valid index of the array
until !(i < array.length)
    #convert to a number then ensure it is an integer
    array[i] = array[i].to_f.floor
    #increment i
    i = i + 1
end

sorted = false

#infinite loop
while true
    #if it hasn't been sorted
    if ((!sorted) == true)
        #try to sort it
        #initialize loop variable as 0
        j = 0
        #loop while i is less than or equal to the length of the array
        while (i <= array.length)
            random = rand # get a random number
            #this gets a zero or one
            random = (random + random.round).floor
            #turn random into a boolean
            if random == 0
                random = true
            end
            if random == 1
                random = false
            end
            #don't do anything if this is the last one
            if j == (array.length - 1)
                #do nothing
            else
                if random == true
                    #true means keep these 2 elements in the same order
                end
                if random == false
                    #false means swap with next element
                    #initialize a variable to store the current element
                    swapvar = array[j]
                    #initialize a variable to store the next element
                    swapvar2 = array[j+1]
                    #set the current element to what was the next element
                    array[j] = swapvar2
                    #set the next element to what was in this one
                    array[j+1] = swapvar
                end
            end
            #increment j
            j = j + 1
            #loop kept looping, fixed now
            if j >= array.length
                break
            end
        end
        #now test if it is sorted
        #lets say it is
        sorted = true
        #now see if we are wrong
        #initialise a loop variable to zero
        k = 0
        while (array.length > k)
            #get current value from array and store it in a variable
            current = array[k]
            #get current value from array and store it in a variable
            next_ = array[k + 1]
            if !(array[k +1].nil? == true)#stop errors
                #if sorted correctly
                if next_ < current || next_ == current
                    #sorted stil== true
                else
                    sorted = false #not sorted, try again
                end
            end
            #increment loop variable
            k = k + 1
        end
            #DEBUG
        #p array
    else
        break #break out of infinite loop
    end
end


#it is now sorted in descending order
#we want ascending so lets flip it

#initialise a loop variable to zero
l = 0

final_array = Array.new([])

while (l <= (array.length - 1))
    final_array[array.length - l - 1] = array[l]
    #increment loop variable
    l += 1
end

#now we need to make it into a string
str = ''

#first map each element to a string
#to do this lets extend Array, then use this for our array
class Array
    def map #map each element to a string
        #initialise a loop variable to zero
        @m = 0
        arr = []
        while @m < self.length
            arr += [self[@m].to_s]
            #increment loop variable
            @m = @m + 1
        end
        return arr
    end
end

final_array = Array.new(final_array).map()
#DEBUG
#p final_array

#now add the elements to a string, separated by commas and spaces
#initialise a loop variable to zero
n = 0

while n < array.length
    #increment loop variable
    #add item to string
    str = str + final_array[n]
    #if not last item
    if !((array.length - 1 )== n)
        #add comma
        str += ','
    end
    #if not last item
    if !((array.length - 1 )== n)
        #add space
        str += ' '
    end
    n = n + 1
end

#now print the string
puts str
david4dev
quelle
3

C ++ (4409)

#include <iostream>
#include <cstdlib>
#include <cctype>
#include <string>
#include <sstream>


std::string itostr(int number)
{
   std::stringstream ss;
   ss << number;
   return(ss.str());
}


class CStackLIFO
{
private:
    int* stack;
    size_t len;
public:
    CStackLIFO();
    CStackLIFO(int);
    ~CStackLIFO();
    void init();
    void init(int);
    void push(int);
    int pop();
    int pop(int&);
    void destroy(size_t);
    int get(size_t);
    size_t get_len();
};


void CStackLIFO::init()
{
    len = 0;
    stack = NULL;
}


void CStackLIFO::init(int val)
{
    len = 1;
    stack = new int[len];
    stack[0] = val;
}


CStackLIFO::CStackLIFO()
{
    init();
}


CStackLIFO::CStackLIFO(int val)
{
    init(val);
}


CStackLIFO::~CStackLIFO()
{
    len = 0;
    delete[] stack;
    stack = NULL;
}


void CStackLIFO::push(int val = NULL)
{
    if((stack == NULL) || (len == 0))
    {
        this->init(val);
    }
    else
    {
        int* buf = stack;
        len++;
        stack = new int [len];

        for(size_t i = 0; i < (len - 1); i++)
        {
            stack[i] = buf[i];
        }

        stack[len - 1] = val;
        delete[] buf;
    }
}


int CStackLIFO::pop()
{
    int val;
    int* buf = stack;
    len--;
    stack = new int [len];

    for(size_t i = 0; i < len; i++)
    {
        stack[i] = buf[i];
    }

    val = buf[len];
    delete[] buf;

    return(val);
}


int CStackLIFO::pop(int &out)
{
    if(len <= 0)
        return(false);

    int* buf = stack;
    len--;
    stack = new int [len];

    for(size_t i = 0; i < len; i++)
    {
        stack[i] = buf[i];
    }

    out = buf[len];
    delete[] buf;

    return(true);
}


void CStackLIFO::destroy(size_t idx)
{
    int* buf = stack;
    len--;
    stack = new int [len];
    for(size_t i = 0; i < idx; i++)
    {
        stack[i] = buf[i];
    }
    for(size_t i = idx; i < len; i++)
    {
        stack[i] = buf[i + 1];
    }
    delete[] buf;
}


int CStackLIFO::get(size_t idx)
{
    return(stack[idx]);
}


size_t CStackLIFO::get_len()
{
    return(len);
}


class CSort
{
private:
    void removeWhitespace();
public:
    std::string in;
    void sort();
    void display();
};


void CSort::display()
{
    std::cout << in << std::endl;
    return;
}


void CSort::removeWhitespace()
{
    for(size_t i = 0; i < in.size(); i++)
    {
        if(in[i] == ' ')
        {
            in = in.substr(0, i) + in.substr(i+1);
        }
    }
}


void CSort::sort()
{
    removeWhitespace();

    CStackLIFO nums;
    CStackLIFO s;

    // build stack
    for(size_t i = 0, offset = 0; i < in.size(); i++)
    {
        for(offset = 0; (i + offset) < in.size(); offset++)
        {
            if(!(isdigit(in[i + offset]) ||
                 (in[i + offset] == '-')))
                break;
        }

        if(offset > 0)
        {
            nums.push(atoi(in.substr(i, offset).c_str()));
        }

        i += offset;
    }

    // sort
    for(size_t lowest = 0; 0 < nums.get_len(); lowest = 0)
    {
        for(size_t i = 0; i < nums.get_len(); i++)
        {
            if(nums.get(i) < nums.get(lowest))
                lowest = i;
        }

        s.push(nums.get(lowest));
        nums.destroy(lowest);
    }    

    // convert to string
    in = "";
    for(size_t i = 0; i < s.get_len(); i++)
    {
        // Convert num to string
        in += itostr(s.get(i));
        in += ", ";
    }
    if(in.size() > 2)
        in = in.substr(0, in.size() - 2);
}


int main(int argc, char* argv[])
{
    while(1)
    {
        CSort unsorted;
        unsorted.in = "";

        while(1)
        {
            std::string userin = "";
            std::cin >> userin;

            if(userin.compare("end") == 0)
                break;

            unsorted.in += userin + ", ";
        }

        unsorted.in = unsorted.in.substr(0, unsorted.in.size() - 2);

        CSort sorted;
        sorted.in = unsorted.in;
        sorted.sort();

        std::cout << "Input:" << std::endl;
        unsorted.display();
        std::cout << "Output:" << std::endl;
        sorted.display();
    }

    return(0);
}

Einige "schlechte" Dinge an diesem Programm:

  • Wirklich fädelig. :) Ich hätte einfach die Zahlen direkt eingeben können, anstatt die Zeichenfolge nach Zahlen zu durchsuchen.

  • Verwendet übermäßige Klassen. Ich hätte auch die eingebauten verwenden können, aber ein schlechter Codierer würde das Rad einfach neu erfinden.

  • Die Schleife für die Sortierung ist schrecklich ineffizient. Ich denke, es ist der langsamste Weg, ohne dass es so aussieht, als hätte ich versucht, es langsam zu machen. Tatsächlich entspricht der eigentliche "Sortier" -Teil des Codes nur 11 Zeilen, einschließlich der geschweiften Klammern und Zeilenumbrüche.

Mateen Ulhaq
quelle
3

Dieser ist O (n * n!)

from itertools import permutations, izip, islice
L=[10,9,8,7,6,5,4,3,2,1]
for l in permutations(L):
    if all([i<j for i,j in izip(L, islice(L,1,None))]):
        break
print l

Es durchläuft alle Permutationen der Liste und prüft, ob sie sortiert sind. Es ist so schrecklich, dass das Sortieren von nur 10 Artikeln 17 Sekunden dauert

$ time python badsort.py 
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

real    0m17.563s
user    0m17.537s
sys     0m0.020s
Knabberzeug
quelle
3

T-SQL

(SQL Server 2008 R2)

Natürlich verwenden Sie bei T-SQL "ORDER BY" zum Sortieren. Duhhh.

DECLARE @LISTIN NVARCHAR(MAX);
SELECT @LISTIN = N'1, 4, 7, 2, 5'; --Input list goes here.
DECLARE @LISTINDEX BIGINT;
SELECT @LISTINDEX = 0;
DECLARE @CHARS NVARCHAR(MAX);
SELECT @CHARS = N'';
DECLARE @LISTOUT NVARCHAR(MAX);
SELECT @LISTOUT = N'';
DECLARE @ORDERBY TABLE (NUMBER NVARCHAR(MAX));
WHILE @LISTINDEX < LEN(@LISTIN) BEGIN;
SELECT @LISTINDEX = @LISTINDEX + 1;
SELECT @CHARS = @CHARS + SUBSTRING(@LISTIN, @LISTINDEX, 1);
IF PATINDEX(N'%, ', @CHARS) > 0 BEGIN;
INSERT INTO @ORDERBY (NUMBER) VALUES (REPLACE(@CHARS, N', ', N''));
SELECT @CHARS = N'';
END;
IF @LISTINDEX = LEN(@LISTIN) BEGIN;
INSERT INTO @ORDERBY (NUMBER) VALUES (@CHARS);
END;
END;
DECLARE ORDERBY CURSOR FOR SELECT NUMBER FROM @ORDERBY ORDER BY CONVERT(DECIMAL, NUMBER);
OPEN ORDERBY;
FETCH NEXT FROM ORDERBY INTO @CHARS;
WHILE @@FETCH_STATUS = 0 BEGIN;
SELECT @LISTOUT = @LISTOUT + @CHARS + N', ';
FETCH NEXT FROM ORDERBY INTO @CHARS;
END;
CLOSE ORDERBY;
DEALLOCATE ORDERBY;
IF @LISTOUT = N'' SELECT @LISTOUT;
ELSE SELECT SUBSTRING(@LISTOUT, 1, LEN(@LISTOUT) - 1);

Siehe "BESTELLEN NACH"? Es ist genau dort in der Cursor-Deklaration.

Muqo
quelle
2

Python- Implementierung von Funnel Sort . Dieser Algorithmus kann bei richtiger Implementierung tatsächlich eine gute Cache-Leistung aufweisen, was in diesem Fall mit Sicherheit nicht der Fall ist (er sortiert jedoch korrekt).

class Funnel(object):
  """ In place funnel sorting algorithm. """
  def __init__(self, left_child, right_child):
    self.left_child = left_child
    self.right_child = right_child
    self.lookahead = (False, -1)

  def get_next(self):
    if self.left_child.has_next() and self.right_child.has_next():
      l, r = self.left_child.get_next(), self.right_child.get_next()
      if l < r:
        self.right_child.put_back(r)
        return l
      else:
        self.left_child.put_back(l)
        return r
    elif self.left_child.has_next():
      return self.left_child.get_next()
    elif self.right_child.has_next():
      return self.right_child.get_next()
    else:
      raise Exception("Out of elements.")

  def has_next():
    if self.lookahead[0]: 
      self.lookahead = (False, self.lookahead[1])
      return self.lookahead[1]
    return self.left_child.has_next() or self.right_child.has_next()

  def put_back(self, item):
    self.lookahead = (True, item)

class Funnel_Base(Funnel):
  def __init__(self, buffer):
    self.buf = buffer
    self.lookahead = (False, -1)

  def get_next(self):
    if self.lookahead[0]:
      self.lookahead = (False, self.lookahead[1])
      return self.lookahead[1]
    return self.buf.pop(0)

  def has_next():
    return len(self.buf) > 0

def make_funnel(funnels):
  while len(funnels) > 1: funnels.append(Funnel(funnels.pop(0), funnels.pop(0)))
  return funnels[0]

def insertion_sort(array):
  def swap(i, j):
    t = array[i]
    array[i] = array[j]
    array[j] = t
  for i in xrange(1,len(array)):
    while i > 0 and  array[i] < array[i-1]:
      swap(i, i-1)
      i -= 1

def funnel_sort_internal(array):
  if len(array) < 100:
    # sort subsections with insertion sort and make base funnels
    insertion_sort(array)
    return Funnel_Base(array)
  else:
    K = int(len(array)**(1.0/3))
    new_funnels = [funnel_sort_internal(array[base:min(base+K, len(array))])
                   for base in xrange(0, len(array), K)]
    return make_funnel(funnels)

def funnel_sort(array):
  cp = array[:]
  srtd = funnel_sort_internal(cp)
  for i in xrange(len(array)): array[i] = cp[i]
Hoa Long Tam
quelle
2

Sortiert eine Liste von 32-Bit-Ganzzahlen. Für die meisten normalen Fälle ist es tatsächlich recht effizient:

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

static unsigned char *bmp[131072];
static size_t total, printed;

static void set(int n);
static void print_page(unsigned char *page, int offset);
static void print_number(int n);

int main(void)
{
    int i, n;

    assert(INT_MIN == -2147483647 - 1 && INT_MAX == 2147483647);

    while (scanf("%d,*", &n) > 0) {
        set(n);
        total++;
    }

    for (i = 0; i < 131072; i++)
        if (bmp[i] != NULL)
            print_page(bmp[i], INT_MIN + i * 32768);
    putchar('\n');

    return 0;
}

static void set(int n)
{
    unsigned int i = n - INT_MIN;

    if (bmp[i >> 15] == NULL)
        bmp[i >> 15] = calloc(4096, sizeof(unsigned char));

    bmp[i >> 15][(i >> 3) & 4095] |= (unsigned int)1 << (i & 7);
}

static void print_page(unsigned char *page, int offset)
{
    int i, j;

    for (i = 0; i < 4096; i++, offset += 8)
        if (page[i])
            for (j = 0; j < 8; j++)
                if (page[i] & (1 << j))
                    print_number(offset + j);
}

static void print_number(int n)
{
    printf("%d%s", n, ++printed < total ? ", " : "");
}

Beispiel:

$ echo '1, 4, -3, 7, -2147483648, 2147483647, 2, 5' | ./bitmap-sort
-2147483648, -3, 1, 2, 4, 5, 7, 2147483647
Joey Adams
quelle
2
<?php
    /*  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY
        EXPRESSED OR IMPLIED WARRANTIES, INCLUDING,
        BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
        OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
        PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
        REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
        INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
        CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
        TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
        LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
        INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
        LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
        OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
        IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
        ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.          */

    // Make the function
    function sort_numbers($nums) {
        // Remove duplicates from array
        array_unique($nums);
        // Filter out everything that's not a number or a numeric string
        foreach ($nums as $val) {
            if (!is_numeric($val)) {
                unset($array[$val]);
            }
        }
        // Do some random computations
        class SorterFunction {
            public $timestamp = 0;
            public $rand_num = 0;
            public function sort_a_numeric_array($num_arr) {
                // Sort the array
                sort($num_arr, SORT_NUMERIC);
                return $num_arr;
            }
            public function __construct() {
            $this->timestamp = time();
            $this->rand_num = rand() % 100000;
        }
    }
    // Create a new SorterFunction class
    $MySorterFunction = new SorterFunction();
    // Print out the sorted array's elements using var_dump
        $MySorterFunction->sort_a_numeric_array($nums);
        var_dump($nums);
    }
    $my_nums = array(1, 4, 7, 2, 5);
    sort_numbers($my_nums);
?>
nyuszika7h
quelle
Das wird nicht einmal funktionieren, da es sort()nach Referenz arbeitet und nicht einmal etwas
zurückgibt
@ircmaxell: Behoben, danke.
nyuszika7h
Seufzer. (obwohl es ein wtf ist, so zählt es technisch). Aber es funktioniert immer noch nicht (falsche
Sortieränderung
1
+1 für die Lizenz, aber es könnte mehr Zeilen abgedeckt haben.
1
@Tim Siehe das Update. ;)
nyuszika7h
2

C ++ , nicht sicher, ob es Namen für diese Art gibt, aber hier geht<ducks for cover/>

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main(void)
{
  std::istream_iterator<int> in(std::cin), end;
  std::vector<int> input(in, end);

  std::cout << "sorting.." << std::endl;
  std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;

  // this is the smart bit.. ;)
  while (std::next_permutation (input.begin(), input.end()));

  std::cout << "sorted.." << std::endl;
  std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;

  return 0;
}
Nim
quelle
Es ähnelt BogoSort, mit dem Unterschied, dass Ihre Worst-Case-Komplexität die durchschnittliche Case-Komplexität von Bogosort ist.
Saeedn
2

Eine Unternehmenslösung (im Pseudocode):

create sql connection
create temporary table: one autoincrementing ID field and one value field
convert array into xml
post xml to sql database
use stored procedure to create records from xml
run sql command "select * from temptable sort by value"
iterate records, adding to array
drop temporary table
close connection
Skizz
quelle
2

In Ruby eine visuelle Darstellung eines " Spaghetti-Sortierung" , die in einem Terminal mit 80 Spalten ausgeführt werden soll:

$CONSOLE_WIDTH = 78
def sort a
  factor = $CONSOLE_WIDTH.to_f/a.max
  puts "Strands:"
  puts (strands=a.map{|v|['-'*(v*factor).to_i,v*factor]}).map{|s|s.first}
  results=[];
  len=0
  n = 1
  until strands.empty? do
   #puts "\nITERATION #{n}\n\n"
    n+=1
    $CONSOLE_WIDTH.downto(0) do |i|
      len = i
      contacts = strands.find_all{|s|s.first[i]!=nil}
      break unless contacts.empty?
    end
    puts "\nResults:"
    puts results.map{|s|s.first}
    puts "\nStrands:"
    puts strands.map{|s|s.first.ljust(len+1)+"|"}
    longest = strands.sort_by{|s|s.last}.max
    strands.delete_at strands.index(longest)
    results << longest
  end
  puts "\nResults:"
  puts results.map{|s|s.first}
  return results.map{|s|s.last/factor}

end

Verwendung: p sort (1..10).map{rand(100)}

Ahelly
quelle
2

PL \ SQL - 109 Zeilen

Dies ist eine Antwort auf den Kommentar von @ eBusiness in der Antwort von @ steenslag. Es dient keinem nützlichen Zweck.

Es hat 4 Stufen:

  1. Nehmen Sie eine durch Kommas getrennte Liste von Zahlen und berechnen Sie, wie viele Kommas darin enthalten sind.
  2. Verwenden Sie die Anzahl der Kommas, um die Zeichenfolge basierend auf den Kommas zu teilen.
  3. Durchlaufen Sie die bekannte Anzahl von Werten und suchen Sie jedes Mal den Mindestwert. Löschen Sie dabei das vorherige Minimum.
  4. Gib sie aus.

 create or replace procedure sort ( Plist_of_numbers varchar2 ) is

   type t_num_array is table of number index by binary_integer;

   t_sorted t_num_array;
   t_unsorted t_num_array;

   i binary_integer := 0;
   -- Can you tell this one was an afterthought?
   x binary_integer := 0;

   no_of_commas integer := 0;

   v_list_of_numbers varchar2(32000);
   v_min_value number;
   v_min_index binary_integer;

begin

   -- Best to be overly careful about these things.
   if trim(Plist_of_numbers) is null then
      raise_application_error(-20000,'You need to give me something to work with.');
   end if;

   -- Firstly we have to make sure that there is a trailing comma
   -- in Plist_of_numbers for this to work.
   if substr(Plist_of_numbers,-1) = ',' then
      v_list_of_numbers := Plist_of_numbers;
   else
      v_list_of_numbers := Plist_of_numbers || ',';
   end if;


   /* SQL ( being SQL ) we had to pass in a string of numbers
      because we'd need to create a type outside the function which
      wouldn-t really be in the spirit of things so, let's unpack
      our string. In order to do this ( bowling ) we need to know how
      many commas are in our sting.
   */

   for j in 1 .. length(v_list_of_numbers) loop

      if substr(v_list_of_numbers,j,1) = ',' then
         no_of_commas := no_of_commas + 1;
      end if;

   end loop;


   -- Next we unpack our list into t_unsorted;
   for j in 1 .. ( no_of_commas - 1 ) loop

      i := i + 1;
      t_unsorted(i) := to_number( substr( v_list_of_numbers
                                        , instr(v_list_of_numbers, ',', 1, j)
                                        , instr(v_list_of_numbers, ',', 1, j + 1)
                                           )
                                  );

   end loop;


   -- Next the actual sorting.
   -- Loop through the known number of elements in the array.
   for j in 1 .. i loop

      -- Then the array each time to find the minimum.
      -- As we-re deleting stuff in the middle here we have to be careful;
      k := t_unsorted.first;
      v_min_value := null;

      while k < t_unsorted.last loop

         if v_min_value is null then 
            v_min_value := t_unsorted(k);
            v_min_index := k;
         elsif t_unsorted(k) < v_min_value then
            v_min_value := t_unsorted(k);
            v_min_index := k;
         end if;

         k := t_unsorted.next;

      end loop;

      -- Now we-ve found the next minimum value put it into the 
      -- t_sorted array
      x := x + 1;          
      t_sorted(x) := v_min_value;
      -- and delete our min value from the unsorted array.
      t_unsorted.delete(v_min_index);

   end loop;


   -- Lastly show that everything worked.
   for j in 1 .. x loop

      dbms_output.put_line( t_sorted(j) );

      -- it-s also nice to show the wider world what-s happening 
      -- but let-s not do it too often, server load etc.
      if mod(j,10) = 0 then
          dbms_application_info.set_module('finding min', 'total: ' || j );
      end if;

   end loop;

end sort;

Wie Sie sehen, ist es lächerlich ... Schlechte Dinge sind:

  • Dies in SQL tun

Das wars eigentlich schon, es sollte extrem schnell gehen.

Ben
quelle
2

Sowohl die Wahl der Sprache als auch der Algorithmus müssen erklärt werden.

Dieser Algorithmus wird als langsame Sortierung bezeichnet. Ich habe vor, den Mist aus Bogosort herauszuschlagen (teste zufällige Permutationen, bis sie sortiert sind), weil die Implementierung zwar algorithmisch schrecklich ineffizient ist, aber zu einfach ist und man ihre Langsamkeit nicht garantieren kann.

Ich codiere langsame Sortierung in Scheme, weil das Hauptziel von Scheme darin besteht, einfach zu sein, was dies zu einer größeren Herausforderung macht. Ein interessantes Merkmal von Scheme ist die unschlagbare Erweiterbarkeit. Tatsächlich werden Implementierungen der Sprache häufig (häufig vollständig) in Schema selbst implementiert. Noch besser: Sie benötigen lediglich Abstraktionen (Lambdas) und Anwendungen. Anwendungen werden in Präfixnotation ausgewertet:

(function arg1 arg2 ...)

... ist nur syntaktischer Zucker für:

(apply function (list arg1 arg2 ...))

... das eine Funktion auf Listen von Argumenten anwendet.

Um aus diesem Code-Bowling einen Strich zu machen, muss ich die Max-Funktion neu definieren, um die Liste rekursiv zu teilen, bis sie sich selbst vergleichen kann. Die min-Funktion wird auch rekursiv unter Verwendung von max neu definiert, indem alle Maxima entfernt werden, bis eine Zahl übrig bleibt. Schließlich wird die Sortierung neu definiert, indem die Minima nacheinander angehängt werden.

Langsame Sortierung basiert auf "Multiplizieren und Ergeben" im Gegensatz zu "Teilen und Erobern". Es funktioniert, indem rekursiv die Maxima herausgezogen werden, bis das Minimum übrig bleibt, jedes Mal das resultierende Minimum an die Lösung angehängt wird und erneut gestartet wird, bis alle Minima der Reihe nach angehängt wurden. Obwohl meine Implementierung völlig ineffizient ist, verwendet sie die Berechnungen so oft wie möglich erneut, weil: 1) Sie für den Algorithmus benötigt werden 2) Sie möchten möglicherweise, dass diese Art eines Tages endet ...

(define sort
  (lambda ns
    (define max
      (lambda (ns)
        (let ([len (length ns)])
          (case len
            [(2) (receive (a b) (car+cdr ns)
                   (if (> a b) a b))]
            [(1) (car ns)]
            [else (receive (a b)
                    (split-at ns
                      (floor (/ len 2)))
                    (let ([ma (max a)]
                          [mb (max b)])
                      (if (> ma mb) ma mb)))]))))
    (define min
      (lambda (ns)
        (if (null? (cdr ns)) (car ns)
            (min (remove ns (max ns))))))
    (if (every number? ns)
        (let sort ([ns ns] [sorted (list)])
          (if (null? ns) sorted
              (let ([m (min ns)])
                (sort (remove ns m)
                  (append ns m)))))
    (error "These are not all numbers: " ns))))
Samuel Duclos
quelle
1

Java übertriebenes Chaos / Schweregefühl

Das hat Spaß gemacht! Es fühlt sich komisch an, so etwas zu posten.

import java.util.LinkedList;

public class WTF {

    // XXX We all know linkedlists are awesome for random access!
    public static LinkedList<Integer> sort(LinkedList<Integer> array) {
        // XXX Instead of sorting in place, we create another array entirely!
        LinkedList<Integer> result = new LinkedList<Integer>();

        // while array is not all null
        // XXX No comments!
        boolean arrayAllNull = true;
        for (int a = 0; a < array.size(); a = a + 1) {
            if (array.get(a) != null) {
                arrayAllNull = false;
            }
        }

        while (arrayAllNull != true) {

            // XXX We could use Integer.MAX_VALUE, but lets assumes something instead
            Integer i = 999999999;
            // find lowest
            for (int a = 0; a < array.size(); a = a + 1) {
                if (array.get(a) != null) {
                    if (array.get(a) < i) {
                        i = array.get(a);
                    }
                }
            }

            // replace lowest by null
            // XXX Yup, another loop! :)
            // XXX We're breaking the original array, but don't tell anyone.
            for (int a = 0; a < array.size(); a = a + 1) {
                if (array.get(a) != null) {
                    if (array.get(a) == i) {
                        array.set(a, null);
                    }
                }
            }

            result.add(i);

            // XXX Lets repeat that test once again, functions are bad.
            arrayAllNull = true;
            for (int a = 0; a < array.size(); a = a + 1) {
                if (array.get(a) != null) {
                    arrayAllNull = false;
                }
            }

        }

        return result;
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{1, 4, 7, 2, 5};
        LinkedList<Integer> nums = new LinkedList<Integer>();
        for (int i : numbers)
            nums.add(i);
        System.out.println(sort(nums));
    }

}
Joanis
quelle
1

Python

Funktioniert nur, wenn alle Artikel weniger als 9e99 sind :)

>>> L=[10,9,8,7,6,5,4,3,2,1]
>>> 
>>> print [[min(L),L.__setitem__(L.index(min(L)),9e99)][0] for i in L]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Extrahieren Sie jedes Mal durch die Schleife das kleinste Element und ersetzen Sie es durch 9e99

Knabberzeug
quelle
1

Python (634)

Wenn die Liste sortiert ist, drucken Sie sie aus. Tauschen Sie andernfalls zwei Elemente in der falschen Reihenfolge aus und generieren Sie ein Python-Skript, das die neue Reihenfolge verarbeitet. Löschen Sie anschließend das erstellte Skript.

list_to_sort = input()
n = 0
n += 1
import sys, os
for i in range(len(list_to_sort)-1):
    if list_to_sort[i]>list_to_sort[i+1]:
        (list_to_sort[i],list_to_sort[i+1]) = (list_to_sort[i+1],list_to_sort[i])
        source_file = open(sys.argv[0],'r')
        temp_filename = 'temp'+repr(n)+'.py'
        temp_file = open(temp_filename,'w')
        temp_file.write('list_to_sort = ' + repr(list_to_sort) + '\n')
        temp_file.write('n = ' + repr(n) + '\n')
        for line in source_file.readlines()[2:]:
            temp_file.write(line)
        source_file.close()
        temp_file.close()
        os.system('python ' + temp_filename)
        os.remove(temp_filename)
        sys.exit(0)
print list_to_sort
Pappschachtel
quelle
1

Bogobogosort in Python

import random
import copy

def isSorted(list):
    newlist = copy.deepcopy(list)
    while True:
        newlist[:len(newlist)-1] = bogobogosort(newlist[:len(newlist)-1])
        if newlist[len(newlist)-2] < newlist[len(newlist)-1]:
            break
        random.shuffle(newlist)
    return newlist == list

def bogobogosort(list):
    ret = copy.deepcopy(list)
    if (len(ret) > 1):
        while not isSorted(ret):
            random.shuffle(ret)
    return ret

Von David Morgan-Mar erfundener Algorithmus.

Achtung: Versuchen Sie dies nicht mit einer Liste, die größer als 5 Elemente ist. Sogar 5 ist sehr langsam.

gereeter
quelle
1

Python

Meine Lösung. Beinhaltet eine Fehlerbehandlung und eine Funktion, mit der Leerzeichen beim Sortieren von Zahlen beibehalten werden, dh Leerzeichen bleiben erhalten. Zahlen bewegen sich.

z.B,

Please tell me your favorite list of numbers.
I'll sort them for you.  
7, 8, 6, 7, 1, 3, 5
1, 3, 5, 6, 7, 7, 8

9,  6  ,8, 43, 90, 13   , 54, 3223, 4
4,  6  ,8, 9, 13, 43   , 54, 90, 3223

Code:

#!/usr/bin/env python
import sys
import re

class SillyUserException(ValueError):
    def __init__(self, reason, input):
        self.reason = reason
        self.input = input

    def __str__(self):
        return '''
"No man is exempt from saying silly things; the mischief is to say them deliberately."
 - Michel de Montaigne, The Complete Essays
 Your offense was {}.  You should know that it's {}.
         '''.format(self.input, self.reason)

class Item(object):
    def __init__(self, number, prespace, postspace):
        self.number = number
        self.prespace = prespace
        self.postspace = postspace

    def __str__(self):
        return self.prespace + str(self.number) + self.postspace

class ListOfNumbers(object):
    def __init__(self, string):
        self.array = self.parse(string)

    def __str__(self):
        outs = ''
        for i in self.array:
            outs += '{}{}{},'.format(i.prespace, i.number, i.postspace)
        return outs[:-1]

    def parse(self, string):
        array = []

        for item in string.split(','):
            try:
                x = int(item)
            except ValueError:
                raise SillyUserException("not a number", item)

            whitespace = re.findall("\s+", item)
            pre = ''
            post = ''
            if len(whitespace) > 0:
                pre = whitespace[0]
            if len(whitespace) > 1:
                post = whitespace[-1]

            array.append(Item(x, pre, post))

        def swap(i, j):
            tmp = array[i].number
            array[i].number = array[j].number
            array[j].number = tmp

        def min(arr, offset):
            m = arr[0]
            index = 0
            for i, e in enumerate(arr):
                if e.number < m.number:
                    m = e
                    index = i
            return index + offset


        for i, x in enumerate(array):
            m = min(array[i:], i)
            if m != i:
                swap(m, i)

        return array


if __name__ == "__main__":
    sys.stdout.writelines('\n'.join([
        "Please tell me your favorite list of numbers.",
        "I'll sort them for you.  ",
        ""
    ]))

    sys.stdout.flush()

    def read_lines():
        while True:
            line = raw_input()
            yield line

    try:
        for line in read_lines():
            if not line:
                raise SillyUserException('polite to speak when asked a question.', "<nothing>")
            if line.strip() == '42':
                raise SillyUserException('the answer to life, the universe, and everything',
                    'using and overly powerful value')
            if ',' not in line:
                raise SillyUserException("not a list", line)


            print ListOfNumbers(line)

    except SillyUserException as sillyness:
        print sillyness
Räuber
quelle
1

Python 3

Dieses Programm akzeptiert eine durch Leerzeichen getrennte Liste von Zahlen in der Standardeingabe. Anschließend wird die Standardausgabe in der richtigen Reihenfolge gedruckt. Schließlich.

import base64, pickle
pickle.loads(base64.b64decode(b'gAIoY2J1aWx0aW5zCmxpc3QKcQBjYnVpbHRpbnMKbWFwCnEBY2J1aWx0aW5zCmludApjYnVpbHRpbnMKZ2V0YXR0cgpxAmNidWlsdGlucwppbnB1dAopUlgFAAAAc3BsaXSGUilShlKFUnEDaABoAWNmdW5jdG9vbHMKcGFydGlhbApxBGNvcGVyYXRvcgphZGQKY19vcGVyYXRvcgpuZWcKY2J1aWx0aW5zCm1pbgpoA4VShVKGUmgDhlKFUnEFaABoAWgCY2FzeW5jaW8KZ2V0X2V2ZW50X2xvb3AKcQYpUlgKAAAAY2FsbF9sYXRlcoZSaAVoAWgEaARjYnVpbHRpbnMKcHJpbnQKhlJoA4ZSh1KFUjFoAmgGKVJYEgAAAHJ1bl91bnRpbF9jb21wbGV0ZYZSY2FzeW5jaW8Kc2xlZXAKY19vcGVyYXRvcgphZGQKY2J1aWx0aW5zCm1heApoBYVSSwGGUoVShVIu'))

Erklärung: Das pickle-Protokoll bietet tatsächlich viel Freiheit, insbesondere die Freiheit, beliebige Objekte mit Argumenten zu importieren und aufzurufen. Die wichtigste Einschränkung besteht darin, dass die Pickle-VM keine Flusssteuerung besitzt. Daher muss jeder Code, der ausschließlich in der Pickle-VM implementiert ist, die Flusssteuerung in den Funktionen der Python-Standardbibliothek verwenden, um ähnliche Effekte zu erzielen. Diese Implementierung der Sortierung verwendet eine Coroutine-basierte Schlafsortierung, die durch liberale Anwendung von Iteratoren und Teilanwendungen erstellt wurde.

Der äquivalente Python-Code würde ungefähr so ​​lauten:

from asyncio import get_event_loop, sleep
from operator import add
from functools import partial
values = list(map(int, input().split()))
times = list(map(partial(add, -min(values)), values))
list(map(get_event_loop().call_later, times, map(partial(partial, print), values)))
get_event_loop().run_until_complete(sleep(max(times)+1))
CensoredUsername
quelle