1. # クイックソート 非再帰版
  2.  
  3. use strict;
  4. use warnings;
  5.  
  6. my $LIST_SIZE ||= 20; # 要素数
  7. my @list;
  8.  
  9. # 0から1増分のリストを作成
  10. for(my $i = 0; $i < $LIST_SIZE; $i++){
  11. $list[$i] = int($i);
  12. }
  13.  
  14. #ランダムに並び替える
  15. for (my $i = @list; --$i; ) {
  16. my $j = int rand ($i + 1);
  17. next if $i == $j;
  18. @list[$i, $j] = @list[$j, $i];
  19. }
  20.  
  21. # ソート前の状態表示
  22. &ShowData();
  23.  
  24. # ソート実行
  25. &QSort(0, $LIST_SIZE - 1);
  26.  
  27. # ソート後の状態表示
  28. &ShowData();
  29.  
  30. sub QSort{
  31. my $begin = shift;
  32. my $end = shift;
  33. my @left_stack;
  34. my @right_stack;
  35. my $sp = 1;;
  36. my $left = 0;
  37. my $right = 0;
  38.  
  39. $left_stack[0] = $begin;
  40. $right_stack[0] = $end;
  41.  
  42. while( $sp > 0){
  43. # スタックPOP
  44. --$sp;
  45. $left = $left_stack[$sp];
  46. $right = $right_stack[$sp];
  47.  
  48. if($left < $right){
  49. my $pivot = $list[int(($left + $right) / 2)];
  50. my $i = $left;
  51. my $j = $right;
  52. while(1){
  53. while($list[$i] < $pivot){$i++;}
  54. while($list[$j] > $pivot){$j--;}
  55. if($i >= $j){ last; }
  56. ($list[$i], $list[$j]) = ($list[$j], $list[$i]);
  57. &ShowData(); # 途中表示
  58. $i++;
  59. $j--;
  60. }
  61. # スタックPUSH
  62. if($i - $left < $right - $i){
  63. $left_stack[$sp] = $j + 1;
  64. $right_stack[$sp++] = $right;
  65. $left_stack[$sp] = $left;
  66. $right_stack[$sp++] = $i - 1;
  67. }else{
  68. $left_stack[$sp] = $left;
  69. $right_stack[$sp++] = $i - 1;
  70. $left_stack[$sp] = $j + 1;
  71. $right_stack[$sp++] = $right;
  72. }
  73. }
  74. }
  75. }
  76.  
  77. # リスト表示
  78. sub ShowData{
  79. for my $a(@list){
  80. print $a," ";
  81. }
  82. print "\n";
  83. }
  84.  





| 新しいページ | 編集 | 差分 | 編集履歴 | ページ名変更 | アップロード | 検索 | ページ一覧 | タグ | RSS | ご利用ガイド | 管理者に問合せ |
@wiki - 無料レンタルウィキサービス | プライバシーポリシー