Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #32856

Re: Sortowanie bąbelkowe

Show all headers | View raw

W dniu czwartek, 22 sierpnia 2019 10:57:40 UTC+2 użytkownik Maciej Sobczak napisał:
> Nudy jakieś, wszyscy na urlopach?
> W każdym razie, skoro ostatnio były tu fajne dyskusje o różnych językach programowania, to pozwolę sobie dla hecy pokazać sortowanie bąbelkowe w Wolframie.
> 
> Otóż jak wiadomo, pojedynczy krok sortowania polega na tym, że jeśli gdzieś jest para elementów w "niewłaściwej" kolejności, to trzeba je zamienić miejscami. A potem powtarzać to aż do skutku.
> 
> No to mamy, pojedynczy krok:
> 
> oneBubbleStep[lst_] := 
>  lst /. {pre___, a_, b_, post___} /; a > b -> {pre, b, a, post}
> 
> oneBubbleStep to funkcja, która ma jeden parametr, nazwany lst. Ta funkcja szuka wzorca:
> 
> {pre___, a_, b_, post___}
> 
> wzorzec ma być listą, składającą się z:
> 1. jakiegoś pre, zero lub więcej elementów
> 2. jakiegoś a
> 3. jakiegoś b
> 4. jakiegoś post, zero lub więcej elementów
> 
> i jeśli przypadkiem a > b, to znaleziony wzorzec ma być zamieniony na taki:
> 
> {pre, b, a, post}
> 
> czyli elementy a i b mają się zamienić miejscami. Jeśli wzorzec nie pasuje, to żadna zmiana nie jest wykonana. To zadziała zawsze, nawet na brzegach, np.:
> 
> oneBubbleStep[{10, 20, 40, 30, 50}]
> 
> {10, 20, 30, 40, 50}
> 
> I teraz biorę jakieś dane testowe:
> 
> testData = RandomSample[Range[10], 10]
> 
> {2, 10, 1, 3, 8, 9, 6, 4, 5, 7}
> 
> i aplikuję funkcję oneBubbleStep tak długo, aż wynik przestanie się zmieniać, pokazując po drodze wszystkie pośrednie wyniki (sformatowałem ręcznie):
> 
> FixedPointList[oneBubbleStep, testData]
> 
> {
>  {2, 10, 1, 3, 8, 9, 6, 4, 5, 7},
>  {2, 1, 10, 3, 8, 9, 6, 4, 5, 7},
>  {1, 2, 10, 3, 8, 9, 6, 4, 5, 7},
>  {1, 2, 3, 10, 8, 9, 6, 4, 5, 7},
>  {1, 2, 3, 8, 10, 9, 6, 4, 5, 7},
>  {1, 2, 3, 8, 9, 10, 6, 4, 5, 7},
>  {1, 2, 3, 8, 9, 6, 10, 4, 5, 7},
>  {1, 2, 3, 8, 6, 9, 10, 4, 5, 7},
>  {1, 2, 3, 6, 8, 9, 10, 4, 5, 7},
>  {1, 2, 3, 6, 8, 9, 4, 10, 5, 7},
>  {1, 2, 3, 6, 8, 4, 9, 10, 5, 7},
>  {1, 2, 3, 6, 4, 8, 9, 10, 5, 7},
>  {1, 2, 3, 4, 6, 8, 9, 10, 5, 7},
>  {1, 2, 3, 4, 6, 8, 9, 5, 10, 7},
>  {1, 2, 3, 4, 6, 8, 5, 9, 10, 7},
>  {1, 2, 3, 4, 6, 5, 8, 9, 10, 7},
>  {1, 2, 3, 4, 5, 6, 8, 9, 10, 7},
>  {1, 2, 3, 4, 5, 6, 8, 9, 7, 10},
>  {1, 2, 3, 4, 5, 6, 8, 7, 9, 10},
>  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
>  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
> }
> 
> Ten "program" ma swoją interpunkcję, która na pewno się tu komuś nie spodoba, ale ma ciekawą zaletę: odzwierciedla opis słowny. Fajne?

Rzeczywiście ładne.
Spośród rozwiązań na Rosetta Code to w Wolframie jest niewątpliwie najładniejsze:

bubbleSort[{w___, x_, y_, z___}] /; x > y := bubbleSort[{w, y, x, z}]
bubbleSort[sortedList_] := sortedList

Szkoda tylko, że taka brzydka interpunkcja ;]

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Sortowanie bąbelkowe Maciej Sobczak <see.my.homepage@gmail.com> - 2019-08-22 01:57 -0700
  Re: Sortowanie bąbelkowe godek.maciek@gmail.com - 2019-08-22 02:13 -0700
    Re: Sortowanie bąbelkowe Maciej Sobczak <see.my.homepage@gmail.com> - 2019-08-22 23:18 -0700
      Re: Sortowanie bąbelkowe godek.maciek@gmail.com - 2019-08-23 00:29 -0700
        Re: Sortowanie bąbelkowe Maciej Sobczak <see.my.homepage@gmail.com> - 2019-08-23 01:34 -0700

csiph-web