May 2022
1 / 7
May 2022
Jun 2022
leszekrz_53
May '22
1

Trochę trudu sobie kiedyś zadałem wyprowadzając to:
Zakładając, że mamy zbiór N losowych nieposortowanych liczb, jaka jest średnia odległość liczb od ich prawidłowych pozycji w tym zbiorze gdy zostanie posortowany?
Okazuje się, że jest to N /3 - 1/(3N), czyli:
N odl.
1 0
2 1/2
3 8/9
4 1+1/4
5 1+3/5
6 1+17/18
… …
12 3+35/36
… …
300 99 +899/900 …
czyli w praktyce już od N=6 można w uproszczeniu przyjąć, że ta odległość to 1/3N.
Pytanie: czy można to wykorzystać w algorytmach sortowania z jakąś korzyścią?

  • created

    May '22

  • last reply

    Jun '22
  • 6

    replies

  • 499

    views

  • 3

    users

  • 1

    like

  • 1

    link

narbej
Jun '22

Nie wiem. Ja w takiej sytuacji wykorzystałbym magiczne 0 - sortowanie kubełkowe

leszekrz_53
Jun '22

W tej “1/3” nie ma założenia równomierności rozkładu, więc kubełkowe nie musi być optymalne.

korkirw
Jun '22

Jak to nie ma założenia jednostajności rozkładu? W takim razie jaki rozkład prawdopodobieństwa przyjąłeś dla otrzymanego przez Ciebie wyniku? Rozkład Gaussa? Rozkład Studenta? Jakiś inny? Dlaczego właśnie taki? Wydajne mi się, że jeśli nie ma dodatkowych informacji o rozkładzie liczb to rozkład równomierny jest najbardziej naturalny.
Ponadto nie przeliczałem tego, ale wydaje mi się, że właśnie dla rozkładu jednostajnego powinno wyjść to co Tobie.

leszekrz_53
Jun '22

Każdy rozkład da w wyniku liczby uszeregowane od 1 do N. w sensie miejsca w zbiorze. Zamieszczę wyprowadzenie za kilka dni jak wrócę z urlopu.

leszekrz_53
Jun '22

Zamieszczam krótki program potwierdzający prawdziwość powyższego dla różnych rozkładów i zakresów. Oraz przykładowe wyniki.
import random
def checkdisplacement(nums):
nums2=nums[:]
nums.sort()
le=len(nums)
sumpos=0
for i in range(le):
j=nums.index(nums2[i])
sumpos+=abs(j-i)
rd=sumpos/le
rdr=rd/le
rc=le/3.-1./(3.*le)
rcr=rc/le
return rdr,rcr
nums=[random.uniform(0.,1.) for i in range(10000)]
print(‘Uniform: ‘,’\t’, checkdisplacement(nums))
nums=[random.triangular(-2.,2.) for i in range(10000)]
print(‘Triangular: ‘,’\t’, checkdisplacement(nums))
nums=[random.gauss(3.,1.) for i in range(10000)]
print(‘Gauss: ‘,’\t’, checkdisplacement(nums))
nums=[random.lognormvariate(10.,1.) for i in range(10000)]
print(‘Lognormal: ‘,’\t’, checkdisplacement(nums))

Uniform: (0.33353726, 0.33333333000000004)
Triangular: (0.33425552, 0.33333333000000004)
Gauss: (0.33084124000000004, 0.33333333000000004)
Lognormal: (0.33409481999999996, 0.33333333000000004)

Uniform: (0.33265344, 0.33333333000000004)
Triangular: (0.33485062, 0.33333333000000004)
Gauss: (0.33356048, 0.33333333000000004)
Lognormal: (0.33240596, 0.33333333000000004)

Uniform: (0.33198692, 0.33333333000000004)
Triangular: (0.33297762, 0.33333333000000004)
Gauss: (0.33546868, 0.33333333000000004)
Lognormal: (0.33468774, 0.33333333000000004)

Uniform: (0.3341877, 0.33333333000000004)
Triangular: (0.33146770000000003, 0.33333333000000004)
Gauss: (0.33054766, 0.33333333000000004)
Lognormal: (0.33670076, 0.33333333000000004)

leszekrz_53
Jun '22

Nie doczytałem jak wklejać kod.
Link do ideone:

Swoją drogą to można by to wykorzystać do testowanie doskonałości generatorów liczb przypadkowych.