Algorytmy i Struktury Danych - Wyszukiwanie mediany

Pierwsze nasuwające się rozwiązanie jest następujące:

Posortować zbiór rosnąco. Zwrócić element na pozycji ⁿ/₂ (dla n nieparzystego – mediana, dla n parzystego – mediana dolna).

Koszt czasowy zależy od zastosowanego algorytmu sortującego. Zwykle wykorzystuje się Sortowanie Szybkie (ang. Quick Sort), opracowane przez prof. Tony'ego Hoare'a. Algorytm ten sortuje w czasie liniowo logarytmicznym – O(n log n). Zaletą tego sposobu jest to, iż wiele współczesnych języków programowania posiada w swoich bibliotekach funkcję sortującą qsort(), która wykorzystuje ten właśnie algorytm. Wadą z kolei jest to, iż do otrzymania wartości jednego elementu musimy sortować cały zbiór danych.

W podanym poniżej algorytmie sortowania szybkiego wykorzystujemy funkcję Dziel_na_partycję(Z, i_p, i_k), którą opisaliśmy dokładnie w poprzednim rozdziale. Funkcja ta dzieli partycję zbioru Z określoną dwoma indeksami i_p oraz i_k na dwie mniejsze partycje. Zwraca indeks podziałowy i_v. Pierwsza partycja zawiera elementy od i_p do i_v - 1, a druga od i_v do i_k. Elementy w partycji pierwszej są niewiększe od elementów w partycji drugiej.

Algorytm szybkiego sortowania i znajdowania mediany

Wejście:

n : liczba elementów w zbiorze Z, n ∈ N.
Z : tablica (n+1)-elementowa odwzorowująca zbiór Z, w który sortujemy. Na pozycji Z[n] należy umieścić wartownika o wartości większej od każdego elementu zbioru.

Wyjście:

Mediana zbioru Z.

Zmienne pomocnicze:

i_v : zawiera pozycję elementu zwrotnego, i_v ∈ C.
v : wartość elementu zwrotnego.
i, j : indeksy w tablicy Z; i, j ∈ C.
i_p : indeks początku partycji, i_p ∈ C.
i_k : indeks końca partycji, i_k ∈ C.

Lista kroków funkcji Dziel_na_partycje(Z, i_p, i_k):

K01: v ← Z[i_p]     ; zapamiętujemy wartość elementu zwrotnego
K02: i ← i_p        ; indeksem i będziemy szukali elementów ≥ v
K03: j ← i_k + 1    ; indeksem j będziemy szukali elementów ≤ v
K04: Dopóki i < j, ; w pętli elementy większe umieszczamy
     wykonuj kroki K05…K10 ; w Z_P, a mniejsze w Z_LK05:   i ← i + 1   ; przesuwamy się na następną pozycję w Z_LK06:   Jeśli Z[i] < v, ; szukamy elementu, który nie należy do Z_L
       to idź do kroku K05
K07:   j ← j - 1   ; przesuwamy się na poprzednią pozycję w Z_PK08:   Jeśli Z[j] > v, ; szukamy elementu, który nie należy do Z_P
       to idź do kroku K07
K09:   Jeśli i < j,    ; znalezione elementy zamieniamy miejscami
       to Z[i] ↔ Z[j]
K10:   Z[i_p] ← Z[j] ; zwalniamy pozycję elementu zwrotnego
K11: Z[j] ← v       ; na zwolnionej pozycji umieszczamy element zwrotny
K12: Zakończ z wynikiem j ; kończymy zwracając pozycję elementu zwrotnego

Lista kroków: funkcji rekurencyjnej Sortuj_szybko(Z, i_p, i_k)

K01: i_v ← Dziel_na_partycje(Z, i_p, i_k) ; wyznaczamy punkt podziałowy
K02: Jeśli i_p < i_v - 1, ; sortujemy rekurencyjnie pierwszą partycję
     to Sortuj_szybko(Z, i_p, i_v - 1)
K03: Jeśli i_k > i_v + 1, ; sortujemy rekurencyjnie drugą partycję
     to Sortuj_szybko(Z, i_v + 1, i_k)
