Sortir ini, cepat!

27

Ya ... ada 59 (sekarang 60) pertanyaan yang , tetapi tidak ada quicksort sederhana.

Itu harus diperbaiki.

Bagi mereka yang tidak terbiasa dengan quicksort , ini adalah rincian, milik Wikipedia-

  1. Pilih elemen, yang disebut pivot , dari array.
  2. Susun ulang array sehingga semua elemen dengan nilai lebih kecil dari pivot datang sebelum pivot, sementara semua elemen dengan nilai lebih besar dari pivot datang setelahnya (nilai yang sama dapat terjadi dengan cara lain). Setelah partisi ini, pivot berada di posisi terakhirnya. Ini disebut operasi partisi.
  3. Secara rekursif menerapkan langkah-langkah di atas untuk sub-array elemen dengan nilai lebih kecil dan secara terpisah ke sub-array elemen dengan nilai lebih besar.

Aturan

Aturannya sederhana:

  • Terapkan quicksort numerik dalam bahasa pemrograman pilihan Anda.
  • Pivot harus dipilih secara acak atau dengan median tiga (elemen 1, terakhir, dan tengah).
  • Program Anda dapat berupa program atau fungsi yang lengkap.
  • Anda bisa mendapatkan input menggunakan STDIN, argumen baris perintah, atau parameter fungsi. Jika menggunakan input string, input dipisahkan oleh ruang.
  • Input mungkin mengandung nilai desimal dan negatif. Namun, tidak akan ada duplikat.
  • Anda dapat output ke STDOUT atau dengan kembali dari fungsi.
  • Tidak ada fungsi penyortiran bawaan (atau terkait penyortiran) atau celah standar.
  • Daftar mungkin panjangnya sewenang-wenang.

Bonus # 1: Pada daftar atau sub-daftar panjang <= 5, gunakan jenis penyisipan untuk mempercepat sedikit. Hadiah: -15%.

Bonus # 2: Jika bahasa Anda mendukung konkurensi, urutkan daftar secara paralel. Jika Anda menggunakan jenis penyisipan pada sub-daftar, jenis penyisipan akhir tidak harus paralel. Dibangun di thread pool / penjadwalan thread diizinkan. Hadiah: -15%.

Catatan: Median tiga orang membingungkan beberapa orang, jadi inilah penjelasan, milik (lagi) Wikipedia:

memilih median elemen pertama, tengah, dan terakhir dari partisi untuk pivot

Mencetak gol

Ini adalah . Skor dasar dalam byte. Jika Anda mendapat satu bonus, ambil diskon 15% dari angka itu. Jika Anda mendapat keduanya, ambil diskon 30%. Itu benar-benar terdengar seperti promosi dagang.

Ini bukan tentang menemukan jawaban terpendek secara keseluruhan, tetapi lebih pendek di setiap bahasa.

Dan sekarang, salinan cuplikan papan peringkat yang tidak tahu malu.

Papan Peringkat

Cuplikan Stack di bagian bawah posting ini menghasilkan katalog dari jawaban a) sebagai daftar solusi terpendek per bahasa dan b) sebagai leaderboard keseluruhan.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N bytes

di mana N adalah ukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:

## Perl, 43 + 2 (-p flag) = 45 bytes

Anda juga dapat membuat nama bahasa menjadi tautan yang kemudian akan muncul di cuplikan:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Daniel M.
sumber
4
"Pivot harus dipilih secara acak atau dengan median tiga (elemen 1, terakhir, dan tengah)." Apa artinya ini? Anda sebelumnya mengatakan hanya satu elemen yang dipilih.
msh210
2
@daniero Snippet sudah diperbaiki sekarang
Daniel M.
1
Apakah algoritma pilihan tengah merupakan persyaratan sulit? Itu tidak praktis (seperti dalam, itu kinerja tank) dalam bahasa yang menggunakan daftar tertaut sebagai jenis array utama mereka (Haskell, LISP) dan sudah ada setidaknya satu jawaban yang mengabaikan aturan.
John Dvorak
2
Baik pivot acak dan median tiga bermasalah dalam bahasa berbasis daftar. Keduanya memerlukan akses acak ke dalam array dan mengakses akhir dari daftar yang ditautkan adalah O (n). Mengambil Mengambil median dari tiga elemen pertama tidak cukup melakukan jenis pekerjaan yang sama (juga karena Anda akan mengambil poros yang sama dalam tiga pembagian saja) dan hanya memperumit kode tanpa alasan yang baik.
John Dvorak
1
Pivot acak juga bermasalah di Haskell karena alasan lain - setelah Anda mulai melempar dadu, Anda tidak lagi menulis fungsi. Anda mendefinisikan tindakan I / O yang menghasilkan array. Anda bisa mendefinisikan fungsi yang menggunakan status RNG sebagai argumen, tetapi juga tidak terlalu bagus.
John Dvorak

