Algoritma bola dalam ruang hampa sangat bagus. Namun, mari kita turun dari surga ke bumi yang penuh dosa dan melihat bagaimana semua keindahan teoretis ini akan membuktikan dirinya dalam praktik.

Analisis jenis kelas berikutnya akan berakhir dengan tes untuk jenis kelas. Hari ini kita akan lari (bukan dalam arti membuang, tetapi dalam arti berlari dalam ujian) menyortir pertukaran. Berbagai kelas lain akan dijalankan nanti.

Dalam perlombaan hari ini terlibat:

Kelompok terlemah

Algoritma ini tidak mengklaim apa pun karena kompleksitas waktu yang tertekan. Kami mengujinya murni untuk referensi.

Semacam konyol

Penyortiran lambat

Pemilahan bodoh

Ini bahkan lebih menarik bukan hanya seberapa baik mereka, tetapi seberapa buruk mereka dalam bisnis, dan mana di antara mereka yang terburuk.

Grup utama

Di sini dikumpulkan pertukaran sortir a la O ( n ² ). Penyortiran katai (dan pengoptimalannya) + segala macam variasi penyortiran gelembung.

Sortir Kurcaci

Penyortiran katai (dioptimalkan)

Sortir Bubble

Sortasi koktail

Sortir genap

Ini adalah bagian paling menarik dari pengukuran hari ini. Di antara perwakilan dari kelompok utama inilah perjuangan yang paling keras kepala diharapkan.

Kelompok terkuat

Salah satu varietas gelembung - pengurutan dengan sisir - berhasil mengatasi penghalang O ( n ² ) dan mencapai waktu yang dihormati O ( n log n ). Jadi dalam kompetisi kami, sortasi cepat memiliki saingan yang layak. Juga, cobalah k-sort yang baru ditemukan , yang merupakan variasi dari sort cepat.

Urutkan sikat rambut

Sortir cepat

K sorting

Omong-omong, yang terkuat tidak hanya sebanding satu sama lain. Pada beberapa set data, kelompok utama akan berada dalam persaingan yang serius.

Kode sumber

Jenis Pertukaran Python

def stooge_rec(data, i = 0, j = None): if j is None: j = len(data) - 1 if data[j] < data[i]: data[i], data[j] = data[j], data[i] if j - i > 1: t = (j - i + 1) // 3 stooge_rec(data, i, j - t) stooge_rec(data, i + t, j) stooge_rec(data, i, j - t) return data def stooge(data): return stooge_rec(data, 0, len(data) - 1) def slow_rec(data, i, j): if i >= j: return data m = (i + j) // 2 slow_rec(data, i, m) slow_rec(data, m + 1, j) if data[m] > data[j]: data[m], data[j] = data[j], data[m] slow_rec(data, i, j - 1) return data def slow(data): return slow_rec(data, 0, len(data) - 1) def stupid(data): i, size = 1, len(data) while i < size: if data[i - 1] > data[i]: data[i - 1], data[i] = data[i], data[i - 1] i = 1 else: i += 1 return data def gnome(data): i, size = 1, len(data) while i < size: if data[i - 1] <= data[i]: i += 1 else: data[i - 1], data[i] = data[i], data[i - 1] if i > 1: i -= 1 return data def gnome_opt(data): i, j, size = 1, 2, len(data) while i < size: if data[i - 1] <= data[i]: i, j = j, j + 1 else: data[i - 1], data[i] = data[i], data[i - 1] i -= 1 if i == 0: i, j = j, j + 1 return data def bubble(data): changed = True while changed: changed = False for i in range(len(data) - 1): if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] changed = True return data def shaker(data): up = range(len(data) - 1) while True: for indices in (up, reversed(up)): swapped = False for i in indices: if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] swapped = True if not swapped: return data def odd_even(data): n = len(data) isSorted = 0 while isSorted == 0: isSorted = 1 for i in range(1, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 for i in range(0, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 return data def comb(data): gap = len(data) swaps = True while gap > 1 or swaps: gap = max(1, int(gap / 1.25)) # minimum gap is 1 swaps = False for i in range(len(data) - gap): j = i + gap if data[i] > data[j]: data[i], data[j] = data[j], data[i] swaps = True return data def quick(data): less = [] pivotList = [] more = [] if len(data) <= 1: return data else: pivot = data[0] for i in data: if i < pivot: less.append(i) elif i > pivot: more.append(i) else: pivotList.append(i) less = quick(less) more = quick(more) return less + pivotList + more def k(data): return k_rec(data, 0, len(data) - 1) def k_rec(data, left, right): key = data[left] i = left j = right + 1 k = left + 1 p = left + 1 temp = False while j - i >= 2: if key <= data[p]: if p != j and j != right + 1: data[j] = data[p] elif j == right + 1: temp = data[p] j -= 1 p = j else: data[i] = data[p] i += 1 k += 1 p = k data[i] = key if temp: data[i + 1] = temp if left < i - 1: k_rec(data, left, i - 1) if right > i + 1: k_rec(data, i + 1, right) return data

