Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2023 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie mediany

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Dla zbioru Z  należy znaleźć element, od którego w tym zbiorze jest tyle samo elementów większych lub równych co mniejszych lub równych.

Element zbioru o powyższej własności nosi nazwę mediany (ang. median ). Mediana posiada wiele ważnych zastosowań praktycznych w statystyce, grafice, obróbce dźwięku i wielu innych dziedzinach.

Jeśli zbiór Z  jest posortowany rosnąco, to

  • przy nieparzystej liczbie elementów n  > 1 mediana jest elementem środkowym Z [ n/ 2 ] (indeksy elementów rozpoczynają się od 0 ).
    Na przykład dla zbioru Z  = {1, 3, 5, 8, 9} medianą jest element 5 – poprzedzają go dwa elementy 1 i 3 oraz wyprzedzają dwa elementy 8 i 9.
  • przy parzystej liczbie elementów n  > 1 mediana jest średnią arytmetyczną dwóch środkowych elementów Z [ n/ 2-1 ] i Z [ n/ 2 ].
    Na przykład dla zbioru Z  = {1, 3, 5, 8, 9, 9} mediana jest równa ( 5 + 8 ) / 2 = 6, 5. Od tej wartości jest dokładnie tyle samo elementów mniejszych (1, 3, 5) co większych (8, 9, 9 ).
    Istnieją również pojęcia dolnej mediany (ang. lower median) i górnej mediany (upper median ), które w tym przypadku oznaczają odpowiednio element Z [ n/ 2-1 ] i Z [ n/ 2 ] w ciągu uporządkowanym o parzystej liczbie elementów.

Rozwiązanie nr 1

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

Posortować zbiór rosnąco. Zwrócić element na pozycji n/ 2 (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,
wykonuj kroki K05...K10		 w pętli elementy większe umieszczamy w Z P, a mniejsze w Z L
K05:     i  ← i  = 1 przesuwamy się na następną pozycję w Z L
K06:     Jeśli Z [ i  ] < v,
    to idź do kroku K05		 szukamy elementu, który nie należy do Z L
K07:     j  ← j  - 1 przesuwamy się na poprzednią pozycję w Z P
K08:     Jeśli Z [ j  ] > v,
    to idź do kroku K07		 szukamy elementu, który nie należy do Z P
K09:     Jeśli i  < j,
    to Z [ i  ] ↔ Z [ j  ]		 znalezione elementy zamieniamy miejscami
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,
to Sortuj_szybko ( Z, i p, i v  - 1 )		 sortujemy rekurencyjnie pierwszą partycję
K03: Jeśli i k  > i v  = 1,
to Sortuj_szybko ( Z, i v  + 1, i k  )		 sortujemy rekurencyjnie drugą partycję
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,
 to zakończ z wynikiem Z [ n  shr 1 ]		 zwracamy medianę zwykłą
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 podziałem

  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 <time.h>

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, x;

  v = Z [ ip ]; i = ip; ik++;
  while( i < ik )
  {
    while( Z [ ++i ]  < v ) ;
    while( Z [ --ik ] > v ) ;
    if( i < ik )
    {
      x = Z [ i ]; Z [ i ] = Z [ ik ]; Z [ ik ] = x;
    }
  }
  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;

  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, ip, ik, k, pv;

  srand ( ( unsigned )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 podziałem

  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 podziałem

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
Wynik:
 627 599 221 107 893 882 757 177 649 711 877 285 138 542 419 771 562 342 674 360
 484 758 915 591 581   7 996 841 164 463 333 427 280 402 146  92 105 552 245  50
 301 610 674 700 198 717  51 928  59 200 772  75 580 945 642 981 278 678 294 464
 621 284 844  74 328 320 882 921 302 263 358 102 299 823 164 944 119 189 389 829
 583 893 857 357 781 216 205 243 152 504  51 830 625  24  21   3 333 241 270

   3   7  21  24  50  51  51  59  74  75  92 102 105 107 119 138 146 152 164 164
 177 189 198 200 205 216 221 241 243 245 263 270 278 280 284 285 294 299 301 302
 320 328 333 333 342 357 358 360 389 402 419 427 463 464 484 504 542 552 562 580
 581 583 591 599 610 621 625 627 642 649 674 674 678 700 711 717 757 758 771 772
 781 823 829 830 841 844 857 877 882 882 893 893 915 921 928 944 945 981 996

402
Na początek:  podrozdziału   strony 

Rozwiązanie nr 2

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 ( n/ 2 + 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.
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:

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

Zmienne pomocnicze:

m  –  indeks mediany, 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;  i k  ← n  - 1 partycja startowa obejmuje cały zbiór
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,
wykonuj kroki K08...K12		 w pętli zamieniamy elementy większe z mniejszymi
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,
    to Z [ i  ] ↔ Z [ j  ]		 jeśli elementy są w złych partycjach, 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,
to zakończ z wynikiem Z [ m  ]		 sprawdzamy, czy znaleziono medianę
K16: Jeśli m  < j,
to i k   ← j  - 1
inaczej i p   ← j  + 1		 wybieramy jedną z dwóch partycji, w której będziemy
; dalej szukać mediany
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 <time.h>

using namespace std;

const int N = 99;

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

  srand ( ( unsigned )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 )
      {
        x = Z [ i ]; Z [ i ] = Z [ j ]; Z [ j ] = x;
      }
    }
    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
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
Wynik:
 537 306 974 949 529 397 188 217 993 999 445 717 451 685 277 934 693 562 253 693
 570 308 932 394 633   7 670  21  85 416 153 787 534 739 166  28 648 757   6 955
 186 506 805 802 145 795 882 936 945 371 662 447 859 854 710 132 310 131 831 672
 800 381 766 589 704 179 153 616 354  30 884 540 411 811 148 307 564 903 621  56
 807 706 599 769 175 229 637 507 758   2 412 400 834 893 895 860 338 157 337

 371 306 337 157 529 397 188 217 338 400 445 412 451   2 277 507 229 175 253  56
 307 308 148 394 411   7  30  21  85 416 153 354 534 153 166  28 179 381   6 131
 186 506 310 132 145 447 537 540 562 564 570 589 599 637 621 616 633 648 693 672
 662 670 685 693 704 706 739 766 787 757 800 831 805 811 769 802 710 758 795 717
 807 834 903 932 884 895 854 934 859 882 860 893 936 999 955 945 993 949 974

564
Na początek:  podrozdziału   strony 

Rozwiązanie nr 3

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;  i k  ← n  - 1 określamy partycję początkową
K03: Dopóki i p  < i k,
wykonuj kroki K04...K12		 szukamy m-tego najmniejszego elementu
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,
    wykonuj i  ← i  + 1		 szukamy elementu nie pasującego do dolnej partycji
K08:     Dopóki v  < Z [ j  ],
    wykonuj j  ← j  - 1		 szukamy elementu nie pasującego do górnej partycji
K09:     Jeśli i  ≤ j,
    to Z [ i  ] ↔ Z [ j  ]; i  ← i  + 1; j  ← j  - 1		 elementy zamieniamy ze sobą, aby trafiły do właściwych
; partycji. Po zamianie indeksy i, j muszą być zmodyfikowane.
K10:     Jeśli i  ≤ j,
    to idź do kroku K07		  
K11:     Jeśli j  < m,
    to i p  ← i		 wybieramy nową partycję do 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 <time.h>

using namespace std;

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

  srand ( ( unsigned )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 )
      {
        x = Z [ i ]; Z [ i ] = Z [ j ]; Z [ j ] = x;
        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
Na początek:  podrozdziału   strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2023 mgr Jerzy Wałaszek

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.