Jawaban:

10

C ++, 440.3 405 388 byte

518 byte - 15% bonus untuk jenis penyisipan = 440,3 byte

477 byte - bonus 15% untuk jenis penyisipan = 405,45 byte

474 byte - 15% bonus untuk jenis penyisipan = 402,9 byte

456 bytes - 15% bonus for insertion sort = 387.6 bytes

Terima kasih kepada @Luke karena telah menghemat 3 byte (2 sungguh).

Terima kasih kepada @ Dúthomhas karena telah menghemat 18 (15 benar-benar) byte.

Perhatikan bahwa saya baru di sini dan ini adalah posting pertama saya.

Ini adalah file .h(header).

Kode Terkompresi:

#include<iostream>
#include<ctime>
#include<cstdlib>
void s(int a[],int i,int j){int t=a[i];a[i]=a[j];a[j]=t;}int z(int a[],int b,int e){int p=a[(rand()%(e-b+1))+b];b--;while(b<e){do{b++;}while(a[b]<p);do{e--;}while(a[e]>p);if(b<e){s(a, b, e)}}return b;}void q(int a[],int b,int e){if(e-b<=5){for(int i=b;i<e;i++){for(int j=i;j>0;j--){if(a[j]<a[j-1]){s(a,j,j-1);}else{break;}}}return;}int x=z(a,b,e);q(a,b,x);q(a,x,e);}void q(int a[],int l){q(a,0,l);}

Kode Lengkap:

#include <iostream>
#include <ctime>
#include <cstdlib>

void swapElements(int toSort[], int i, int j) {
    int temp = toSort[i];
    toSort[i] = toSort[j];
    toSort[j] = temp;
}

int partitionElements(int toSort[], int beginPtr, int endPtr)
{
    int pivot = toSort[(rand() % endPtr - beginPtr + 1) + beginPtr];
    beginPtr--;
    while (beginPtr < endPtr) {
        do {
            beginPtr++;
        } while (toSort[beginPtr] < pivot);
        do {
            endPtr--;
        } while (toSort[endPtr] > pivot);
        if (beginPtr < endPtr) {
            // Make sure they haven't crossed yet
            swapElements(toSort, beginPtr, endPtr);
        }
    }
    return beginPtr;
}

void quickSort(int toSort[], int beginPtr, int endPtr)
{
    if (endPtr - beginPtr <= 5) { // Less than 5: insertion sort
        for (int i = beginPtr; i < endPtr; i++) {
            for (int j = i; j > 0; j--) {
                if (toSort[j] < toSort[j - 1]) {
                    swapElements(toSort, j, j - 1);
                } else {
                    break;
                }
            }
        }
        return;
    }
    int splitIndex = partitionElements(toSort, beginPtr, endPtr);
    quickSort(toSort, beginPtr, splitIndex );
    quickSort(toSort, splitIndex, endPtr);
}

void quickSort(int toSort[], int length)
{
    quickSort(toSort, 0, length);
}
Cangkir Kopi
sumber
5
Anda dapat menyimpan 10 byte menggunakan nama huruf tunggal, bukan quickSort dan menghapus spasi di panggilan fungsi terakhir. Dan saya yakin Anda bisa mendapatkan skor yang lebih baik dengan menghindari bonus (15% tidak cukup)
edc65
1
Anda dapat menyimpan 5 byte lainnya dengan mengganti tanda kurung argumen dengan tanda bintang tunggal. Beberapa sihir makro bisa mengurangi beberapa byte lagi, saya kira.
cadaniluk
2
Anda tidak perlu spasi setelahnya #include.
Lukas
Singkirkan 34 byte dengan menghapus panggilan ke srand(time(NULL));Anda masih akan mendapatkan nomor pseudo-acak rand().
Dúthomhas
9

APL, 49 42 byte

{1≥⍴⍵:⍵⋄(∇⍵/⍨⍵<p),(⍵/⍨⍵=p),∇⍵/⍨⍵>p←⍵[?⍴⍵]}

Ini menciptakan fungsi monadik rekursif tanpa nama yang menerima larik di sebelah kanan. Itu tidak memenuhi syarat untuk bonus.

Penjelasan:

{1≥⍴⍵:⍵⋄                                     ⍝ If length(⍵) ≤ 1, return ⍵
                                  p←⍵[?⍴⍵]}  ⍝ Choose a random pivot
                           ∇⍵/⍨⍵>            ⍝ Recurse on >p
                  (⍵/⍨⍵=p),                  ⍝ Concatenate with =p
        (∇⍵/⍨⍵<p),                           ⍝ Recurse on <p

