Sortowanie przez wybieranie

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Sortowanie przez wybieranie - jedna z prostszych metod sortowania o złożoności O(n²). Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.

Algorytm przedstawia się następująco:

wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy
zamień wartość minimalną, z elementem na pozycji i

Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu

Spis treści

1 Przykład

[edytuj] Przykład

Posortowana zostanie tablica 8-elementowa [9,1,6,8,4,3,2,0]. W tablicy pogrubione zostaną te elementy wśród których wyszukuje się wartość minimalną.

nr iteracji (wartość `i`)	tablica	minimum
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1 (element znajduje się na właściwej pozycji)
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4 (...)
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8 (...)

Algorytm można nieco przyspieszyć, gdy tablica jest wypełniana z obu końców, tj. wyszukiwane jest równocześnie minimum i maksimum.

[edytuj] Przykładowy kod w C++, realizujący sortowanie przez wybieranie

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

const int n = 10; // zadana liczba elementów w sortowanym zbiorze

// funkcja porównująca
bool mniejsze(int x, int y)
{
  return x < y;
}

int main(int argc, char *argv[])
{
  size_t i, j, t;
  int x, a[n], b[n];

  // 
  // tworzenie przykładowej tablicy z przypadkową zawartością
  // tablica b[] służy wyłącznie do zapamiętania stanu a[]
  srand((unsigned)time(NULL));
  for (i = 0; i < n; i++)
    a[i] = b[i] = 1 + rand() % (n + n);

  // 
  // właściwe sortowanie przez wybieranie
  for(i = 0; i < n - 1; i++)
  {
    t = i;
    for (j = i + 1; j < n; j ++)
      if (mniejsze(a[j], a[t]))
        t = j;
    x = a[t]; a[t] = a[i]; a[i] = x;
  }

  // 
  // wyświetlanie wyników
  cout << "Sortowanie przez wybieranie\n"
       << "  lp    przed       po\n"
       << "------------------------" << endl;
  for(i = 0; i < n; i++)
  {
    cout.width(4); cout << i + 1;
    cout.width(9); cout << b[i];
    cout.width(9); cout << a[i] << endl;
  };
  cout << endl;

  return 0;
  system("pause"); // zapobiega nagłemu wyłączeniu programu
}

[edytuj] Sortowanie przez wybieranie w C#

public static void SelectionSort(IComparable[] a)
{
  int n = a.Length;
  for(int i = 0; i < n - 1; i++)
  {
    int k = i;
    IComparable x = a[i];
    for(int j = i + 1; j < n; j++)
    {
      if(a[j].CompareTo(x) < 0)
      {
        k = j;
        x = a[j];
      }
    }
    a[k] = a[i];
    a[i] = x;
  }
}

[edytuj] Sortowanie przez wybieranie w Pascalu

procedure SelectSort(var tab:tablica;ele:integer); //ele - liczba elementow tablicy
var i,j,poz,temp:integer;  
begin
for i:=1 to ele-1 do
  begin
      poz:=i;
      for j:=i+1 to ele do if tab[poz]>tab[j] then poz:=j;
      if poz<>i then
        begin
          temp:=tab[i];
          tab[i]:=tab[poz];
          tab[poz]:=temp;
       end;
    end;
end;

[edytuj] Sortowanie przez wybieranie w programie Mathematica

  lista[n_] := Table[Random[Integer, {0, 100}], {i, 0, n - 1}];
  (*generowanie listy n liczb pseudolosowych z zakresu 0-100*)
  selekcja[x1_] := Module[{x, n, i, j, z, k},
   x = x1;
   n = Length[x];
   i = 1;
   While[i ≤ n, k = i; z = xi; j = i + 1;
     While[j ≤ n,
       If[x j < z, {k = j;
    z = x j}]; j++]; x k = x i; x i = z; i++];
   Return[x]];
   selekcja[lista[1000]]; (*przykładowe wywołanie*)

Źródło: "http://pl.wikipedia.org../../../s/o/r/Sortowanie_przez_wybieranie.html"

Kategoria: Sortowanie