[B! quick sort] yassのブックマーク

yass id:yass

quick sortに関するyassのブックマーク (2)

[KMP77] を読んでみた - d.y.d.
17:53 14/12/22 ソートの逆流れクイックソートってあるじゃないですか、クイックソート。配列、たとえば [4,2,1,7,0,6,5,3] があったときに、小さい方を左に、大きい方を右にまず適当に集める。この「小さい方」と「大きい方」への二分割を、いわゆる再帰的に、分かれたブロック両方で同じ事を繰り返していくと… なんと、小さい順に並んだ配列 [0,1,2,3,4,5,6,7] が出来上がるというアルゴリズムです。逆向き！このデータの流れを「逆向きに」見てみたい。つまり、ソートが終わった最終状態から話が始まります。しかも、さっきから説明なしで意味ありげにくっついていた、「入力配列で元々どの位置にあったか」を表す値に注目していきます。 0の上に[4]がくっついているのは、最初は値0は配列のインデックス[4]の位置にあった、ということを意味しています。（上のソート
yass 2017/01/03
sort

quick sort

merge sort

Algorithm
リンク
How MySQL executes ORDER BY
In last couple of weeks there has been a tide of ORDER/GROUP BY-related optimization bugs, where I was the fixer or the reviewer. This wasn’t an easy job because there is no sane description of how GROUP BY/ORDER BY handling is supposed to work. To figure it out, I had to write an explanation of how it works. The first part is about ORDER BY. Hopefully there will be subsequent parts that will show
yass 2013/10/19
" In a nutshell, filesort() does quicksort on chunks of data that fit into its memory and then uses mergesort approach to merge the chunks. / if the sorted data doesn’t fit into memory (i.e. there is more than one chunk), filesort uses a temporary file to store the chunks. "

mysql

sort

merge sort

sort_buffer_size

quick sort
リンク
1