Cobalah online

Memperbaiki masalah (dengan biaya 8 byte) berkat marinus dan menyimpan 7 byte berkat Thomas Kwa!

Alex A.
sumber
Pertanyaannya menentukan tidak akan ada duplikat. (Tidak tahu bagaimana saya butuh waktu lama untuk melihatnya ...)
lirtosiast
5

C ++ 17, 254 199 195 byte

#include<vector>
#include<cstdlib>
#define P push_back(y)
using V=std::vector<int>;V q(V a){int p=a.size();if(p<2)return a;p=rand()%p;V l,r;for(y:a)(y<a[p]?l:r).P;l=q(l);for(y:q(r))l.P;return l;}

Dengan spasi putih:

V q(V a) {
    int p = a.size();

    if (p < 2)
        return a;

    p = rand() % p;
    V l,r;

    for (y : a)
        (y < a[p] ? l : r).P;

    l=q(l);

    for (y : q(r))
        l.P;

    return l;
}
Lynn
sumber
Tidak perlu untuk srand (waktu (NULL)). Tidak perlu untuk dihapus, biarkan nilainya dipartisi, lalu ubah 'if (a.empty ())' menjadi 'if (a.size () <2)' dan hapus 'lP (x)'.
Chris Jefferson
Menghapuskan penghapusan memungkinkan saya untuk menyimpan banyak byte. Terima kasih!
Lynn
Satu lagi kecil: Tidak perlu menetapkan 'r = q (r)', cukup gunakan 'untuk (y: q (r))', tapi hanya itu yang bisa saya lihat!
Chris Jefferson
Hanya ingin tahu: di mana C ++ 17 khususnya digunakan di sini?
kirbyfan64sos
1
for (y : a)jika tidak perlu for (auto y : a)atau for (int y : a). (Sebenarnya, clang++menyebut ini ekstensi C ++ 1z , tapi sepertinya bukan C ++ 17? Saya tidak tahu dan sudah larut malam untuk mencarinya.)
Lynn
4

Pyth, 25 byte

L?tbsyMa_,]JObf<TJbf>TJbb

Ini mendefinisikan fungsi y, yang mengambil daftar angka sebagai input.

Cobalah online: Demonstrasi

Penjelasan

L?tbsyMa_,]JObf<TJbf>TJbb
L                          define function y(b), that returns: 
 ?tb                         if t[1:] (if the list has more than one element):
            Ob                 choose a random element of b
           J                   save it in J
          ]                    put J in a list
         ,    f<TJb            create a pair, that contains ^ and a list of 
                               all numbers smaller than J: [[J], [smaller than J]] 
        _                      reverse this list: [[smaller than J], [J]]
       a           f>TJb       append a list with all elements bigger than J: 
                               [[smaller than J], [J], [bigger than J]]
     yM                        call y recursively for each sublist
    s                          combine the results and return it
                        b    else: simply return b

Pyth, 21 byte (mungkin tidak valid)

Saya menggunakan metode "grup-oleh", yang secara internal menggunakan semacam. Saya menggunakannya untuk membagi daftar asli menjadi tiga sublists (semua elemen lebih kecil dari pivot, pivot, dan semua elemen lebih besar dari pivot). Tanpa mengurutkan dalam "grup-oleh", itu bisa mengembalikan 3 daftar ini dalam urutan yang berbeda.

Seperti yang dikatakan, ini mungkin tidak valid. Meskipun demikian saya akan menyimpannya di sini, karena ini merupakan solusi yang menarik.

L?tb&]JObsyM.g._-kJbb

Cobalah online: Demonstrasi

Penjelasan

L?tb&]JObsyM.g._-kJbb
L                      def y(b): return
 ?tb                     if t[1:] (if the list has more than one element):
       Ob                  choose a random element of b
      J                    save it in J
    &]                     put it in an array and call "and" 
                           (hack which allows to call 2 functions in one statement)

            .g     b       group the elements in b by:
              ._-kJ           the sign of (k - J)
                           this generates three lists
                             - all the elements smaller than J
                             - J
                             - all the elements bigger than J
          yM               call y recursively for all three lists
         s                 and combine them
                    b    else: return b
Jakube
sumber
3

> <> (Ikan), 313 309 byte

!;00l[l2-[b1.
>:0)?v~$:@&vl2,$:&${:}$
^-1@{< ]]. >055[3[5b.
?v~~@~ v:}@:}@:}:}@:}@}}}(}(}({{:@=
.>=$~?$>~]]
.001-}}d6.{$}1+}d6
?v:{:}@{(?v08.}:01-=
 >{$~~{09.>95.v-1@{<   v-1}$<
.:@}:@{=${::&@>:0)?^~}&>:0)?^~+}d6
 1-:0a.{{$&l&1+-: >:0)?v~:1)?!v62fb.