Urusan Pertukaran PHP

  // function StoogeSort(&$arr, $i, $j) { if($arr[$j] < $arr[$i]) list($arr[$j], $arr[$i]) = array($arr[$i], $arr[$j]); if(($j - $i) > 1) { $t = ($j - $i + 1) / 3; StoogeSort($arr, $i, $j - $t); StoogeSort($arr, $i + $t, $j); StoogeSort($arr, $i, $j - $t); } return $arr; } // function SlowSort(&$arr, $i, $j) { if($i >= $j) return $arr; $m = ($i + $j) / 2; SlowSort($arr, $i, $m); SlowSort($arr, $m + 1, $j); if($arr[$m] > $arr[$j]) list($arr[$m], $arr[$j]) = array($arr[$j], $arr[$m]); SlowSort($arr, $i, $j - 1); return $arr; } // function StupidSort($arr) { $i = 1; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ ++$i; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); $i = 1; } } return $arr; } // function GnomeSort($arr) { $i = 1; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ ++$i; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); if($i > 1) --$i; } } return $arr; } // () function GnomeSort_opt($arr) { $i = 1; $j = 2; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ $i = $j; ++$j; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); if(--$i == 0){ $i = $j; $j++; } } } return $arr; } // function BubbleSort($arr) { $c = count($arr) - 1; do { $swapped = false; for ($i = 0; $i < $c; ++$i) { if ($arr[$i] > $arr[$i + 1]) { list($arr[$i + 1], $arr[$i]) = array($arr[$i], $arr[$i + 1]); $swapped = true; } } } while($swapped); return $arr; } // function ShakerSort($arr){ do{ $swapped = false; for($i = 0; $i < count($arr); $i++){ if(isset($arr[$i + 1])) { if($arr[$i] > $arr[$i+1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $swapped = true; } } } if ($swapped == false) break; $swapped = false; for($i = count($arr) - 1; $i >= 0; $i--){ if(isset($arr[$i - 1])){ if($arr[$i] < $arr[$i - 1]) { list($arr[$i], $arr[$i - 1]) = array($arr[$i - 1], $arr[$i]); $swapped = true; } } } } while($swapped); return $arr; } //- function OddEvenSort($arr){ $n = count($arr); $sorted = false; while(!$sorted) { $sorted = true; for($i = 1; $i < $n - 2; $i += 2) { if($arr[$i] > $arr[$i + 1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $sorted = false; } } for($i = 0; $i < $n - 1; $i += 2) { if($arr[$i] > $arr[$i + 1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $sorted = false; } } } } // function CombSort($arr){ $gap = count($arr); $swap = true; while($gap > 1 || $swap){ if($gap > 1) $gap /= 1.25; $swap = false; $i = 0; while($i + $gap < count($arr)){ if($arr[$i] > $arr[$i + $gap]){ list($arr[$i], $arr[$i + $gap]) = array($arr[$i + $gap], $arr[$i]); $swap = true; } ++$i; } } return $arr; } // function QuickSort($arr) { $loe = $gt = array(); if(count($arr) < 2) { return $arr; } $pivot_key = key($arr); $pivot = array_shift($arr); foreach($arr as $val){ if($val <= $pivot){ $loe[] = $val; }elseif ($val > $pivot){ $gt[] = $val; } } return array_merge(QuickSort($loe), array($pivot_key => $pivot), QuickSort($gt)); } //k- function K_Sort($arr) { K_Sort_rec($arr, 0, count($arr) - 1); return $arr; } function K_Sort_rec(&$arr, $left, $right) { $key = $arr[$left]; $i = $left; $j = $right + 1; $k = $p = $left + 1; $temp = false; while($j - $i >= 2) { if($key <= $arr[$p]) { if(($p != $j) && ($j != ($right + 1))) { $arr[$j] = $arr[$p]; } elseif($j == ($right + 1)) { $temp = $arr[$p]; } --$j; $p = $j; } else { $arr[$i] = $arr[$p]; ++$i; ++$k; $p = $k; } } $arr[$i] = $key; if($temp) $arr[$i + 1] = $temp; if($left < ($i - 1)) K_Sort_rec($arr, $left, $i - 1); if($right > ($i + 1)) K_Sort_rec($arr, $i + 1, $right); }

Waktu

Waktu diukur di mana-mana dalam hitungan detik akurat untuk mikrodetik.

Jika satu pak array (dari sepuluh, seratus atau bahkan satu juta keping) segera dimasukkan ke algoritma, maka total waktu ditunjukkan.