K04: Zakończ

Lista kroków:

K01: Z[n] ← Największa liczba ; na ostatniej pozycji umieszczamy wartownika
K02: Sortuj_szybko(Z, 0, n-1) ; sortujemy cały zbiór
K03: Jeśli n mod 2 = 1,       ; zwracamy medianę zwykłą
     to zakończ z wynikiem Z[n shr 1]
K04  Zakończ z wynikiem: (Z[(n shr 1) - 1] + Z[n shr 1]) : 2
                              ; mediana średnia z dolnej i górnej

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wypełnia tablicę 99 elementową Z liczbami pseudolosowymi z zakresu od 0 do 999, wyświetla ją, sortuje szybko, wyświetla posortowaną i zwraca medianę. Na wydruku zbioru posortowanego mediana znajduje się w środku trzeciego wiersza.

Pascal

// Wyszukiwanie mediany
// Data:   21.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 99;

// Funkcja dzieli podany zbiór Z na dwie partycje:
// ZL - elementy mniejsze od elementu zwrotnego
// ZP - elementy większe od elementu zwrotnego
// Zwraca pozycję elementu zwrotnego
//------------------------------------------------

function Dziel_na_partycje(var Z : array of integer;
                           ip, ik : integer) : integer;
var
  i, v, x : integer;
begin
  v := Z[ip]; i := ip; inc(ik);
  while i < ik do
  begin
    repeat inc(i);  until Z[i]  >= v;
    repeat dec(ik); until Z[ik] <= v;
    if i < ik then
    begin
      x := Z[i]; Z[i] := Z[ik]; Z[ik] := x;
    end;
  end;
  Z[ip] := Z[ik]; Z[ik] := v;
  Dziel_na_partycje := ik;
end;

// Procedura sortuje rosnąco podany zbiór
//---------------------------------------

procedure Sortuj_szybko(var Z : array of integer;
                        ip, ik : integer);
var
  iv : integer;
begin
  iv := Dziel_na_partycje(Z, ip, ik);
  if ip < iv - 1 then Sortuj_szybko(Z, ip, iv - 1);
  if ik > iv + 1 then Sortuj_szybko(Z, iv + 1, ik);
end;

var
  Z : array [0..N] of integer;
  i, ip, ik, k, pv : integer;
begin
  randomize;

  // Przygotowujemy tablicę Z[]

  for i := 0 to N-1 do Z[i] := random(1000);

  // Na końcu Z[] umieszczamy wartownika

  Z[N] := 1000;

  // Wyświetlamy Z[] przed sortowaniem

  for i := 0 to N-1 do write(Z[i]:4);
  writeln; writeln;

  // Sortujemy szybko tablicę Z[]

  Sortuj_szybko (Z, 0, N-1);

  // Wyświetlamy Z[] po sortowaniu

  for i := 0 to N-1 do write(Z[i]:4);
  writeln; writeln;

  // Wyświetlamy medianę

  writeln(Z[N shr 1]);
  writeln;
  writeln;
end.

C++

// Wyszukiwanie mediany
// Data:   21.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 99;

// Funkcja dzieli podany zbiór Z na dwie partycje:
// ZL - elementy mniejsze od elementu zwrotnego
// ZP - elementy większe od elementu zwrotnego
// Zwraca pozycję elementu zwrotnego
//------------------------------------------------

int Dziel_na_partycje(int * Z, int ip, int ik)
{
  int i, v;

  v = Z[ip]; i = ip; ik++;
  while(i < ik)
  {
    while(Z[++i]  < v);
    while(Z[--ik] > v);
    if(i < ik) swap(Z[i],Z[ik]);
  }
  Z[ip] = Z[ik]; Z[ik] = v;
  return ik;
}

// Procedura sortuje rosnąco podany zbiór
//---------------------------------------

void Sortuj_szybko(int * Z, int ip, int ik)
{
  int iv = Dziel_na_partycje(Z, ip, ik);
  if(ip < iv - 1) Sortuj_szybko(Z, ip, iv - 1);
  if(ik > iv + 1) Sortuj_szybko(Z, iv + 1, ik);
}