>:0)?v~:}:1)?v~69.^@{-1<>.!]]~<
^@{-1<:}@@73.>69@@:3+[{[b1.

Saya butuh waktu lama untuk menulis. Anda dapat mencobanya di sini , cukup masukkan daftar yang harus disortir ke dalam tumpukan awal, dipisahkan dengan koma, sebelum menjalankan program.

Bagaimana itu bekerja

Program ini mengambil elemen pertama, tengah dan terakhir dalam tumpukan awal dan menghitung median dari ketiganya.
Kemudian mengubah tumpukan ke:

[daftar 1] elemen [daftar 2]

di mana semua yang ada di daftar 1 lebih kecil atau sama dengan elemen dan semua yang ada di daftar 2 lebih besar.
Itu secara berulang mengulangi proses ini pada daftar 1 dan daftar 2 sampai seluruh daftar diurutkan.

Thijs ter Haar
sumber
2

CJam, 40 byte

{_1>{_mR:P-PaL@{_P<{+}{@\+\}?}/J\J+}&}:J

Ini adalah fungsi bernama yang mengharapkan array pada stack dan mendorongnya sebagai balasan.

Cobalah online di juru bahasa CJam .

Kode di atas mengikuti spesifikasi sedekat mungkin. Jika tidak diperlukan, 12 byte dapat disimpan:

{_1>{_mR:P;_{P<},J_@^J+}&}:J
Dennis
sumber
2

Python 3, 123 , 122.

Disimpan 1 byte berkat Aaron.

Ini adalah pertama kalinya saya benar-benar repot untuk menulis algoritma penyortiran. Sebenarnya ini sedikit lebih mudah dari yang saya kira.

from random import*
def q(s):
 if len(s)<2:return s
 p=choice(s);return q([d for d in s if d<=p])+q([d for d in s if d>p])

Tidak Disatukan:

from random import choice
def quick_sort(seq):
    if len(seq) < 2:
        return seq
    low = []
    high = []
    pivot = choice(seq)
    for digit in seq:
        if digit > pivot:
            high += [digit]
        else:
            low += [digit]
    return quick_sort(low) + quick_sort(high)
Morgan Thrapp
sumber
Sepertinya ini mungkin tidak berfungsi, karena <=perbandingan - ini tidak menjamin bahwa pitu di tempat yang tepat, Anda mungkin perlu mengubahnya ke ketidaksetaraan eksklusif, dan menambahkan pdi tengah secara independen (saya belum diuji / dapat dapat menguji kode).
VisualMelon
@VisualMelon Saya mengujinya dengan banyak kasus yang berbeda dan tidak pernah mendapatkan hasil yang salah, tetapi jika Anda dapat menemukan kasus uji yang merusaknya, beri tahu saya. Juga, itu mungkin tidak bekerja dengan duplikat, tetapi tantangan menentukan bahwa tidak akan ada duplikat.
Morgan Thrapp
Saya akan berpikir itu [2, 1, 3]akan mematahkannya 1/3 dari waktu, seperti ketika memilih inden menjadi 2, itu akan memiliki daftar rendah menjadi [2, 1]- Maaf saya tidak dapat menguji ini sendiri sekarang.
VisualMelon
@VisualMelon Yah, tentu saja, tapi kemudian secara rekursif memilah lagi.
Morgan Thrapp
Ah, maaf, tidak terjawab sepenuhnya, tidak seperti yang saya harapkan Quicksort diimplementasikan - memiliki suara positif untuk membingungkan saya
VisualMelon
2

Javascript (ES2015), 112

q=l=>{let p=l[(Math.random()*l.length)|0];return l.length<2?l:q(l.filter(x=>x<=p)).concat(q(l.filter(x=>x>p)));}

Penjelasan

//Define lambda function q for quicksort
q=l=>{

    //Evaluate the pivot
    let p=l[(Math.random()*l.length)|0];

    //return the list if the length is less than 2
    return l.length < 2 ? l:

    //else return the sorted list of the elements less or equal than 
      the pivot concatenated with the sorted list of the elements 
      greater than the pivot
    q(l.filter(x=>x<=p)).concat(q(l.filter(x=>x>p)));
}
Flávio Teixeira Penjualan
sumber
ES6 mungkin bisa mempersingkat ini.
Nissa
1

Rubi, 87 60 byte

q=->a,p=a.sample{a[1]?(l,r=a.partition{|e|e<p};q[l]+q[r]):a}

Tidak Disatukan:

def quicksort(a, pivot=a.sample)
  if a.size > 1
    l,r = a.partition { |e| e < pivot}
    quicksort(l) + quicksort(r)
  else
    a
  end
end

Uji:

q[[9, 18, 8, 5, 13, 20, 7, 14, 16, 15, 10, 11, 2, 4, 3, 1, 12, 17, 6, 19]]
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
daniero
sumber
1

Oktaf, 76 75 byte

function u=q(u)n=numel(u);if n>1 k=u(randi(n));u=[q(u(u<k)),q(u(u>=k))];end

Versi multi-baris:

function u=q(u) 
   n=numel(u);
   if n>1 
      k=u(randi(n));
      u=[q(u(u<k)),q(u(u>=k))];
   end
gelas kimia
sumber
1

Julia, 83 byte

Q(x)=endof(x)<2?x:(p=rand(x);[Q((f=filter)(i->i<p,x));f(i->i==p,x);Q(f(i->i>p,x))])

Ini menciptakan fungsi rekursif Qyang menerima array dan mengembalikan array. Itu tidak kondisional menggunakan penyisipan, jadi tidak ada bonus yang berlaku.

Tidak Disatukan:

function Q(x::AbstractArray)
    if endof(x)  1
        # Return on empty or 1-element arrays
        x
    else
        # Select a random pivot
        p = rand(x)

        # Return the function applied to the elements less than
        # the pivot concatenated with those equal to the pivot
        # and the function applied to those greater than the pivot
        [Q(filter(i -> i < p, x));
         filter(i -> i == p, x);
         Q(filter(i -> i > p, x))]
    end
end

Memperbaiki masalah dan menyimpan beberapa byte berkat Glen O!

Alex A.
sumber
Kemungkinan masalah dengan hilangnya elemen berulang (yang sudah ada dalam kode Anda) di samping, Anda dapat menyimpan beberapa byte di sini dengan menetapkan fketika Anda pertama kali menggunakan filter, dan menggunakan endofalih-alih length. Q(x)=endof(x)<2?x:(p=rand(x);[Q((f=filter)(i->i<p,x));p;Q(f(i->i>p,x))])
Glen O
@ GlenO Terima kasih atas sarannya. Saya telah menerapkannya dan memperbaiki masalah dengan elemen berulang.
Alex A.
Saya mengatakan itu bisa menjadi masalah, tetapi saya bertanya pada poster pertanyaan untuk klarifikasi, dan "Masukan mungkin berisi nilai desimal dan negatif. Namun, tidak akan ada duplikat"
Glen O
1

R, 78 byte

Q=function(x)if(length(x)>1)c(Q(x[x<(p=sample(x,1))]),x[x==p],Q(x[x>p]))else x

Ini menciptakan fungsi rekursif Qyang menerima vektor dan mengembalikan vektor. Ini tidak secara kondisional menerapkan penyisipan, jadi tidak ada bonus

Tidak Disatukan:

Q <- function(x) {
    # Check length
    if (length(x) > 1) {
        # Select a random pivot
        p <- sample(x, 1)

        # Recurse on the subarrays consisting of
        # elements greater than and less than p,
        # concatenate with those equal to p
        c(Q(x[x < p]), x[x == p], Q(x[x > p]))
    } else {
        x
    }
}

Cobalah online

Disimpan 4 byte berkat flodel!

Alex A.
sumber
Anda dapat menggigit beberapa byte dengan menjatuhkan "> 1" dari perbandingan panjang. Ini secara implisit membandingkannya dengan 0, tetapi lapisan rekursi tambahan tidak menjadi masalah,
Miff
@Miff Terima kasih atas masukan Anda, tetapi saya sudah mencobanya dan itu tidak menghasilkan hasil yang diharapkan untuk saya.
Alex A.
1

K, 41 byte

s:{$[#x;(s@x@&x<p),p,s@x@&x>p:x@*1?#x;x]}

AMBIL ITU, APL !!! Tidak melakukan bonus apa pun.

kirbyfan64sos
sumber
1

Haskell, 137136 byte

f=filter
m a b c=max(min a b)(min(max a b)c)
q[]=[]
q l=let{n=m(head l)(head$drop(length l`div`2)l)(last l)}in(q$f(<n)l)++(n:(q$f(>n)l))

Versi ungolfed ada di bawah ini, dengan variabel yang diperluas dan nama fungsi dan beberapa hasil antara ditambahkan:

median a b c = max (min a b) (min (max a b) c)
quicksort [] = []
quicksort l = let mid = median (head l) (middle l) (last l)
                  lesser = filter (< mid) l
                  greater = filter (> mid) l
                  middle l = head $ drop (length l `div` 2) l
              in (quicksort lesser) ++ (mid : (quicksort greater))

Saya mengambil keuntungan dari kenyataan bahwa tidak ada duplikat untuk menggunakan dua perbandingan ketat. Saya harus memeriksa apakah Data.List.partitiontidak membuat segalanya lebih pendek, bahkan mengingat saya harus menambahkan pernyataan impor. Saya tidak mengambil bonus jenis penyisipan karena saya anggap Data.List.insertsebagai fungsi terkait penyortiran - dengan demikian dilarang - dan jika tidak menggunakannya, menambahkan jenis penyisipan mendorong kode ke 246 byte, 209.1 dengan bonus, sehingga tidak layak.

Sunting: Terima kasih kepada RobAu untuk saran mereka untuk membuat alias untuk digunakan f=filter. Ini mungkin menyimpan hanya satu byte tetapi semuanya membantu.

arjanen
sumber
1
f=filtermungkin memotong beberapa byte.
RobAu
Mungkin Anda bisa mencukur beberapa byte dengan membuat fungsi untuk menangani dua redundan q$f(>n)ldan q$f(<n)lpanggilan?
Cyoce
1

Tcl, 138 byte

proc q v {if {$v eq {}} return
lassign {} a b
foreach x [lassign $v p] {if {$x<$p} {lappend a $x} {lappend b $x}}
concat [q $a] $p [q $b]}

Ini adalah quicksort yang sangat standar.

Pivot hanyalah elemen pertama dari setiap subarray (saya berpendapat bahwa ini adalah angka acak. Https://xkcd.com/221/ )

Ini tidak terlalu efisien dalam hal penggunaan memori, meskipun itu dapat diperbaiki beberapa dengan tailcallpada rekursi kedua dan kasus dasar n <1 elemen.

Ini versi yang bisa dibaca:

proc quicksort xs {
  if {![llength $xs]} return
  set lhs [list]
  set rhs [list]
  foreach x [lassign $xs pivot] {
    if {$x < $pivot} \
      then {lappend lhs $x} \
      else {lappend rhs $x}
  }
  concat [quicksort $lhs] $pivot [quicksort $rhs]
}

Bekerja pada semua input dan mengizinkan duplikat. Oh, ini juga stabil . Anda dapat mengujinya dengan sesuatu yang sederhana, seperti:

while 1 {
  puts -nonewline {xs? }
  flush stdout
  gets stdin xs
  if {$xs eq {}} exit
  puts [q $xs]    ;# or [quicksort $xs]
  puts {}
}

Nikmati! :HAI)

Dúthomhas
sumber
Anda dapat menyimpan byte yang diganti foreacholeh lmap
sergiol
1

JavaScript (ES6), 191

Q=(a,l=0,h=a.length-1)=>l<h&&(p=((a,i,j,p=a[i+(0|Math.random()*(j-i))])=>{for(--i,++j;;[a[i],a[j]]=[a[j],a[i]]){while(a[--j]>p);while(a[++i]<p);if(i>=j)return j}})(a,l,h),Q(a,l,p),Q(a,p+1,h))

// More readable
U=(a,l=0,h=a.length-1)=>l<h && 
  (p=( // start of partition function
    (a,i,j,p=a[i+(0|Math.random()*(j-i))])=>
    {
      for(--i,++j;;[a[i],a[j]]=[a[j],a[i]])
      {
        while(a[--j]>p);
        while(a[++i]<p);
        if(i>=j)return j
      }
    } // end of partition function
  )(a,l,h),U(a,l,p),U(a,p+1,h))

// This is the shortest insertion sort that I could code, it's 72 bytes
// The bonus is worth  ~30 bytes - so no bonus
I=a=>{for(i=0;++i<a.length;a[j]=x)for(x=a[j=i];j&&a[j-1]>x;)a[j]=a[--j]}


// TEST
z=Array(10000).fill().map(_=>Math.random()*10000|0)

Q(z)

O.innerHTML=z.join(' ')
<div id=O></div>

edc65
sumber
1

Ceylon (hanya JVM), 183 170

Tidak ada bonus yang berlaku.

import ceylon.math.float{r=random}{Float*}q({Float*}l)=>if(exists p=l.getFromFirst((r()*l.size).integer))then q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))}else[];

Tampaknya tidak ada cara lintas platform untuk menghasilkan angka acak di Ceylon, jadi ini hanya JVM. (Pada akhirnya saya memiliki versi non-acak yang juga berfungsi di JS, dan lebih kecil.)

Ini mendefinisikan suatu fungsi yang mengambil versi float, dan mengembalikan versi yang diurutkan.

import ceylon.math.float {
    r=random
}

{Float*} q({Float*} l) {
    if (exists p = l.getFromFirst((r() * l.size).integer)) {
        return q(l.filter((e) => e < p)).chain { p, *q(l.filter((e) => p < e)) };
    } else {
        return [];
    }
}

Jika (terhadap spesifikasi) entri rangkap dilewatkan, mereka akan disaring.

Ini adalah 183 byte: import ceylon.math.float{r=random}{Float*}q({Float*}l){if(exists p=l.getFromFirst((r()*l.size).integer)){return q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))};}else{return[];}}

