# \[suggestion\] sorted flag for Array

**URL:** <https://www.ruby-forum.com/t/suggestion-sorted-flag-for-array/168840>\
**Category:** Development\
**Created:** [May 26, 2009, 3:59pm UTC](https://www.ruby-forum.com/t/suggestion-sorted-flag-for-array/168840 "2009-05-26T15:59:11Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Yusuke\_ENDOH](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/c89c15/32.png) [@Yusuke\_ENDOH](https://www.ruby-forum.com/u/Yusuke_ENDOH)\
**Post date:** [May 26, 2009, 3:59pm UTC](https://www.ruby-forum.com/t/suggestion-sorted-flag-for-array/168840/1 "2009-05-26T15:59:11Z")

</div>

e$B1sF#$G$9!#e(B

e$B;W$$IU$-$G$9$,!"e(BArray  
e$B$K!V%=!\<%H:Q$\_!W$rI=$9%U%i%0$r;}$?$;$k$N$O$I$&e(B  
e$B$G$7$g$&$+!#e(B

e$B!V%=!\<%H:Q$\_!W$NG[Ns$KBP$7$F$O!"e(B

- Array#index e$B$de(B include? e$B$GFsJ,C5:w$r;H$&e(B
- Array#uniq e$B$de(B - e$B!"e(B& e$B!"e(B|  
e$B$G$O!"0l;~%O%C%7%e$r:n$i$:!"e(B1 e$B%Q%9$G=hM}$9$ke(B

e$B$H$$$&:GE,2=$,$G$-$^$9!#FC$KA0\<T$Oe(B O(n) e$B$+$ie(B O(log n)  
e$B$K$J$j$^$9!#e(B  
e$BA0\<T$O%F!\<%V%k$rG[Ns$G\<BAu$7$F$$$k%W%m%0%i%`$G;H$($=$&$G!"8e<T$O=89g$re(B e$BG[Ns$GBeBXI=8=$7$F$$$k%W%m%0%i%`$G;H$($=$&$G$9!#e(B

e$B%U%i%0$N4IM}$Oe(B

- e$B%V%m%C%/$J$7e(B Array#sort e$B$de(B Array#sort!  
e$B$NJV$jCM$N%U%i%0$rN)$F$ke(B
- e$BGK2uE\*JQ99$r9T$C$?$i%U%i%0$r\>C$9e(B

e$B$H$9$k$@$1$J$N$G!"%\*!\<%P!\<%X%C%I$OL5;k$G$-$kNL$@$H;W$$$^$9e(B  
(e$BL$8!\>Ze(B) e$B!#e(B

e$B;n83E\*$Ke(B Array#include? e$B$@$1\<BAu$7$^$7$?!#e(B  
e$BHs\>o$K6KC\<$JNc$G\<BB,$7$?$H$3$m!"%_%j%8%J%k$Ge(B 30  
e$BIC!"%Q%C%A8e$Ge(B 0.04 e$BICe(B  
e$B$G$7$?e(B (e$B%_!\<%@$N2~A1$J$N$G?tCM$K$"$^$j0UL#$O$J$$$G$9$,e(B)  
e$B!#e(B

a = ([0] \* 100000 + [1]).sort; 1000.times { a.include?(1) }

e$B\<+J,$G$b$3$NDs0F$,$I$N$/$i$$JXMx$J$N$+e(B  
(e$B$^$?$OJXMx$G$J$$$N$+!"$b$7$/$Oe(B  
e$B$^$:$$$N$+e(B) e$BFI$_$-$l$F$$$^$;$s!#$_$J$5$s$I$&;W$o$l$^$9$+!#e(B

e$B0J2\<!"\<+J,$G9M$(IU$$$?5DO@e(B:

- sort e$B$,JV$7$?G[Ns$@$1B.$$$H$$$&$N$,$o$+$j$K$/$$e(B  
(e$B%V%m%C%/$D$-e(B sort e$B$de(B sort\_by  
e$B$G$O%@%a$H$$$&$N$b$o$+$j$K$/$$$+e(B)

- e$B%=!\<%H$9$Y$-$G$J$$G[Nse(B (\<=\> e$B$,A4=g=x$K$J$C$F$$$J$$G[Nse(B)  
e$B$r%=!\<%H$7$?e(B  
e$BG[Ns$G$O!":GE,2=$G7k2L$,JQ$o$k$3$H$,$"$k$,!“8=\<BE\*$K$^$:$$Nc$O$”$k$+e(B

- \<=\> e$B$He(B ==  
e$B$,L7=b$9$k$h$&$JMWAG$r4^$`G[Ns$G$b7k2L$,JQ$o$k$,!“8=\<BE\*$Ke(B  
e$B$^$:$$Nc$O$”$k$+e(B

# Index: array.c

— array.c (revision 23590)  
+++ array.c (working copy)  
@@ -140,6 +140,14 @@  
FL\_SET(ary, RARRAY\_SHARED\_ROOT\_FLAG);   
} while (0)

+#define RARRAY\_SORTED\_FLAG FL\_USER6  
+#define ARY\_SORTED\_P(ary) (FL\_TEST(ary, RARRAY\_SORTED\_FLAG))  
+#define FL\_SET\_SORTED(ary) do { \

- assert(!ARY\_SORTED\_P(ary)); \
- FL\_SET(ary, RARRAY\_SORTED\_FLAG);   
+} while (0)  
+#define FL\_UNSET\_SORTED(ary) FL\_UNSET(ary, RARRAY\_SORTED\_FLAG)
- 

static void  
ary\_resize\_capa(VALUE ary, long capacity)  
{  
@@ -268,6 +276,9 @@  
ARY\_SET\_PTR(ary, ptr);  
}  
}

- if (ARY\_SORTED\_P(ary)) {
- FL\_UNSET\_SORTED(ary);
- }  
}

VALUE  
@@ -1863,6 +1874,7 @@  
}  
/\* tmp will be GC’ed. \*/  
RBASIC(tmp)-\>klass = rb\_cArray;

- if (!rb\_block\_given\_p()) FL\_SET\_SORTED(ary);  
}  
return ary;  
}  
@@ -2856,6 +2868,25 @@  
{  
long i;

- if (ARY\_SORTED\_P(ary)) {

- long j;

- struct ary\_sort\_data data;

- volatile VALUE tmp = rb\_ary\_tmp\_new(0);

- data.ary = tmp;

- data.opt\_methods = 0;

- data.opt\_inited = 0;

- i = 0; j = RARRAY\_LEN(ary) - 1;

- if (j == -1) return Qfalse;

- while (i \<= j) {

- 

```
 long m = i + (j - i) / 2;

```

- 

```
 long r = sort_2(&RARRAY_PTR(ary)[m], &item, &data);

```

- 

```
 if (!ARY_SORTED_P(ary)) goto unsorted;

```

- 

```
 if (r == 0) return Qtrue;

```

- 

```
 if (r > 0) j = m - 1; else i = m + 1;

```

- }

- return Qfalse;

- }

- unsorted:  
for (i=0; i\<RARRAY\_LEN(ary); i++) {  
if (rb\_equal(RARRAY\_PTR(ary)[i], item)) {  
return Qtrue;

---

<div class="post-metadata">

**Author:** ![Yusuke\_ENDOH](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/c89c15/32.png) [@Yusuke\_ENDOH](https://www.ruby-forum.com/u/Yusuke_ENDOH)\
**Post date:** [June 1, 2009, 12:10pm UTC](https://www.ruby-forum.com/t/suggestion-sorted-flag-for-array/168840/2 "2009-06-01T12:10:37Z")

</div>

e$B@\>;3OB9-$G$9!#e(B

At Tue, 26 May 2009 22:58:16 +0900,  
Yusuke ENDOH wrote:

> e$B\<+J,$G$b$3$NDs0F$,$I$N$/$i$$JXMx$J$N$+e(B (e$B$^$?$OJXMx$G$J$$$N$+!"$b$7$/$Oe(B  
> e$B$^$:$$$N$+e(B) e$BFI$_$-$l$F$$$^$;$s!#$_$J$5$s$I$&;W$o$l$^$9$+!#e(B

e$B%=!\<%H8e$K!Ve(B\<=\>e$B!W$r:FDj5A$7$?$j!"e(B  
(0…100).map{|i|[i]}.sort.map!{|a|a[0]=-a[0]}  
e$B$N$h$&$K%=!\<%H8e$KCf?H$NCf?H$rJQ99$7$?$j$7$?\>l9g$Ne(B  
e$B5sF0$,JQ$o$k$N$O$o$+$j$K$/$$$H;W$$$^$9!#e(B

---

<div class="post-metadata">

**Author:** ![Yusuke\_ENDOH](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/c89c15/32.png) [@Yusuke\_ENDOH](https://www.ruby-forum.com/u/Yusuke_ENDOH)\
**Post date:** [June 1, 2009, 5:11pm UTC](https://www.ruby-forum.com/t/suggestion-sorted-flag-for-array/168840/3 "2009-06-01T17:11:33Z")

</div>

e$B1sF#$G$9!#e(B

2009/06/01 19:09 Kazuhiro NISHIYAMA [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> e$B$N$h$&$K%=!\<%H8e$KCf?H$NCf?H$rJQ99$7$?$j$7$?\>l9g$Ne(B  
> e$B5sF0$,JQ$o$k$N$O$o$+$j$K$/$$$H;W$$$^$9!#e(B

e$B$J$k$[$I!"A0\<T$OBP:v$G$-$k5$$,$7$^$9$,!"8e\<T$O$I$&$7$h$&$be(B  
e$B$J$5$=$&$G$9$M!#8+Mn$H$7$F$^$7$?!#e(B  
e$B$3$NDs0F$O\<h$j2\<$2$^$9!#$\*A{$,$;$7$^$7$?!#e(B