int main()
{
  int Z[N + 1], i;

  srand(time(NULL));

  // Przygotowujemy tablicę Z[]

  for(i = 0; i < N; i++) Z[i] = rand() % 1000;

  // Na końcu Z[] umieszczamy wartownika

  Z[N] = 1000;

  // Wyświetlamy Z[] przed sortowaniem

  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl << endl;

  // Sortujemy szybko tablicę Z[]

  Sortuj_szybko(Z, 0, N-1);

  // Wyświetlamy Z[] po sortowaniu

  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl << endl;

  // Wyświetlamy medianę

  cout << Z[N >> 1] << endl << endl;
  return 0;
}

Basic

' Wyszukiwanie mediany
' Data:   21.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 99

' Funkcja dzieli podany zbiór Z na dwie partycje:
' ZL - elementy mniejsze od elementu zwrotnego
' ZP - elementy większe od elementu zwrotnego
' Zwraca pozycję elementu zwrotnego
'------------------------------------------------

Function Dziel_na_partycje (Z() As Integer,_
                            Byval ip As Integer,_
                            Byval ik As Integer)_
                            As Integer
  Dim As Integer i, v

  v = Z(ip): i = ip: ik += 1
  While i < ik
    Do: i  += 1: Loop Until Z(i)  >= v
    Do: ik -= 1: Loop Until Z(ik) <= v
    If i < ik Then Swap Z(i), Z(ik)
  Wend
  Z(ip) = Z(ik): Z(ik) = v
  Dziel_na_partycje = ik
End Function

' Procedura sortuje rosnąco podany zbiór
'---------------------------------------

Sub Sortuj_szybko (Z() As Integer,_
                   Byval ip As Integer,_
                   Byval ik As Integer)

  Dim iv As Integer

  iv = Dziel_na_partycje(Z(), ip, ik)
  If ip < iv - 1 Then Sortuj_szybko(Z(), ip, iv - 1)
  If ik > iv + 1 Then Sortuj_szybko(Z(), iv + 1, ik)
End Sub

Dim As Integer Z(N), i, ip, ik, k, pv

Randomize

' Przygotowujemy tablicę Z()

For i = 0 To N-1
  Z(i) = Cint(Rnd * 999)
Next

' Na końcu Z() umieszczamy wartownika

Z(N) = 1000

' Wyświetlamy Z() przed sortowaniem

For i = 0 To N-1
  Print Using "####";Z(i);
Next
Print: Print

' Sortujemy szybko tablicę Z()

Sortuj_szybko(Z(), 0, N-1)

' Wyświetlamy Z() po sortowaniu

For i = 0 To N-1
  Print Using "####";Z(i);
Next
Print: Print

' Wyświetlamy medianę

Print Z(N Shr 1)
Print
Print
End

Python (dodatek)

# Wyszukiwanie mediany
# Data:    2.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 99 # Liczba elementów

# Funkcja dzieli podany zbiór Z na dwie partycje:
# ZL - elementy mniejsze od elementu zwrotnego
# ZP - elementy większe od elementu zwrotnego
# Zwraca pozycję elementu zwrotnego
#------------------------------------------------

def Dziel_na_partycje(Z, ip, ik):
 
    v = Z[ip]
    i = ip
    ik += 1
    while i < ik:
        while  True:
            i  += 1
            if Z[i] >= v: break
        while True:
            ik -= 1
            if Z[ik] <= v: break
        if i < ik: Z[i],Z[ik] = Z[ik],Z[i]
    Z[ip],Z[ik] = Z[ik],v
    return ik

# Procedura sortuje rosnąco podany zbiór
#---------------------------------------

def Sortuj_szybko(Z, ip, ik):
    iv = Dziel_na_partycje(Z,ip,ik)
    if ip < iv - 1: Sortuj_szybko(Z,ip,iv-1)
    if ik > iv + 1: Sortuj_szybko(Z,iv+1,ik)
    return


Z = []

# Przygotowujemy tablicę Z[]

for i in range(N):
  Z.append(random.randrange(1000))

# Na końcu Z[] umieszczamy wartownika

Z.append(1000)