Kami dapat meningkatkan sedikit dengan menggunakan ifekspresi Ceylon 1.2 yang baru :

import ceylon.math.float {
    r=random
}

{Float*} q({Float*} l) =>
        if (exists p = l.getFromFirst((r() * l.size).integer))
        then q(l.filter((e) => e < p)).chain { p, *q(l.filter((e) => p < e)) }
        else [];

Ini adalah 170 byte: import ceylon.math.float{r=random}{Float*}q({Float*}l)=>if(exists p=l.getFromFirst((r()*l.size).integer))then q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))}else[];


Ini adalah versi non-acak:

{Float*} r({Float*} l) =>
        if (exists p = l.first)
        then r(l.filter((e) => e < p)).chain { p, *r(l.filter((e) => p < e)) }
        else [];

Tanpa spasi, ini akan menjadi 107 byte: {Float*}r({Float*}l)=>if(exists p=l.first)then r(l.filter((e)=>e<p)).chain{p,*r(l.filter((e)=>p<e))}else[];

Paŭlo Ebermann
sumber
0

AutoIt , 320,45 304,3 byte

Ini sangat cepat (untuk AutoIt). Memenuhi syarat untuk bonus semacam penyisipan. Akan menambahkan penjelasan setelah golf terakhir terjadi.

