Bubble-sorting digits
Bubble
sort, sometimes
referred to as sinking sort, is a simple sorting algorithm that
repeatedly steps through the input list element by element, comparing the
current element with the one after it, swapping their values if needed. These
passes through the list are repeated until no swaps have to be performed during
a pass, meaning that the list has become fully sorted. The algorithm, which is
a comparison sort, is named for the way the larger elements "bubble"
up to the top of the list. This simple algorithm performs poorly in real world.
[Wikipedia]
If
we bubble-sort 2024 we get 0224 in 1 swap. We could then assign 1 to
2024.
We
see that every integer can be bubble-tagged this way. The list starts:
n bubble-tag
0 ->
0
1 ->
0
2 ->
0
3 ->
0
...
9 ->
0
10 -> 1
11 -> 0
12 -> 0
13 -> 0
...
19 -> 0
20 -> 1
21 -> 1
22 -> 0
...
97 -> 1
98 -> 1
99 -> 0
100
-> 2
101
-> 1
102
-> 1
103
-> 1
...
109
-> 1
110
-> 2
111
-> 0
112
-> 0
...
What about adding to n its bubble-tag
to form k and iterate? The fate of the first 100 natural numbers is a
bit dull (they all enter rapidly into the loop [k, k, k, k,
k, …]
I guess from 100 on we might have a few
things to say:
S = 100, 102, 103, 104, 105, 106, 107, 108,
109, 110, 112, 112, 112, … <-- loop
T = 101, 102, 103, 104, 105, 106, 107, 108,
109, 110, 112, 112, 112, … <-- loop
U = 111, 111, 111, … <-- loop
...
We see above that n = 100 and n
= 101 produce 10 distinct ks (distinct from n), but n =
111 produces none.
The sequence V(n)
could then assign to each n the number of such distinct ks
produced. We would have this table:
n successive ks V(n)
0 ->
0, 0, 0, 0, 0, ... 0
1 ->
0, 0, 0, 0, 0, ... 1
2 ->
0, 0, 0, 0, 0, ... 1
3 ->
0, 0, 0, 0, 0, ... 1
...
9 ->
0, 0, 0, 0, 0, ... 0
10 -> 11, 11, 11, 11, ... 1
11 -> 11, 11, 11, 11, ... 0
12 -> 12, 12, 12, 12, ... 0
13 -> 13, 13, 13, 13, ... 0
...
19 -> 19, 19, 19, 19, ... 0
20 -> 21, 22, 22, 22, ... 2
21 -> 22, 22, 22, 22, ... 1
22 -> 22, 22, 22, 22, ... 0
...
97 -> 98, 99, 99, 99, ... 2
98 -> 99, 99, 99, 99, ... 1
99 -> 99, 99, 99, 99, ... 0
100
-> 102, 103, (see S above), ... 10
101
-> 102, 103, (see S above), ... 10
102
-> 103 --> 112, 112, 112, ... 9
103
-> 104 --> 112, 112, 112, ... 8
104
-> 105 --> 112, 112, 112, ... 7
...
109
-> 110, 112, 112, 112, ... 2
110
-> 112, 112, 112, 112, ... 1
111
-> 111, 111, 111, 111, ... 0
112
-> 112, 112, 112, 112, ... 0
...
2024
-> 2025, 2026, 2027, 2028, 2029, 2030, 2033, 2034, 2035, 2036, 2037, 2038,
2039, 2040, 2043, 2044, 2045, 2046, 2047, 2048, 2049, 2050, 2053, 2054, 2055,
2056, 2057, 2058, 2059, 2060, 2063, ...
[and so on, until a possible 2222 (or 2223,
or 2224) which should fix the end value of V(2024).]
Question
Will the V(n) graph have a fractal look?
____________________
Next day update
... Yes, says Jean-Marc Falcoz – increasing sort graphs hereunder (115 terms, 1150 and 11500)
JMF
> Je suis allé jusqu’à 11500 pour chaque tri. Dans cette plage, les valeurs les plus élevées sont, pour un tri croissant {n,V(n)} :
{9984,466},{9983,466},{9982,466},{9981,466},{9979,467},{9978,467},{9977,467},{9976,467},{9974,468},{9973,468},{9972,468},{9971,468},{9969,469},{9968,469},{9967,469},{9964,470},{9963,470},{9962,470},{9958,471},{9953,472}
... avec, par exemple pour le dernier :
{9953,9958,9962,9967,9971,9976,9981,9986,9991,9994,9997,10000,10004,10007,10010,10014,10016,10018,10020,10024,10026,10028,10030,10034,10036,10038,10040,10044,10046,10048,10050,10054,10057,10059,10061,10064,10067,10069,10071,10074,10077,10079,10081,10084,10087,10090,10094,10097,10100,10105,10108,10111,10112,10113,10114,10115,10116,10117,10118,10119,10120,10124,10125,10126,10127,10128,10129,10130,10134,10135,10136,10137,10138,10139,10140,10144,10145,10146,10147,10148,10149,10150,10154,10156,10157,10158,10159,10160,10164,10166,10167,10168,10169,10170,10174,10176,10178,10179,10180,10184,10186,10188,10189,10190,10194,10196,10198,10200,10205,10208,10211,10214,10216,10218,10220,10224,10225,10226,10227,10228,10229,10230,10234,10235,10236,10237,10238,10239,10240,10244,10245,10246,10247,10248,10249,10250,10254,10256,10257,10258,10259,10260,10264,10266,10267,10268,10269,10270,10274,10276,10278,10279,10280,10284,10286,10288,10289,10290,10294,10296,10298,10300,10305,10308,10311,10314,10316,10318,10320,10325,10327,10329,10331,10334,10335,10336,10337,10338,10339,10340,10344,10345,10346,10347,10348,10349,10350,10354,10356,10357,10358,10359,10360,10364,10366,10367,10368,10369,10370,10374,10376,10378,10379,10380,10384,10386,10388,10389,10390,10394,10396,10398,10400,10405,10408,10411,10414,10416,10418,10420,10425,10427,10429,10431,10435,10437,10439,10441,10444,10445,10446,10447,10448,10449,10450,10454,10456,10457,10458,10459,10460,10464,10466,10467,10468,10469,10470,10474,10476,10478,10479,10480,10484,10486,10488,10489,10490,10494,10496,10498,10500,10505,10508,10511,10514,10517,10519,10521,10525,10527,10529,10531,10535,10537,10539,10541,10545,10547,10549,10551,10554,10557,10558,10559,10560,10564,10567,10568,10569,10570,10574,10577,10578,10579,10580,10584,10587,10589,10590,10594,10597,10599,10600,10605,10609,10612,10615,10618,10620,10625,10628,10630,10635,10638,10640,10645,10648,10650,10655,10658,10660,10664,10667,10668,10669,10670,10674,10677,10678,10679,10680,10684,10687,10689,10690,10694,10697,10699,10700,10705,10709,10712,10715,10718,10720,10725,10728,10730,10735,10738,10740,10745,10748,10750,10755,10758,10760,10765,10769,10771,10774,10777,10778,10779,10780,10784,10787,10789,10790,10794,10797,10799,10800,10805,10809,10812,10815,10818,10820,10825,10828,10830,10835,10838,10840,10845,10848,10850,10855,10858,10860,10865,10869,10871,10875,10879,10881,10884,10887,10890,10894,10897,10900,10905,10909,10912,10915,10918,10921,10925,10928,10931,10935,10938,10941,10945,10948,10951,10955,10958,10961,10965,10969,10971,10975,10979,10981,10985,10989,10991,10994,10997,11000,11006,11010,11015,11017,11019,11021,11024,11026,11028,11030,11035,11037,11039,11041,11044,11046,11048,11050,11055,11057,11059,11061,11064,11067,11069,11071,11074,11077,11079,11081,11084,11087,11090,11095,11098,11101,11104,11107,11110,11114,11114,...}
Et pour un tri décroissant {n,V(n)} :
{11117,1911},{11112,1911},{11113,1912},{11108,1912},{11109,1913},{11104,1913},{11105,1914},{11098,1914},{11099,1915},{11092,1915},{11093,1916},{11086,1916},{11090,1917},{11087,1917},{11079,1917},{11084,1918},{11073,1918},{11070,1919},{11064,1920},{11057,1921}
... avec, par exemple pour le dernier :
{11057,11064,11070,11073,11079,11086,11092,11098,11104,11108,11112,11116,11120,11123,11130,11133,11139,11146,11153,11159,11166,11172,11178,11185,11191,11194,11200,11202,11207,11213,11219,11225,11233,11241,11246,11255,11263,11271,11276,11284,11292,11299,11307,11313,11318,11324,11332,11338,11346,11355,11363,11370,11375,11383,11390,11395,11403,11408,11414,11419,11425,11433,11439,11447,11455,11463,11470,11475,11483,11490,11495,11503,11508,11514,11519,11525,11532,11538,11546,11554,11560,11565,11572,11579,11588,11596,11604,11609,11615,11620,11624,11631,11635,11642,11648,11656,11663,11669,11677,11685,11692,11699,11707,11712,11717,11722,11728,11736,11743,11749,11757,11764,11770,11774,11780,11785,11792,11799,11807,11812,11817,11822,11828,11835,11842,11848,11855,11861,11865,11871,11875,11881,11885,11891,11896,11903,11908,11913,11918,11923,11930,11934,11941,11945,11952,11958,11965,11971,11975,11981,11985,11991,11995,12001,12004,12009,12014,12020,12023,12030,12034,12042,12048,12056,12064,12071,12076,12083,12090,12094,12101,12103,12108,12113,12118,12123,12130,12134,12142,12148,12156,12164,12171,12175,12182,12188,12195,12202,12206,12212,12216,12222,12226,12233,12241,12246,12255,12263,12271,12276,12284,12292,12298,12306,12313,12319,12326,12334,12343,12351,12357,12367,12377,12386,12395,12404,12410,12413,12419,12426,12434,12442,12448,12457,12467,12477,12486,12495,12504,12510,12513,12519,12526,12534,12542,12548,12557,12566,12575,12583,12591,12597,12606,12612,12617,12624,12631,12636,12644,12651,12656,12664,12671,12677,12686,12694,12702,12707,12713,12719,12726,12733,12740,12745,12753,12760,12765,12772,12778,12787,12795,12803,12809,12816,12822,12827,12834,12842,12848,12856,12864,12871,12876,12883,12890,12896,12904,12910,12913,12919,12925,12932,12938,12946,12954,12961,12966,12973,12980,12985,12992,12998,13005,13010,13012,13017,13023,13029,13036,13043,13049,13057,13065,13072,13078,13086,13093,13099,13106,13111,13112,13116,13121,13124,13131,13134,13141,13145,13153,13159,13167,13175,13182,13188,13195,13202,13206,13212,13216,13222,13226,13233,13239,13247,13256,13265,13273,13280,13285,13293,13300,13302,13306,13312,13316,13322,13326,13333,13337,13344,13352,13358,13367,13376,13384,13392,13398,13406,13413,13418,13425,13433,13438,13446,13455,13464,13472,13479,13489,13499,13508,13515,13521,13525,13532,13537,13545,13553,13559,13568,13578,13588,13597,13606,13612,13617,13624,13631,13635,13642,13648,13657,13666,13673,13680,13686,13694,13702,13707,13713,13718,13725,13732,13737,13744,13751,13756,13764,13771,13776,13783,13790,13796,13804,13810,13813,13818,13824,13831,13835,13842,13848,13856,13864,13871,13876,13883,13889,13898,13906,13912,13917,13923,13929,13936,13943,13949,13957,13965,13972,13978,13986,13993,13999,14006,14011,14014,14019,14025,14032,14037,14044,14049,14056,14064,14070,14074,14080,14084,14090,14094,14100,14101,14103,14107,14112,14116,14121,14124,14130,14133,14138,14145,14152,14158,14166,14173,14179,14187,14194,14200,14202,14206,14212,14216,14222,14226,14233,14239,14247,14255,14263,14270,14275,14283,14290,14295,14303,14307,14313,14317,14323,14328,14335,14342,14347,14355,14363,14369,14378,14387,14395,14403,14407,14413,14417,14423,14428,14435,14442,14446,14453,14459,14468,14477,14485,14493,14499,14507,14514,14519,14526,14534,14540,14544,14549,14557,14566,14575,14583,14590,14596,14605,14611,14614,14619,14626,14633,14638,14646,14653,14659,14668,14677,14686,14694,14701,14705,14711,14714,14719,14726,14733,14738,14746,14753,14759,14768,14777,14784,14791,14797,14805,14811,14814,14819,14826,14833,14838,14845,14852,14858,14866,14873,14879,14888,14895,14903,14908,14914,14919,14925,14932,14937,14944,14949,14956,14964,14970,14975,14982,14988,14995,15002,15006,15011,15014,15019,15025,15031,15035,15041,15045,15051,15055,15060,15064,15070,15074,15080,15084,15090,15094,15100,15101,15103,15107,15112,15116,15121,15124,15130,15133,15138,15145,15151,15154,15159,15166,15173,15179,15187,15194,15200,15202,15206,15212,15216,15222,15226,15233,15239,15247,15255,15261,15266,15274,15281,15286,15294,15301,15304,15309,15315,15320,15323,15328,15335,15341,15345,15352,15357,15365,15372,15378,15387,15395,15402,15406,15412,15416,15422,15426,15433,15437,15444,15448,15455,15461,15466,15474,15480,15485,15492,15498,15506,15512,15516,15522,15526,15533,15537,15544,15548,15555,15559,15566,15574,15580,15585,15591,15596,15604,15609,15616,15622,15627,15635,15641,15645,15651,15655,15660,15665,15671,15677,15686,15694,15701,15705,15710,15713,15718,15725,15731,15735,15741,15745,15751,15755,15760,15765,15771,15776,15783,15790,15796,15804,15809,15816,15822,15827,15834,15840,15844,15849,15857,15864,15870,15875,15881,15886,15893,15900,15903,15908,15914,15919,15925,15931,15935,15941,15945,15951,15955,15960,15965,15971,15976,15983,15989,15997,16004,16008,16013,16018,16024,16030,16033,16038,16045,16051,16055,16060,16063,16068,16075,16081,16086,16092,16098,16105,16109,16114,16118,16123,16129,16136,16142,16147,16154,16159,16166,16171,16175,16181,16185,16191,16195,16201,16204,16209,16215,16220,16223,16229,16236,16243,16249,16257,16265,16271,16276,16283,16290,16295,16302,16306,16311,16313,16317,16323,16328,16335,16341,16345,16352,16357,16365,16371,16376,16383,16389,16398,16406,16411,16413,16417,16423,16428,16435,16441,16444,16448,16455,16461,16465,16471,16476,16483,16489,16498,16506,16511,16513,16517,16523,16528,16535,16540,16543,16547,16554,16558,16565,16570,16575,16581,16586,16593,16599,16607,16613,16617,16623,16628,16635,16640,16643,16647,16654,16658,16665,16669,16676,16682,16688,16696,16702,16707,16713,16718,16725,16731,16735,16741,16745,16751,16755,16760,16764,16769,16777,16784,16791,16797,16805,16810,16813,16818,16824,16830,16834,16840,16844,16849,16857,16864,16869,16877,16884,16890,16896,16903,16908,16914,16919,16925,16931,16935,16941,16945,16951,16955,16960,16964,16969,16976,16982,16988,16995,17001,17004,17008,17013,17018,17024,17030,17033,17038,17045,17051,17055,17060,17063,17068,17075,17080,17084,17090,17094,17100,17101,17103,17107,17111,17112,17116,17120,17123,17129,17136,17142,17147,17153,17158,17165,17170,17173,17178,17185,17191,17195,17201,17204,17209,17215,17220,17223,17229,17236,17243,17249,17257,17264,17270,17274,17280,17285,17292,17298,17306,17311,17313,17317,17322,17326,17332,17336,17342,17347,17354,17360,17364,17370,17374,17380,17385,17392,17398,17406,17411,17413,17417,17422,17426,17432,17436,17442,17446,17452,17457,17464,17469,17477,17483,17489,17498,17506,17511,17513,17517,17522,17526,17532,17536,17542,17546,17552,17556,17562,17567,17574,17579,17587,17594,17600,17602,17606,17610,17612,17616,17620,17623,17628,17635,17640,17643,17647,17653,17657,17663,17667,17673,17678,17686,17692,17698,17706,17710,17712,17716,17720,17723,17728,17735,17740,17743,17747,17752,17756,17761,17764,17768,17775,17779,17786,17792,17798,17806,17811,17814,17819,17826,17832,17837,17843,17848,17855,17860,17864,17869,17877,17882,17888,17895,17902,17907,17912,17917,17922,17927,17933,17938,17945,17951,17955,17960,17964,17969,17976,17981,17986,17992,17998,18005,18009,18014,18019,18025,18031,18035,18041,18045,18051,18055,18060,18063,18068,18074,18079,18086,18091,18096,18102,18106,18110,18111,18112,18116,18120,18123,18129,18136,18142,18147,18153,18158,18164,18169,18176,18181,18184,18189,18196,18202,18206,18211,18213,18218,18223,18229,18236,18243,18249,18257,18264,18270,18274,18280,18284,18290,18295,18302,18306,18311,18313,18317,18322,18326,18332,18336,18342,18347,18354,18360,18364,18370,18374,18380,18384,18390,18395,18402,18406,18411,18413,18417,18422,18426,18432,18436,18442,18446,18452,18457,18464,18469,18477,18483,18488,18494,18500,18502,18506,18511,18513,18517,18522,18526,18532,18536,18542,18546,18552,18556,18562,18567,18574,18579,18587,18593,18599,18607,18612,18616,18620,18623,18628,18634,18639,18646,18651,18654,18658,18664,18668,18674,18679,18687,18693,18699,18707,18711,18713,18717,18721,18724,18729,18736,18741,18744,18748,18754,18758,18764,18768,18774,18778,18784,18789,18797,18803,18807,18811,18813,18817,18821,18824,18829,18836,18841,18844,18848,18853,18857,18862,18866,18870,18873,18877,18881,18884,18888,18892,18898,18904,18909,18915,18920,18924,18930,18934,18940,18944,18949,18956,18962,18967,18973,18978,18984,18989,18996,19002,19006,19010,19012,19017,19022,19027,19033,19038,19044,19049,19055,19060,19063,19068,19074,19079,19085,19090,19093,19098,19103,19107,19111,19112,19116,19120,19123,19129,19135,19141,19144,19149,19155,19160,19163,19168,19174,19179,19185,19190,19193,19198,19203,19208,19213,19218,19223,19229,19235,19242,19247,19254,19260,19264,19270,19274,19280,19284,19290,19294,19300,19302,19306,19311,19313,19317,19322,19326,19332,19336,19342,19347,19354,19360,19364,19370,19374,19380,19384,19390,19394,19400,19402,19406,19411,19413,19417,19422,19426,19432,19436,19442,19446,19452,19457,19464,19469,19476,19482,19487,19493,19498,19504,19508,19513,19517,19522,19526,19532,19536,19542,19546,19552,19556,19562,19567,19574,19579,19586,19592,19597,19603,19607,19612,19616,19620,19623,19628,19634,19639,19645,19650,19653,19657,19663,19667,19673,19678,19685,19690,19694,19699,19705,19709,19714,19718,19723,19728,19734,19739,19745,19750,19753,19757,19762,19766,19770,19773,19777,19781,19785,19790,19794,19799,19805,19809,19814,19818,19822,19826,19831,19834,19839,19845,19850,19853,19857,19862,19866,19870,19873,19877,19881,19884,19888,19892,19897,19902,19906,19910,19912,19916,19920,19923,19928,19933,19937,19942,19946,19951,19954,19958,19963,19967,19972,19976,19980,19983,19987,19991,19994,19998,20002,20005,20009,20013,20019,20025,20031,20036,20043,20049,20056,20063,20069,20076,20082,20087,20093,20099,20105,20110,20112,20117,20123,20130,20134,20142,20148,20156,20164,20171,20176,20183,20190,20194,20201,20204,20209,20214,20220,20222,20225,20231,20236,20244,20251,20256,20264,20271,20276,20283,20290,20294,20301,20305,20311,20315,20322,20326,20333,20339,20347,20356,20365,20373,20380,20385,20393,20400,20402,20406,20412,20417,20424,20430,20434,20441,20446,20454,20461,20467,20476,20484,20491,20497,20505,20510,20513,20519,20526,20533,20539,20547,20555,20561,20567,20576,20584,20591,20597,20605,20610,20613,20619,20626,20632,20637,20645,20652,20657,20665,20671,20677,20685,20692,20698,20706,20711,20715,20721,20725,20731,20736,20743,20749,20757,20764,20770,20774,20780,20785,20792,20798,20806,20811,20815,20821,20825,20831,20836,20843,20849,20857,20864,20870,20874,20880,20884,20890,20895,20902,20906,20911,20915,20921,20925,20931,20936,20943,20949,20956,20963,20969,20976,20982,20987,20993,20999,21005,21009,21013,21018,21023,21029,21035,21042,21047,21054,21060,21063,21069,21076,21082,21087,21093,21099,21105,21109,21113,21117,21121,21123,21129,21135,21142,21147,21154,21160,21163,21169,21176,21182,21187,21193,21199,21205,21210,21211,21212,21215,21220,21222,21225,21231,21235,21243,21250,21254,21261,21265,21272,21277,21284,21291,21295,21302,21306,21312,21316,21322,21326,21333,21339,21347,21356,21365,21373,21380,21385,21393,21400,21402,21406,21412,21416,21422,21426,21433,21439,21447,21455,21463,21470,21475,21483,21490,21495,21503,21508,21514,21519,21525,21531,21535,21542,21547,21555,21561,21566,21574,21581,21586,21594,21601,21604,21609,21615,21620,21623,21629,21636,21643,21649,21657,21665,21671,21676,21683,21690,21695,21702,21706,21711,21713,21718,21724,21730,21734,21741,21745,21752,21757,21764,21770,21774,21780,21785,21792,21798,21806,21811,21813,21818,21823,21829,21836,21843,21849,21857,21864,21870,21874,21880,21884,21890,21895,21902,21906,21911,21913,21918,21923,21929,21935,21942,21947,21954,21960,21964,21970,21974,21980,21984,21990,21994,22000,22000,...}
Beautiful, thank you Jean-Marc!
Four interesting sequences about sorting that are already present in the OEIS:
I) Numerator of average number of swaps needed to bubble sort a string of n distinct letters --> https://oeis.org/A064038
II) Sort-then-add sequence: a(n+1) = a(n) + sort(a(n)) --> https://oeis.org/A033860
III) a(n) = n plus the sorted version of the base-10 digits of n --> https://oeis.org/A070196
IV) Arrange digits of n in increasing order, then (for n > 0) omit the zeros --> https://oeis.org/A004185
[this last sequence (by Neil Sloane) has the hereunder nice fractal graph]
(there is a follow-up of this page there)
Commentaires
Enregistrer un commentaire