Besi adalah laptop lama saya yang setia yang tahu waktu yang lebih baik. Jadi, sangat mungkin, semuanya akan bekerja untuk Anda lebih cepat.

Yang terburuk dari yang terburuk

Segera berurusan dengan orang luar. Array untuk 40/50/60 elemen yang berisi angka acak dari 0 hingga 9 disiapkan untuk mereka.

type = acak, unik = Salah, min = 0, maks = 9, jumlah = 1
ukuran
40		50		60
Python	Php	Python	Php	Python	Php
0,004	0,001	0,005	0,003	0,007	0,004
0,007	0,009	0,018	0,009	0,018	0,023
0,02	8.26647	0,053	20.8722	0,12901	45.9786

Penyortiran bodoh adalah urutan besarnya lebih cepat dari penyortiran konyol, dan penyortiran konyol adalah urutan besarnya lebih cepat dari lamban. Tidak ada yang perlu diperhatikan.

Petani menengah

Untuk memeriksa rata-rata, paket seratus array masing-masing 100 elemen (nomor unik 100 hingga 999), serta paket sepuluh array masing-masing elemen 1000 (nomor unik 1000 hingga 9999) dihasilkan.

Susunan acak, susunan yang hampir diurutkan, dan susunan urutan terbalik disiapkan.

Middleweight: Acak

type = acak, unik = Benar
size ^{(min to max)} × hitung
100 ^{(100 hingga 999)} × 100		1000 ^{(1000 hingga 9999)} × 10
Python	Php	Python	Php
0,14101	0,18901	1.59109	1.7251
0,20601	0,22301	2.33013	2.09712
0,15301	0,22901	1.6711	2.23613
0,21601	0,26402	2.55515	2.73116
0,16701	0,33402	1.7251	3.13218

Sekitar hasil yang sama untuk semua. Implementasi python bekerja sedikit lebih cepat daripada PHP.

Middles: Hampir diurutkan

type = hampir, unik = Benar
size ^{(min to max)} × hitung
100 ^{(100 hingga 999)} × 100		1000 ^{(1000 hingga 9999)} × 10
Python	Php	Python	Php
0,009	0,005	0,009	0,005
0,009	0,014	0,01	0,014
0,01	0,01	0,011	0,008
0,011	0,008	0,013	0,008
0,011	0,017	0,013	0,017

Semua memiliki hasil yang sama, plus atau minus. Dari yang menarik: pemesanan data parsial puluhan kali meningkatkan kinerja semua algoritma.

Tengah: Terbalik

type = terbalik, unik = Benar
size ^{(min to max)} × hitung
100 ^{(100 hingga 999)} × 100		1000 ^{(1000 hingga 9999)} × 10
Python	Php	Python	Php
0,26801	0,35902	3.10018	3.4292
0,39602	0,45303	4.49726	4.19524
0,22701	0,38402	2.48114	3.64421
0,30202	0,42603	3.34419	4.17524
0,30402	0,64404	3.36519	6.22036

Ada kesimpulan yang menarik - urutan terbalik tidak terlalu mempengaruhi kecepatan, yang jatuh hanya 2 kali dibandingkan dengan angka acak.

Tengah: Biner

type = acak, unik = Salah, min = 0, maks = 1
ukuran × hitungan
100 × 100		1000 × 10
Python	Php	Python	Php
0,073	0,094	0,81105	0,86905
0,10401	0,11301	1.16307	1.06606
0,08801	0,12901	0,86405	1.18207
0,11501	0,15001	1.30107	1.41608
0,11401	0,25801	1.31908	2.46314

Dari kurang lebih menarik: jika alih-alih angka dari 100 hingga 9999 Anda mengurutkan nol dan yang, maka indikator kecepatan tidak akan tumbuh banyak.

Juara

Intrik utama di sini adalah apakah menyortir dengan sisir dan menyortir k dapat memeras puasa dari alas?

Juara: Acak

Untuk mengetahuinya, mari kita bentuk paket array acak: 10 buah 10 ribu elemen dan 10 buah 100 ribu elemen. Saya ingin memberikan jutawan untuk algoritma input, tetapi laptop tidak menarik. Entah tidak ada RAM yang cukup, maka kedalaman rekursi terlalu besar.

type = acak, unik = Salah, hitung = 10
ukuran ^{(minimal maks)}
10000 ^{(dari 10.000 hingga 99999)}		100000 ^{(dari 100000 hingga 999999)}
Python	Php	Python	Php
0,80205	0,63104	10.4506	8.24647
0,47703	1.64009	6.65138	26.5435
0,90005	2.18613	15.8089	29.4867