Masukan adalah q(Array, StartingElement, EndingElement).

Func q(ByRef $1,$2,$3)
$5=$3
$L=$2
$6=$1[($2+$3)/2]
If $3-$2<6 Then
For $i=$2+1 To $3
$4=$1[$i]
For $j=$i-1 To $2 Step -1
$5=$1[$j]
ExitLoop $4>=$5
$1[$j+1]=$5
Next
$1[$j+1]=$4
Next
Else
Do
While $1[$L]<$6
$L+=1
WEnd
While $1[$5]>$6
$5-=1
WEnd
ContinueLoop $L>$5
$4=$1[$L]
$1[$L]=$1[$5]
$1[$5]=$4
$L+=1
$5-=1
Until $L>$5
q($1,$2,$5)
q($1,$L,$3)
EndIf
EndFunc

Input + output uji acak:

862, 543, 765, 577, 325, 664, 503, 524, 192, 904, 143, 483, 146, 794, 201, 511, 199, 876, 918, 416
143, 146, 192, 199, 201, 325, 416, 483, 503, 511, 524, 543, 577, 664, 765, 794, 862, 876, 904, 918
mınxomaτ
sumber
Menarik, belum pernah mendengar tentang AutoIt sebelumnya
Daniel M.
0

Java, 346 byte