# Wyświetlamy Z[] przed sortowaniem

for i in range(N):
    print("%4d" % Z[i], end="")
print()
print()

# Sortujemy szybko tablicę Z[]

Sortuj_szybko(Z,0,N-1)

# Wyświetlamy Z[] po sortowaniu

for i in range(N):
    print("%4d" % Z[i], end="")
print()
print()

#' Wyświetlamy medianę

print(Z[N >> 1])
print()
print()

Wynik:

 386 896 738 974 812 400 714 757 637 772  14 575 645 635 841 768 525 827 206 721
 466 929 215 716 284 300 755 128 900 203 973   9 685  75 499 124 921 813 900 297
 935 440  13 906 692 427 470 475 985 622 296 891 563 233 770 170 928 740 461 179
 104 401 740 308 506 159 984 475 690 705 283 796  79 703 291 512 561 258 698 368
 474 965 891 250  68 331 215 907 620 188 154 478 158 884 855 876 658 221 707

   9  13  14  68  75  79 104 124 128 154 158 159 170 179 188 203 206 215 215 221
 233 250 258 283 284 291 296 297 300 308 331 368 386 400 401 427 440 461 466 470
 474 475 475 478 499 506 512 525 561 563 575 620 622 635 637 645 658 685 690 692
 698 703 705 707 714 716 721 738 740 740 755 757 768 770 772 796 812 813 827 841
 855 876 884 891 891 896 900 900 906 907 921 928 929 935 965 973 974 984 985

563

Na początek: podrozdziału strony

Lepszym podejściem do znajdowania mediany zbioru od jego sortowania jest zastosowanie prostszego algorytmu – Szybkiego Wyszukiwania (ang. Quick Search), który opisaliśmy dokładnie w poprzednim rozdziale. Szukanym elementem będzie oczywiście (ⁿ/₂ + 1)-szy największy element zbioru. Algorytm Szybkiego Wyszukiwania jest podobny w działaniu do algorytmu Szybkiego Sortowania. Różnica polega jedynie na tym, iż Szybkie Wyszukiwanie przetwarza zawsze tylko jedną z dwóch partycji, mianowicie tę, w której występuje poszukiwany element. Druga partycja pozostaje przetworzona tylko wstępnie. Algorytm Sortowania Szybkiego przetwarza do końca cały zbiór. W efekcie, chociaż klasa złożoności obu metod jest liniowo logarytmiczna O(n log n), to jednak Wyszukiwanie Szybkie da szybciej wynik od Szybkiego Sortowania.

Algorytm szybkiego wyszukiwania mediany

Wejście:

n : liczba elementów w zbiorze Z; n ∈ N.
Z : tablica (n+1)-elementowa odwzorowująca zbiór Z, w którym poszukujemy mediany. Na pozycji Z[n] należy umieścić wartownika o wartości większej od każdego elementu zbioru.

Wyjście:

Wartość mediany zbioru Z. Jeśli zbiór posiada parzystą liczbę elementów, to wynikiem jest mediana górna.

Zmienne pomocnicze:

m : pozycja mediany w tablicy Z; m ∈ C.
i_p : indeks początku partycji; i_p ∈ C.
i_k : indeks końca partycji; i_k ∈ C.
i, j : indeksy w tablicy Z; i, j ∈ C.
v : wartość elementu zwrotnego.

Lista kroków:

K01: m ← n shr 1   ; wyznaczamy docelową pozycję mediany
K02: Z[n] ← Największa liczba ; do zbioru wstawiamy wartownika
K03: i_p ← 0        ; partycja startowa obejmuje cały zbiór
     i_k ← n - 1
K04: v ← Z[i_p]     ; wybieramy element zwrotny
K05: i ← i_p; indeksem i poszukujemy elementów ≥ v
K06: j ← i_k + 1    ; indeksem j poszukujemy elementów ≤ v
K07: Dopóki i < j, ; w pętli zamieniamy elementy większe z mniejszymi
     wykonuj kroki K08…K12
K08:   i ← i + 1   ; szukamy elementów ≥ v
K09:   Jeśli Z[i] < v,
       to idź do kroku K08