Penyortiran Python K lebih lambat, dan PHP lebih cepat daripada penyortiran cepat.
Menyortir sisir dibandingkan dengan yang cepat terlihat padat, meskipun lebih rendah dari itu di semua tes (dan yang ini dan yang berikutnya) untuk setiap kumpulan data.

Namun, ada sisir dan keuntungan penting yang tak terbantahkan. Itu tidak memiliki rekursi dan karena itu, tidak seperti rekan-rekannya, ia berhasil memproses array jutaan elemen.

Kasus khusus

Meskipun juara ratusan kali lebih cepat daripada petani rata-rata, pada beberapa dataset tertentu, pengurutan menunjukkan lebih sederhana bahwa mereka tidak mudah dijahit.

Kasus khusus: Hampir diurutkan

Mari kita coba array yang hampir diurutkan, hanya mengambil ukuran yang lebih besar daripada yang diuji untuk petani rata-rata.

Paket 10 array masing-masing 10 ribu dan paket 10 array masing-masing 100 ribu elemen.

type = hampir, unik = Salah
size ^{(min to max)} × hitung
10.000 ^{(dari 10.000 hingga 99999)} × 10		100000 ^{(dari 100000 hingga 999999)} × 10
Python	Php	Python	Php
0,43202	0,058	0,81705	0,58003
0,084	0,062	0,85805	0,54003
0,11601	0,12401	1.41908	1.36008
0,14001	0,11901	1.83411	1.41708
0,13801	0,23101	1.6491	2.56915
?	122.088	?	?
0,71504	1.58909	9,78356	19.4731

Penyortiran cepat tidak ada di sini sama sekali - tidak ada cukup RAM. Pada saat yang sama, array acak dengan 10/100 ribu elemen diproses oleh quicksort dengan bang. k-sort mengalami masalah serupa, hanya menarik 10 ribu di PHP. Array besar hampir diurutkan adalah kasus merosot untuk penyortiran cepat dan modifikasinya. Karena pengaturan elemen ini, rekursi membagi array menjadi bagian-bagian untuk hampir setiap pasangan elemen yang berdekatan, yang mengarah pada jumlah panggilan rekursi maksimum yang dimungkinkan.

Omong-omong, situasinya mirip dengan array berurutan terbalik besar. Masalah yang sama muncul dengan yang hampir teratur - algoritma harus memanggil dirinya sendiri untuk setiap pasangan elemen yang berdekatan.

Menyortir dengan sisir, meskipun berfungsi satu setengah hingga dua kali lebih lambat daripada cepat atau k (secara umum), tetapi tidak memiliki memori yang disebutkan di atas meluap. Tanpa rekursi - tidak ada masalah.

Nah, kami perhatikan bahwa semua petani menengah bersama-sama menyusul para juara dalam susunan besar yang hampir disortir. Kemudian prinsip itu bekerja: "Pergi dengan tenang - Anda akan melanjutkan."

Kasus khusus: Juta mawar merah array kecil

Array kecil - elemen petani menengah. Jika Anda perlu memproses sejumlah besar set angka kecil, maka Anda bisa mendapatkan keuntungan waktu dengan mengambil gelembung "primitif" atau semacam gnome. Dan gunakan penyortiran cepat dan yang lain menyukainya untuk tugas yang lebih besar.

type = acak, unik = Benar
size ^{(min to max)} × hitung
5 ^{(10 hingga 99)} × 1.000.000		10 ^{(10 hingga 99)} × 1.000.000
Python	Php	Python	Php
11.77267	17.888	24.29039	33.6659
12.51872	18.165	29.33268	35.202
15.44188	17.861	30.06672	36.7911
14.18681	19.7831	31.65981	39.3533
13.63978	24.3374	28.41662	52.864
14.21881	21.1452	25.80548	32.5419
14.58683	28.5016	24.85942	50.3139
18.53806	30.7238	29.6647	58.2493

Dengan penyortiran pertukaran, semuanya jelas. Sekarang untuk bagian yang sangat menarik - urutkan berdasarkan sisipan.

Referensi

Aplikasi-Excel , AlgoLab , yang dengannya Anda dapat selangkah demi selangkah melihat visualisasi dari jenis-jenis ini (dan bukan hanya ini).

Semua array dalam bentuk JSON juga diletakkan di disk Google .

Wiki - Silly / Stooge , Lambat , Kerdil / Gnome , Gelembung / Gelembung , Pengocok / Pengocok , Ganjil / Genap , Sisir / Sisir , Cepat / Cepat

Artikel Seri

Aplikasi Excel AlgoLab.xlsm
Pertukaran macam
- Perbandingan Penukaran Exchange
Urutan Penyisipan
Sortir berdasarkan pilihan
Gabungkan Urusan
Urutkan berdasarkan distribusi
Sortasi Hibrid

Perbandingan Penukaran Exchange