407 bytes - 15% bonus for insertion sort = 345.95 bytes

Kode Terkompresi:

class z{Random r=new Random();void q(int[] a){q(a,0,a.length);}void q(int[] a,int b,int e){if(e-b<6){for(int i=b;i<e;i++){for(int j=i;j>0&a[j]<a[j-1];j--){s(a,j,j-1);}}return;}int s=p(a,b,e);q(a,b,s);q(a,s,e);}int p(int[] a,int b,int e){int p=a[r.nextInt(e-b)+b--];while(b<e){do{b++;}while(a[b]<p);do{e--;}while(a[e]>p);if(b<e){s(a,b,e);}}return b;}void s(int[] a,int b,int e){int t=a[b];a[b]=a[e];a[e]=t;}}

Kode Lengkap:

public class QuickSort {

    private static final Random RANDOM = new Random();

    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length);
    }

    private static void quickSort(int[] array, int begin, int end) {
        if (end - begin <= 5) {
            for (int i = begin; i < end; i++) {
                for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
                    swap(array, j, j - 1);
                }
            }
            return;
        }
        int splitIndex = partition(array, begin, end);
        quickSort(array, begin, splitIndex);
        quickSort(array, splitIndex, end);
    }

    private static int partition(int[] array, int begin, int end) {
        int pivot = array[RANDOM.nextInt(end - begin) + begin];
        begin--;
        while (begin < end) {
            do {
                begin++;
            } while (array[begin] < pivot);
            do {
                end--;
            } while (array[end] > pivot);
            if (begin < end) {
                // Make sure they haven't crossed yet
                swap(array, begin, end);
            }
        }
        return begin;
    }

    private static void swap(int[] array, int begin, int end) {
        int temp = array[begin];
        array[begin] = array[end];
        array[end] = temp;
    }

}
Cangkir Kopi
sumber
Peningkatan pasangan: 1. singkirkan spasi antara int [] dan a di header metode. 2. Buat kenaikan atau penurunan dalam for loop tempat terakhir variabel diakses. 3. Buat kelas int (atau pasangan) untuk menyimpan byte dengan menggunakannya sebagai ganti int baru. 4. Menggunakan Math.random () dan casting mungkin lebih pendek daripada membuat objek acak.
Biru
0

