Otwórz menu główne

Sortowanie przez wybieranie

Sortowanie przez wybieranie - jedna z prostszych metod sortowania o złożoności O(n2). 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
Ilustracja
Przykład działania sortowania przez wybieranie
Rodzaj Sortowanie
Struktura danych Tablica, lista
Złożoność
Czasowa

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ładEdytuj

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.

ImplementacjaEdytuj

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ętrzneEdytuj