K10:   j ← j - 1   ; teraz szukamy elementów ≤ v
K11:   Jeśli Z[j] > v,
       to idź do kroku K10
K12:   Jeśli i < j,   ; jeśli elementy są w złych partycjach,
       to Z[i] ↔ Z[j] ; zamieniamy je
K13: Z[i_p] ← Z[j] ; robimy miejsce pod v
K14: Z[j] ← v     ; v umieszczamy na początku drugiej partycji
K15: Jeśli j = m, ; sprawdzamy, czy znaleziono już medianę
     to zakończ z wynikiem Z[m]
K16: Jeśli m < j,   ; wybieramy jedną z dwóch partycji,
     to i_k ← j - 1  ; w której będziemy dalej szukać mediany
     inaczej i_p ← j + 1
K17: Idź do kroku K04 ; i kontynuujemy pętlę

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wypełnia tablicę 99 elementową Z liczbami pseudolosowymi z zakresu od 0 do 999, wyświetla ją, szybko wyszukuje medianę, wyświetla przetworzoną tablicę i zwraca medianę. Na wydruku zbioru przetworzonego mediana znajduje się w środku trzeciego wiersza. Zwróć uwagę, iż zbiór Z przetworzony tym algorytmem nie jest posortowany. Jednakże mediana znajduje się na właściwym miejscu – elementy wcześniejsze w zbiorze są od niej mniejsze (lub równe). Elementy dalsze w zbiorze są większe od mediany (lub równe).

Pascal

// Szybkie wyszukiwanie mediany
// Data:   21.05.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

const N = 99;

var
  Z : array [0..N] of integer;
  m, ip, ik, i, j, v, x : integer;

begin
  randomize;

  // Przygotowujemy tablicę Z[]

  for i := 0 to N-1 do Z[i] := random(1000);

  // Na końcu umieszczamy wartownika

  Z[N] := 1000;

  // Wyświetlamy tablicę Z[]

  for i := 0 to N-1 do write(Z[i]:4);

  writeln; writeln;

  // Ustalamy pozycję mediany w zbiorze

  m := N shr 1;

  // Szukamy mediany

  ip := 0; ik := N - 1;
  repeat
    v := Z[ip]; i := ip; j := ik + 1;
    while i < j do
    begin
      repeat inc(i); until Z[i] >= v;
      repeat dec(j); until Z[j] <= v;
      if i < j then
      begin
        x := Z[i]; Z[i] := Z[j]; Z[j] := x;
      end;
    end;
    Z[ip] := Z[j]; Z[j] := v;
    if m = j then break;
    if m < j then ik := j - 1 else ip := j + 1;
  until false;

  // Wyświetlamy tablicę Z[]

  for i := 0 to N-1 do write(Z[i]:4);
  writeln; writeln;

  // Wyświetlamy medianę

  writeln(Z[m]);
  writeln; writeln;
end.

C++

// Szybkie wyszukiwanie mediany
// Data:   21.05.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 99;

int main()
{
  int Z[N+1], m, ip, ik, i, j, v;

  srand(time(NULL));

  // Przygotowujemy tablicę Z[]

  for(i = 0; i < N; i++) Z[i] = rand()% 1000;

  // Na końcu umieszczamy wartownika

  Z[N] = 1000;

  // Wyświetlamy tablicę Z[]

  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl << endl;

  // Ustalamy pozycję mediany w zbiorze

  m = N >> 1;

  // Szukamy mediany

  ip = 0; ik = N - 1;
  for(;;)
  {
    v = Z[ip]; i = ip; j = ik + 1;
    while(i < j)
    {
      while(Z[++i] < v);
      while(Z[--j] > v);
      if(i < j) swap(Z[i], Z[j])
     
    }
    Z[ip] = Z[j]; Z[j] = v;
    if(m == j) break;
    if(m < j) ik = j - 1; else ip = j + 1;
  }

  // Wyświetlamy tablicę Z[]

  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl << endl;

  // Wyświetlamy medianę

  cout << Z[m] << endl << endl;
  return 0;
}

Basic

