Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Just finished the fastest ever, general purpose sorting algorithm.
Replies: 29   Last Post: Jan 8, 2013 10:21 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
JT

Posts: 1,148
Registered: 4/7/12
Re: Just finished the fastest ever, general purpose sorting algorithm.
Posted: Jan 5, 2013 6:17 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On 5 Jan, 18:39, forbisga...@gmail.com wrote:
> http://stackoverflow.com/questions/3074861/binary-sort-algorithmi
>
> Algorithmi?  That's sorta correct.  it points to:
>
> http://www.brpreiss.com/books/opus5/html/page487.html
>
> It says:
> Whereas a linear search requires O(n) comparisons in the worst case, a binary search only requires  comparisons
>
> and gives this caveat:
> The number of comparisons required by the straight insertion sort is  in the worst case as well as on average. Therefore on average, the binary insertion sort uses fewer comparisons than straight insertion sort. On the other hand, the previous section shows that in the best case the running time for straight insertion is O(n). Since the binary insertion sort method always does the binary search, its best case running time is . Table  summarizes the asymptotic running times for the two insertion sorts.
>
> (sorry that didn't all copy.  quicksort is probably better in most cases.)


Here is how an array implementation of countsort works.
<HTML>
<HEAD><TITLE>SORT</TITLE></HEAD>
<BODY>
<SCRIPT LANGUAGE="Javascript">
function jtsort(){
dist=document.encipher.cipher.value;
dval = dist.split(",");
countval= new Array();
for (j=0;j<256;j++){
countval[j]=0;


}


for (i=0;i<dval.length-1;i++){
temp=dval[i];
countval[temp]=countval[temp]+1;


}


temp2=0;
valdist="";
for (j=0;j<256;j++){
temp2=countval[j]
for (k=0;k<temp2;k++){
valdist=valdist+j+",";
}


}


document.dasort.distrib.value=valdist;


}


</SCRIPT>
<BODY>
<TABLE WIDTH=100%><TR><TD BGCOLOR=BLACK ALIGN=CENTER WITH=50%>
<FONT COLOR=WHITE>
<FORM NAME=dasort onSubmit="jtsort(); return false;">
(n)sort ALGO *Canto was kind of a great man, but not that tall*
<input type=submit value="SORT"><P>
SORTED VALUES:
<TEXTAREA TYPE=TEXT NAME=distrib COLS=40 ROWS=6></TEXTAREA><BR>
</FORM>
<FORM NAME=encipher onSubmit="encrypt(); return false;">
VALUES TO SORT:
<TEXTAREA NAME=cipher COLS=40

ROWS=6>99,22,191,216,69,26,255,126,56,3,206,77,50,84,193,10,7,64,244,173,16
2
,

72,84,162,27,245,33,133,249,201,9,128,78,135,74,115,135,26,237,12,147,89,2
3

1,44,17,174,195,142,232,165,52,130,113,7,101,136,93,110,253,46,82,211,122,2
4

1,2,77,132,103,91,167,105,123,80,50,237,29,33,129,202,217,38,63,39,104,171,
1

0,133,65,109,230,142,59,79,43,83,80,159,47,185,96,177,126,155,82,29,122,92,
1

00,40,21,125,19,70,93,247,11,46,26,35,227,138,137,108,58,19,16,115,24,236,9
9
,

8,151,209,195,38,47,95,47,231,102,80,105,239,161,166,55,244,195,164,245,50 ,

218,158,136,143,99,97,144,69,68,196,141,144,208,125,79,213,135,36,148,38,62 ,

35,30,82,4,180,59,66,219,233,122,244,220,147,114,191,67,195,112,180,169,214 ,

112,170,44,170,168,163,6,90,132,124,156,76,29,52,38,237,138,177,14,130,248,
2

0,238,112,49,137,101,48,85,232,241,3,213,150,10,3,11,217,52,45,22,101,226,2
3
,

212,121,237,254,90,245,172,199,255,68,20,75,26,136,145,93,251,229,34,199,4
8
,

215,103,179,63,190,196,111,206,90,195,211,11,226,207,148,181,36,165,89,133 ,

71,247,207,237,251,159,129,125,209,105,239,100,242,102,116,169,166,70,37,96 ,

218,232,218,37,139,221,63,180,113,190,173,120,5,31,146,19,217,89,255,196,44 ,

125,204,218,129,97,141,101,53,143,127,245,142,66,112,96,128,87,61,106,217,2
1

7,98,71,184,115,182,247,25,131,165,226,4,186,132,16,101,130,223,56,238,149,
2

30,30,19,49,149,179,184,177,34,44,11,222,253,95,180,54,74,205,107,75,252,7,
1

15,226,209,70,132,70,88,108,152,167,89,17,217,99,22,191,216,69,26,255,126,5
6
,

3,206,77,50,84,193,10,7,64,244,173,162,72,84,162,27,245,33,133,249,201,9,1
2

8,78,135,74,115,135,26,237,12,147,89,231,44,17,174,195,142,232,165,52,130,1
1

3,7,101,136,93,110,253,46,82,211,122,241,2,77,132,103,91,167,105,123,80,50,
2

37,29,33,129,202,217,38,63,39,104,171,10,133,65,109,230,142,59,79,43,83,80,
1

59,47,185,96,177,126,155,82,29,122,92,100,40,21,125,19,70,93,247,11,46,26,3
5
,

227,138,137,108,58,19,16,115,24,236,99,8,151,209,195,38,47,95,47,231,102,8
0
,

105,239,161,166,55,244,195,164,245,50,218,158,136,143,99,97,144,69,68,196,
1

41,144,208,125,79,213,135,36,148,38,62,35,30,82,4,180,59,66,219,233,122,244 ,

220,147,114,191,67,195,112,180,169,214,112,170,44,170,168,163,6,90,132,124,
1

56,76,29,52,38,237,138,177,14,130,248,20,238,112,49,137,101,48,85,232,241,3 ,

213,150,10,3,11,217,52,45,22,101,226,23,212,121,237,254,90,245,172,199,255,
6

8,20,75,26,136,145,93,251,229,34,199,48,215,103,179,63,190,196,111,206,90,1
9

5,211,11,226,207,148,181,36,165,89,133,71,247,207,237,251,159,129,125,209,1
0

5,239,100,242,102,116,169,166,70,37,96,218,232,218,37,139,221,63,180,113,19
0
,

173,120,5,31,146,19,217,89,255,196,44,125,204,218,129,97,141,101,53,143,12
7
,

245,142,66,112,96,128,87,61,106,217,217,98,71,184,115,182,247,25,131,165,2
2

6,4,186,132,16,101,130,223,56,238,149,230,30,19,49,149,179,184,177,34,44,11 ,

222,253,95,180,54,74,205,107,75,252,7,115,226,209,70,132,70,88,108,152,167,
8

9,17,217,99,22,191,216,69,26,255,126,56,3,206,77,50,84,193,10,7,64,244,173,
1

62,72,84,162,27,245,33,133,249,201,9,128,78,135,74,115,135,26,237,12,147,89 ,

231,44,17,174,195,142,232,165,52,130,113,7,101,136,93,110,253,46,82,211,122 ,

241,2,77,132,103,91,167,105,123,80,50,237,29,33,129,202,217,38,63,39,104,17
1
,

10,133,65,109,230,142,59,79,43,83,80,159,47,185,96,177,126,155,82,29,122,9
2
,

100,40,21,125,19,70,93,247,11,46,26,35,227,138,137,108,58,19,16,115,24,236 ,

99,8,151,209,195,38,47,95,47,231,102,80,105,239,161,166,55,244,195,164,245,
5

0,218,158,136,143,99,97,144,69,68,196,141,144,208,125,79,213,135,36,148,38,
6

2,35,30,82,4,180,59,66,219,233,122,244,220,147,114,191,67,195,112,180,169,2
1

4,112,170,44,170,168,163,6,90,132,124,156,76,29,52,38,237,138,177,14,130,24
8
,

20,238,112,49,137,101,48,85,232,241,3,213,150,10,3,11,217,52,45,22,101,226 ,

23,212,121,237,254,90,245,172,199,255,68,20,75,26,136,145,93,251,229,34,199 ,

48,215,103,179,63,190,196,111,206,90,195,211,11,226,207,148,181,36,165,89,1
3

3,71,247,207,237,251,159,129,125,209,105,239,100,242,102,116,169,166,70,37,
9

6,218,232,218,37,139,221,63,180,113,190,173,120,5,31,146,19,217,89,255,196,
4

4,125,204,218,129,97,141,101,53,143,127,245,142,66,112,96,128,87,61,106,217 ,

217,98,71,184,115,182,247,25,131,165,226,4,186,132,16,101,130,223,56,238,14
9
,

230,30,19,49,149,179,184,177,34,44,11,222,253,95,180,54,74,205,107,75,252,
7
,

115,226,209,70,132,70,88,108,152,167,89,17,217,99,22,191,216,69,26,255,126 ,

56,3,206,77,50,84,193,10,7,64,244,173,162,72,84,162,27,245,33,133,249,201,9 ,

128,78,135,74,115,135,26,237,12,147,89,231,44,17,174,195,142,232,165,52,130 ,

113,7,101,136,93,110,253,46,82,211,122,241,2,77,132,103,91,167,105,123,80,5
0
,

237,29,33,129,202,217,38,63,39,104,171,10,133,65,109,230,142,59,79,43,83,8
0
,

159,47,185,96,177,126,155,82,29,122,92,100,40,21,125,19,70,93,247,11,46,26 ,

35,227,138,137,108,58,19,16,115,24,236,99,8,151,209,195,38,47,95,47,231,102 ,

80,105,239,161,166,55,244,195,164,245,50,218,158,136,143,99,97,144,69,68,19
6
,

141,144,208,125,79,213,135,36,148,38,62,35,30,82,4,180,59,66,219,233,122,2
4

4,220,147,114,191,67,195,112,180,169,214,112,170,44,170,168,163,6,90,132,12
4
,

156,76,29,52,38,237,138,177,14,130,248,20,238,112,49,137,101,48,85,232,241 ,

3,213,150,10,3,11,217,52,45,22,101,226,23,212,121,237,254,90,245,172,199,25
5
,

68,20,75,26,136,145,93,251,229,34,199,48,215,103,179,63,190,196,111,206,90 ,

195,211,11,226,207,148,181,36,165,89,133,71,247,207,237,251,159,129,125,209 ,

105,239,100,242,102,116,169,166,70,37,96,218,232,218,37,139,221,63,180,113,
1

90,173,120,5,31,146,19,217,89,255,196,44,125,204,218,129,97,141,101,53,143,
1

27,245,142,66,112,96,128,87,61,106,217,217,98,71,184,115,182,247,25,131,165 ,

226,4,186,132,16,101,130,223,56,238,149,230,30,19,49,149,179,184,177,34,44,
1

1,222,253,95,180,54,74,205,107,75,252,7,115,226,209,70,132,70,88,108,152,16
7
,

89,17,217,99,22,191,216,69,26,255,126,56,3,206,77,50,84,193,10,7,64,244,17
3
,

162,72,84,162,27,245,33,133,249,201,9,128,78,135,74,115,135,26,237,12,147,
8

9,231,44,17,174,195,142,232,165,52,130,113,7,101,136,93,110,253,46,82,211,1
2

2,241,2,77,132,103,91,167,105,123,80,50,237,29,33,129,202,217,38,63,39,104,
1

71,10,133,65,109,230,142,59,79,43,83,80,159,47,185,96,177,126,155,82,29,122 ,

92,100,40,21,125,19,70,93,247,11,46,26,35,227,138,137,108,58,19,16,115,24,2
3

6,99,8,151,209,195,38,47,95,47,231,102,80,105,239,161,166,55,244,195,164,24
5
,

50,218,158,136,143,99,97,144,69,68,196,141,144,208,125,79,213,135,36,148,3
8
,

62,35,30,82,4,180,59,66,219,233,122,244,220,147,114,191,67,195,112,180,169 ,

214,112,170,44,170,168,163,6,90,132,124,156,76,29,52,38,237,138,177,14,130,
2

48,20,238,112,49,137,101,48,85,232,241,3,213,150,10,3,11,217,52,45,22,101,2
2

6,23,212,121,237,254,90,245,172,199,255,68,20,75,26,136,145,93,251,229,34,1
9

9,48,215,103,179,63,190,196,111,206,90,195,211,11,226,207,148,181,36,165,89 ,

133,71,247,207,237,251,159,129,125,209,105,239,100,242,102,116,169,166,70,3
7
,

96,218,232,218,37,139,221,63,180,113,190,173,120,5,31,146,19,217,89,255,19
6
,

44,125,204,218,129,97,141,101,53,143,127,245,142,66,112,96,128,87,61,106,2
1

7,217,98,71,184,115,182,247,25,131,165,226,4,186,132,16,101,130,223,56,238,
1

49,230,30,19,49,149,179,184,177,34,44,11,222,253,95,180,54,74,205,107,75,25
2
,

7,115,226,209,70,132,70,88,108,152,167,89,17,217,99,22,191,216,69,26,255,1
2

6,56,3,206,77,50,84,193,10,7,64,244,173,162,72,84,162,27,245,33,133,249,201 ,
9,128,78,</TEXTAREA><BR>
</FORM>
</TD><TD ALIGN=CENTER BGCOLOR=WHITE WIDTH=50%>
</TD></TR></TABLE>
</BODY></HTML>


Date Subject Author
1/5/13
Read Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
David Bernier
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
Scott Berg
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/7/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/8/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
kiru.sengal@gmail.com
1/8/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
forbisgaryg@gmail.com
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
UpChunky
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/6/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT
1/5/13
Read Re: Just finished the fastest ever, general purpose sorting algorithm.
JT

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.