比較ソートの理論限界　これ分かる奴いるのか... [173238122]

1 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:11:19.35 ID:I60i7POj0.net ?2BP(1000)

http://img.5ch.net/ico/obake2.gif
https://i.imgur.com/RnkcSH5.jpg

ソート - Wikipedia
https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88

2 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:12:36.39 ID:LXkF1qhga.net

少なくともバブルソートではない

3 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:13:56.58 ID:ZLhWYlWe0.net

まーじで？

4 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:17:36.97 ID:4omrp6SJp.net

なるほどね

5 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:18:23.06 ID:6OxMrM4+0.net

木構造仮定してるしこれヒープソートじゃねえの

6 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:19:29.29 ID:56GvflwI0.net

男ならボゴソートで一発ツモ狙え

7 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:21:37.62 ID:65aDFblVa.net

記号使って圧縮して書いてるだけ
圧縮せずに文章で書けば誰でもわかる

8 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:24:21.15 ID:hX8zhSzH0.net

高専在学中は理解できてたけど今はもう無理

9 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:32:49.68 ID:oukjvubv0.net

ちまちま比べてないでバケツにぶちこめ

10 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:43:41.60 ID:nwVh5+xO0.net

簡単すぎだろ

11 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:44:43.94 ID:zdf4pXps0.net

qsortにとりあえずつっこむか、適当なライブラリにつっこむから、
あまりsortの種類って気にしないよね

12 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:44:45.45 ID:CBOsvsPvM.net

比叡ソートはそんな使わない

13 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:47:15.65 ID:PYgGtBzGK.net

クイックソートの話はオーダー含めて結構基本じゃないのか

14 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:47:32.41 ID:kRE/87gy0.net

メモリじゃぶじゃぶ使うソートアルゴリズムの仕事とか
一時期やっとったなぁ

15 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 21:54:00.50 ID:WfpuYype0.net

ラディックスソートとかコムソートじゃないタイプの比較処理を使うソートの限界ってことやろ。。

16 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 22:21:59.88 ID:qVLdieLk0.net

長さnの数列の並べ方はn!なのはわかるだろ？
比較ソートの場合各比較で数列の並び方が二通り考えられるから、比較回数をhとすると2^h個の数列が生成できる
アルゴリズムはn!通りの数列をすべてソートできなければいけないから、比較回数hは2^h >= n! = O(n^n) を満たす必要がある
両辺に対数をとって、h >= O(n log n)
木を書いてややこしくするからヒープソートとか言い出すやつが出る

17 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 22:48:11.77 ID:6OxMrM4+0.net

>>16
ああ、やっとわかった

ありがと

18 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/09(火) 23:45:07.87 ID:ZLhWYlWe0.net

比較ソートって何だと思って検索したがソートアルゴリズムの分類みたいなものかな？

ヒープソートやマージソートは比較ソートに含まれる
みたいな使い方かな

検索しても>>1に載ってるのしか見つからない

19 ：：2018/10/10(水) 06:22:16.57 .net

test

20 ：：2018/10/10(水) 06:22:36.46 .net

tes

21 ：：2018/10/10(水) 06:22:52.29 .net

tes

22 ：：2018/10/10(水) 06:23:07.30 .net

書き込みテスト

23 ：：2018/10/10(水) 06:23:22.47 .net

test

24 ：：2018/10/10(水) 06:23:42.84 .net

test

25 ：：2018/10/10(水) 06:23:57.35 .net

テスト

26 ：：2018/10/10(水) 06:24:12.03 .net

書き込みテスト

27 ：：2018/10/10(水) 06:24:31.85 .net

test

28 ：：2018/10/10(水) 06:24:47.95 .net

書き込みテスト

29 ：：2018/10/10(水) 06:25:02.17 .net

tes

30 ：：2018/10/10(水) 06:25:16.50 .net

テスト

31 ：：2018/10/10(水) 06:25:37.29 .net

テスト

32 ：：2018/10/10(水) 06:25:52.21 .net

tes

33 ：：2018/10/10(水) 06:26:08.57 .net

tes

34 ：：2018/10/10(水) 06:26:24.95 .net

test

35 ：：2018/10/10(水) 06:26:43.71 .net

テスト

36 ：：2018/10/10(水) 06:26:57.92 .net

test

37 ：：2018/10/10(水) 06:27:11.99 .net

テスト

38 ：：2018/10/10(水) 06:27:32.45 .net

test

39 ：：2018/10/10(水) 06:27:47.82 .net

tes

40 ：：2018/10/10(水) 06:28:02.87 .net

書き込みテスト

41 ：：2018/10/10(水) 06:28:17.43 .net

テスト

42 ：：2018/10/10(水) 06:28:36.54 .net

test

43 ：：2018/10/10(水) 06:28:52.40 .net

テスト

44 ：：2018/10/10(水) 06:29:06.50 .net

テスト

45 ：：2018/10/10(水) 06:29:20.71 .net

書き込みテスト

46 ：番組の途中ですがアフィサイトへの＼(^o^)／です ：2018/10/10(水) 06:29:21.13 ID:Gh9mgCjJ0.net

大学でやるだろ

47 ：：2018/10/10(水) 06:29:39.75 .net

テスト

48 ：：2018/10/10(水) 06:29:55.62 .net

test

49 ：：2018/10/10(水) 06:30:10.33 .net

書き込みテスト

50 ：：2018/10/10(水) 06:30:25.84 .net

test

51 ：：2018/10/10(水) 06:30:44.99 .net

test

52 ：：2018/10/10(水) 06:31:00.06 .net

tes

53 ：：2018/10/10(水) 06:31:18.51 .net

テスト

54 ：：2018/10/10(水) 06:31:40.80 .net

tes

55 ：：2018/10/10(水) 06:31:56.01 .net

test

56 ：：2018/10/10(水) 06:32:10.50 .net

書き込みテスト

57 ：：2018/10/10(水) 06:32:28.77 .net

書き込みテスト

58 ：：2018/10/10(水) 06:32:48.59 .net

test

59 ：：2018/10/10(水) 06:33:06.57 .net

tes

60 ：：2018/10/10(水) 06:33:25.77 .net

書き込みテスト

61 ：：2018/10/10(水) 06:33:44.15 .net

書き込みテスト

62 ：：2018/10/10(水) 06:33:59.38 .net

テスト

63 ：：2018/10/10(水) 06:34:14.02 .net

テスト

64 ：：2018/10/10(水) 06:34:33.71 .net

test

65 ：：2018/10/10(水) 06:34:49.69 .net

tes

66 ：：2018/10/10(水) 06:35:05.14 .net

test

67 ：：2018/10/10(水) 06:35:19.79 .net

テスト

68 ：：2018/10/10(水) 06:35:39.36 .net

tes

69 ：：2018/10/10(水) 06:35:55.10 .net

テスト

70 ：：2018/10/10(水) 06:36:10.59 .net

書き込みテスト

71 ：：2018/10/10(水) 06:36:26.86 .net

test

72 ：：2018/10/10(水) 06:36:44.92 .net

テスト

73 ：：2018/10/10(水) 06:36:59.68 .net

書き込みテスト

74 ：：2018/10/10(水) 06:37:18.44 .net

テスト