' Szybkie wyszukiwanie mediany
' Data:   21.05.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Const N = 99

Dim As Integer Z(N), m, ip, ik, i, j, v

Randomize

' Przygotowujemy tablicę Z()

For i = 0 To N-1
  Z(i) = Cint(Rnd * 999)
Next

' Na końcu umieszczamy wartownika

Z(N) = 1000

' Wyświetlamy tablicę Z()

For i = 0 To N-1
  Print Using "####";Z(i);
Next
Print: Print

' Ustalamy pozycję mediany w zbiorze

m = N Shr 1

' Szukamy mediany

ip = 0: ik = N - 1
Do
  v = Z(ip): i = ip: j = ik + 1
  While i < j
    Do: i += 1: Loop Until Z(i) >= v
    Do: j -= 1: Loop Until Z(j) <= v
    If i < j Then Swap Z(i),Z(j)
  Wend
  Z(ip) = Z(j): Z(j) = v
  If m = j Then Exit Do
  If m < j Then
    ik = j - 1
  Else
    ip = j + 1
  End If
Loop

' Wyświetlamy tablicę Z()

For i = 0 To N-1
  Print Using "####";Z(i);
Next
Print: Print

' Wyświetlamy medianę

Print Z(m)
Print: Print
End

Python (dodatek)

# Szybkie wyszukiwanie mediany
# Data:   21.05.2008
# (C)2020 mgr Jerzy Wałaszek
#-----------------------------

import random

N = 99
Z = []

# Przygotowujemy tablicę Z[]

for i in range(N):
    Z.append(random.randrange(1000))

# Na końcu umieszczamy wartownika

Z.append(1000)

# Wyświetlamy tablicę Z[]

for i in range(N):
    print("%4d" % Z[i], end="")
print()
print()

# Ustalamy pozycję mediany w zbiorze

m = N >> 1

# Szukamy mediany

ip,ik = 0,N - 1
while True:
    v,i,j = Z[ip],ip,ik+1
    while i < j:
        while True:
            i += 1
            if Z[i] >= v: break
        while True:
            j -= 1
            if Z[j] <= v: break
        if i < j: Z[i],Z[j] = Z[j],Z[i]
    Z[ip],Z[j] = Z[j],v
    if m == j: break
    if m < j:
        ik = j - 1
    else:
        ip = j + 1

# Wyświetlamy tablicę Z[]

for i in range(N):
    print("%4d" % Z[i], end="")
print()
print()

# Wyświetlamy medianę

print(Z[m])
print()
print()

Wynik:

 320  96 604  39 241 295 527 644 431 187 373 856 302 711 458 486 513 872 620 442
 550 135 672 334 925 629 522 993 829 509  95 400 653 947 838 287 140 699 215 804
 513 722 652 287 111 353 973 539 534 458 740 765 875 114 589 562 559  69 950 668
 755 596 856 443 879 216 112 411 764 212 887 816 223 292 243 873 564 840 921 569
 116 842 830 731 451 941 332 181 141 671 275  63 624 705  46 388 395 246 158

  95  96 158  39 241 295 246  46  63 187 275 141 302 181 116 243 292 223 212 112
 216 135  69 114 111 287 215 140 287 320 353 400 395 388 431 373 332 451 458 486
 411 442 443 334 458 509 513 522 513 527 740 765 875 629 589 562 559 672 950 668
 755 596 856 652 879 550 722 925 764 620 887 816 872 534 804 873 564 840 921 569
 539 842 830 731 699 941 604 711 856 671 829 838 624 705 644 947 653 973 993

527

Na początek: podrozdziału strony

Profesor Niklaus Wirth (twórca języków programowania Pascal, Modula 2, Oberon) w swojej książce pt. Algorytmy + Struktury Danych = Programy przedstawia interesujący algorytm wyszukiwania mediany zbioru, który jest wariacją algorytmu Szybkiego Wyszukiwania Tony'ego Hoare'a. Pod względem funkcjonalnym i klasy złożoności obliczeniowej oba algorytmy są równoważne. Dodatkowo w zbiorze Z nie musimy umieszczać wartownika.

Algorytm Wirtha szybkiego wyszukiwania mediany