Mathematica, 93 90 byte

If[Length@#>1,pv=RandomChoice@#;Join[qs2[#~Select~(#<pv&)],{pv},qs2[#~Select~(#>pv&)]],#]&

Tidak ada bonus, belum punya cara minimal untuk melakukan penyisipan. Ketika saya sedang belajar C ++ baru-baru ini, saya melakukan perbandingan berbagai algoritma pengurutan di sini .

Jason B.
sumber
0

Python2, 120 byte

def p(a):
 if[]==a[1:]:return a
 b,c,m=[],[],__import__("random").choice(a)
 for x in a:[b,c][x>m]+=[x];return p(b)+p(c)

if[]==a[1:]persis sepanjang if len(a)>2tetapi terlihat lebih golf.

Filip Haglund
sumber
0

Lua, 242 Bytes

function f(t,p)if(#t>0)then local P,l,r,i=math.random(#t),{},{},table.insert p=t[P]for k,v in ipairs(t)do if(k~=P)then i(v<p and l or r,v)end end t={}for k,v in pairs(f(l))do i(t,v)end i(t,p)for k,v in pairs(f(r))do i(t,v)end end return t end

Tidak Digabungkan & Eksplorasi

function f(t,p)                                             # Assign 'p' here, which saves two bytes, because we can't assign it to t[P] IN the local group.
    if(#t>0)then                                            # Just return 0 length lists...
        local P,l,r,i=math.random(#t),{},{},table.insert    # Using local here actually makes the a,b=1,2 method more efficient here. Which is unnormal for Lua
        p = t[P]                                            # P is the index of the pivot, p is the value of the pivot, l and r are the sub-lists around the pivot, and i is table.insert to save bytes.
        for k,v in ipairs(t) do                             # We use a completely random pivot, because it's cheaper on the bytes.
            if(k~=P)then                                    # Avoid 'sorting' the pivot.
                i(v<p and l or r,v)                         # If the value is less than the pivot value, push it to the left list, otherwise, push it to the right list.
            end                                             #
        end                                                 #
        t = {}                                              # We can re-use t here, because we don't need it anymore, and it's already a local value. Saving bytes!
        for k,v in pairs(f(l)) do                           # Quick sort the left list, then append it to the new output list.
            i(t,v)                                          #
        end                                                 #
        i(t,p)                                              # Append the pivot value.
        for k,v in pairs(f(r)) do                           # Ditto the right list.
            i(t,v)                                          #
        end                                                 #
    end                                                     #
    return t                                                # Return...
end                                                         #
ATaco
sumber
0

Racket 121 byte

(λ(l)(if(null? l)l(let((h(car l))(t(cdr l)))(append(qs (filter(λ(x)(< x h))t))(list h)(qs (filter(λ(x)(>= x h))t))))))

Tidak digabungkan (l = daftar, h = kepala (elemen pertama), t = ekor (elemen lainnya atau sisanya)):

(define qs
  (λ(l)
    (if (null? l) l
        (let ((h (first l))
              (t (rest  l)))
          (append (qs (filter (λ(x) (< x h) ) t))
                  (list h) 
                  (qs (filter (λ(x) (>= x h)) t))  )))))

Pengujian:

(qs (list 5 8 6 8 9 1 2 4 9 3 5 7 2 5))

Keluaran:

'(1 2 2 3 4 5 5 5 6 7 8 8 9 9)
juga
sumber
0

Japt , 23 byte

Setiap bonus harus tiga byte atau kurang untuk melunasi dalam skor total, jadi saya tidak mengambil bonus.

Z=Uö;Ê<2?UUf<Z)cßUf¨Z
Z=Uö;                   // Take a random element from the input for partitioning.
     Ê<2                // If the input is shorter than two elements,
        ?U              // return it.
          :             // Otherwise
           ß      ß     // recursively run again
            Uf<Z        // with both items that are smaller than the partition
                   Uf¨Z // and those that are larger or equal,
                )c      // returning the combined result.

Cobalah online!

Nit
sumber
20 byte
Shaggy