Sortowanie przez wybieranie

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

Sortowanie przez wybieranie

Przykład działania sortowania przez wybieranie
Rodzaj	Sortowanie
Struktura danych	Tablica, lista
Złożoność
Czasowa	$O(n^{2})$

Algorytm przedstawia się następująco:

1. wyszukaj minimalną wartość z tablicy spośród elementów od i do końca tablicy
2. 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.

Algorytm jest niestabilny. Przykładowa lista to: [2a,2b,1] → [1,2b,2a] (gdzie 2b=2a)

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ą.

element tablicy (wartość i)	tablica	wartość najmniejszego elementu tablicy (z części nieposortowanej)
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 (element znajduje się na właściwej pozycji)
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8 (element znajduje się na właściwej pozycji)

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

Implementacja

Sortowanie przez wybieranie w C++:

• przez wyszukiwanie największego składnika:

 int Max_element_indeks(int n)
   {
     int max = 0;
     for (int i = 1; i < n; i++)
       if (t[i] > t[max])
         max = i;
     return max;
   }

  void Selection_sort(int n)
  {
    for (int i = n; i >= 2; i--)
    {
      int max = Max_element_indeks(i);
      if (max != i - 1)
        swap(t[i - 1], t[max]);
    }
  }

template<typename It>
void selection_sort(It begin, It end)
{
  for (; begin != end; ++begin)
    std::iter_swap(begin, std::min_element(begin, end));
}

• przez wyszukiwanie najmniejszego składnika:

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

using namespace std;

void selection_sort(int n, int t[]);

int main(void)
{
   int tab[20];
   srand(time(NULL));
   for(int i=0; i<20; i++) {
      tab[i] = rand()%100;
      cout << tab[i] << " ";
   }
   cout << endl;
   selection_sort(20, tab);
   for(int i=0; i<20; i++) cout << tab[i] << " ";
   cout << endl;
   return 0;
}

void selection_sort(int n, int t[])
{
   int i, j, k;
   for(i=0; i<n; i++) {
      k=i;
      for(j=i+1; j<n; j++) if(t[j]<t[k]) k=j;
      swap(t[k], t[i]);
   }
}

Sortowanie przez wybieranie w ruby

#!/usr/bin/ruby

# sortowanie przez wybor

def wsort(list)
	for i in 0...(list.size - 1)
		min = i
		for j in (i+1)...(list.size)
			if list[j] <= list[min]
				min = j
			end
		list[i], list[min] = list[min], list[i]
		end
	end
	return list
end

list = []
puts "podaj dane do posortowania CTRL-D - koniec"
while line = $stdin.gets
  list << line.to_i
end
puts "Dane posortowane"
puts wsort(list)

Sortowanie przez wybieranie w PHP

<?php
function selection_sort($tab)
{
	$n = count($tab);
	for($j=0; $j<$n-1; $j++)
	{
		$pmin = $j;
		for($i=$j+1; $i<$n; $i++)
		{
			if($tab[$i] < $tab[$pmin])
			{
				$pmin = $i;
			}
		}
		$x = $tab[$pmin];
		$tab[$pmin] = $tab[$j];
		$tab[$j] = $x;
	}
	return $tab;
}

// generujemy tablicę 30 liczb do posortowania
$arr = array();
for($i=1; $i<=30; $i++)
{
	$arr[] = rand(10,99); // zapełniamy tablicę liczbami dwucyfrowymi
}

// drukujemy wygenerowaną tablicę
echo "Przed sortowaniem:<br />";
foreach($arr as $k)
{
	echo $k. " ";
}

// drukujemy posortowaną tablicę
echo "<br /><br />Po sortowaniu:<br />";
$sort = selection_sort($arr);
foreach($sort as $k)
{
	echo $k. " ";
}
?>

Sortowanie przez wybieranie w Javascript

/**
 * Prototyp dla tablicy zamieniający kolejność dwóch indeksów tej tablicy
 * @param x
 * @param y
 * @returns {Array}
 */
Array.prototype.swap = function (x, y) {
    var b = this[x];
    this[x] = this[y];
    this[y] = b;
    return this;
};

/**
 *  Funkcja wypełniająca tablice losowymi liczbami
 * @param array
 */
function fillArray(array) {
    for (var i = 0; i < 30; i++) {
        var randomNumber = Math.floor(Math.random() * 30) + 1; // "+ 1" aby losowało z zakresu <1, 30>
        array.push(randomNumber);
    }
}

/**
 * Funkcja sortowania przez wybieranie
 * @param array
 */
function selectionSort(array) {
    for (var i = 0; i < array.length - 1; i++) {
        var min = i;
        for (var j = i + 1; j < array.length; j++) {
            if (array[j] < array[min]) {
                min = j;
            }
        }
        if (min !== i) {
            array.swap(i, min);
        }
    }
}

Linki zewnętrzne

• Algorytm przedstawiony z wykorzystaniem cygańskiego tańca