Wejście:

n : liczba elementów w zbiorze Z.
Z : tablica n-elementowa odwzorowująca zbiór Z, w którym poszukujemy mediany.

Wyjście:

Mediana zbioru Z. Jeśli zbiór posiada parzystą liczbę elementów, to wynikiem jest mediana górna.

Zmienne pomocnicze:

m : indeks mediany.
i_p : indeks początku partycji, i_p ∈ C.
i_k : indeks końca partycji, i_k ∈ C.
i, j : indeksy w tablicy Z; i, j ∈ C.
v : wartość elementu zwrotnego.

Lista kroków:

K01: m ← n shr 1 ; wyznaczamy docelową pozycję mediany
K02: i_p ← 0      ; określamy partycję początkową
     i_k ← n - 1
K03: Dopóki i_p < i_k, ; szukamy m-tego najmniejszego elementu
     wykonuj kroki K04…K12
K04:   v ← Z[m]  ; podziału dokonujemy wg m-tego elementu zbioru
K05:   i ← i_p    ; indeksem i będziemy szukali elementów ≥ v
K06:   j ← i_k    ; indeksem j będziemy szukali elementów ≤ v
K07:   Dopóki Z[i] < v,  ; szukamy elementu nie pasującego
       wykonuj i ← i + 1 ; do dolnej partycji
K08:   Dopóki v < Z [j], ; szukamy elementu nie pasującego
       wykonuj j ← j - 1 ; do górnej partycji
K09:   Jeśli i ≤ j,   ; elementy zamieniamy ze sobą,
       to Z[i] ↔ Z[j] ; aby trafiły do właściwych
          i ← i + 1   ; partycji. Po zamianie indeksy i, j
          j ← j - 1   ; muszą być zmodyfikowane
K10:   Jeśli i ≤ j,
       to idź do kroku K07
K11:   Jeśli j < m, ; wybieramy nową partycję do
       to i_p ← i    ; poszukiwań mediany
K12:   Jeśli m < i,
       to i_k ← j
K13: Zakończ z wynikiem Z[m] ; mediana znaleziona

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wypełnia tablicę 99 elementową Z liczbami pseudolosowymi z zakresu od 0 do 999, wyświetla ją, wyszukuje medianę algorytmem Wirtha, wyświetla przetworzoną tablicę i zwraca medianę. Na wydruku zbioru przetworzonego mediana znajduje się w środku trzeciego wiersza.

Pascal

// Szybkie wyszukiwanie mediany
// Data:   22.05.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

const N = 99;

var
  Z : array [0..N-1] of integer;
  m, ip, ik, i, j, v, x : integer;

begin
  randomize;

  // Przygotowujemy tablicę Z[]

  for i := 0 to N-1 do Z[i] := random(1000);

  // Wyświetlamy tablicę Z[]

  for i := 0 to N-1 do write(Z[i]:4);

  writeln; writeln;

  // Ustalamy pozycję mediany w zbiorze

  m := N shr 1;

  // Szukamy mediany

  ip := 0; ik := N-1;
  while ip < ik do
  begin
    v := Z[m]; i := ip; j := ik;
    repeat
      while Z[i] < v do inc(i);
      while v < Z[j] do dec(j);
      if i <= j then
      begin
        x := Z[i]; Z[i] := Z[j]; Z[j] := x;
        inc(i); dec(j);
      end;
    until i > j;
    if j < m then ip := i;
    if m < i then ik := j;
  end;

  // Wyświetlamy tablicę Z[]

  for i := 0 to N-1 do write(Z[i]:4);
  writeln; writeln;

  // Wyświetlamy medianę

  writeln(Z[m]);
  writeln; writeln;
end.

C++

// Szybkie wyszukiwanie mediany
// Data:   22.05.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  const int N = 99;
 
  int Z[N-1], m, ip, ik, i, j, v, x;

  srand(time(NULL));

  // Przygotowujemy tablicę Z[]

  for(i = 0; i < N; i++)
    Z[i] = rand() % 1000;

  // Wyświetlamy tablicę Z[]

  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl << endl;

  // Ustalamy pozycję mediany w zbiorze

  m = N >> 1;

  // Szukamy mediany

  ip = 0; ik = N - 1;
  while(ip < ik)
  {
    v = Z[m]; i = ip; j = ik;
    do
    {
      while(Z[i] < v) i++;
      while(v < Z[j]) j--;
      if(i <= j)
      {
        swap(Z[i],Z[j]);
        i++; j--;
      }
    } while(i <= j);
    if(j < m) ip = i;
    if(m < i) ik = j;
  }

  // Wyświetlamy tablicę Z[]

  for(i = 0; i < N; i++)
    cout << setw(4) << Z[i];
  cout << endl << endl;

  // Wyświetlamy medianę

  cout << Z[m] << endl << endl << endl;
  return 0;
}

Basic

' Szybkie wyszukiwanie mediany
' Data:   22.05.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Const N = 99

Dim As Integer Z(N-1), m, ip, ik, i, j, v

Randomize

' Przygotowujemy tablicę Z()

For i = 0 To N-1
  Z[i] = Cint(Rnd * 999)
Next

' Wyświetlamy tablicę Z()

For i = 0 To N-1
  Print Using "####";Z(i);
Next
Print: Print

' Ustalamy pozycję mediany w zbiorze

m = N Shr 1

' Szukamy mediany

ip = 0: ik = N - 1
While ip < ik
  v = Z(m): i = ip: j = ik
  Do
    While Z(i) < v: i += 1: Wend
    While v < Z(j): j -= 1: Wend
    If i <= j Then
      Swap Z(i),Z(j)
      i += 1: j -= 1
    End If
  Loop Until i > j
  If j < m Then ip = i
  If m < i Then ik = j
Wend

' Wyświetlamy tablicę Z()

For i = 0 To N-1
  Print Using "####";Z(i);
Next
Print: Print

' Wyświetlamy medianę

Print Z(m)
Print: Print
End

Python (dodatek)

# Szybkie wyszukiwanie mediany
# Data:    3.03.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------

import random

N = 99
Z = []

# Przygotowujemy tablicę Z[]

for i in range(N):
    Z.append(random.randrange(1000))

# Wyświetlamy tablicę Z[]

for i in range(N):
    print("%4d" % Z[i], end="")
print()
print()

# Ustalamy pozycję mediany w zbiorze

m = N >> 1

# Szukamy mediany

ip,ik = 0,N-1
while ip < ik:
    v,i,j = Z[m],ip,ik
    while True:
        while Z[i] < v: i += 1
        while v < Z[j]: j -= 1
        if i <= j:
            Z[i],Z[j] = Z[j],Z[i]
            i += 1
            j -= 1
        if i > j: break
    if j < m: ip = i
    if m < i: ik = j

# Wyświetlamy tablicę Z[]

for i in range(N):
    print("%4d" % Z[i], end="")
print()
print()

# Wyświetlamy medianę

print(Z[m])
print()
print()

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Wyszukiwanie mediany

Problem

Rozwiązanie nr 1

Algorytm szybkiego sortowania i znajdowania mediany

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków funkcji Dziel_na_partycje(Z, i_p, i_k):

Lista kroków: funkcji rekurencyjnej Sortuj_szybko(Z, i_p, i_k)

Przykładowe programy

Rozwiązanie nr 2

Algorytm szybkiego wyszukiwania mediany

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 3

Algorytm Wirtha szybkiego wyszukiwania mediany

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Wyszukiwanie mediany

Problem

Rozwiązanie nr 1

Algorytm szybkiego sortowania i znajdowania mediany

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków funkcji Dziel_na_partycje(Z, ip, ik):

Lista kroków: funkcji rekurencyjnej Sortuj_szybko(Z, ip, ik)

Przykładowe programy

Rozwiązanie nr 2

Algorytm szybkiego wyszukiwania mediany

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 3

Algorytm Wirtha szybkiego wyszukiwania mediany

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Lista kroków funkcji Dziel_na_partycje(Z, i_p, i_k):

Lista kroków: funkcji rekurencyjnej Sortuj_szybko(Z, i_p, i_k)