Sortowania Według Wyboru
Algorytm sortowania sortuje tablicę, wielokrotnie znajdując minimalny element z nieposortowanej części tablicy i umieszczając go na początku tablicy.
Algorytm utrzymuje dwie podrzędne tablice w danej tablicy:
1) Podtablica, która jest już posortowana.
2) Pozostała część, czyli podtablica, która jest nieposortowana.
W każdej iteracji sortowania jest wybierany minimalny element z nieposortowanej podtablicy i przenoszony do posortowanej podtablicy.
Poniższy przykład wyjaśnia powyższe kroki:
Mamy tablicę: tablica[] = 79 43 7 11 5
Znajdź minimalny element w tablicy sprawdzając indeksy od [0 … 4]
i umieść go na początku5 79 43 7 11
Znajdź minimalny element w tablicy sprawdzając indeksy od [1 … 4]
i umieść go na początku tablicy [1 … 4]5 7 79 43 11
Znajdź minimalny element w tablicy sprawdzając indeksy od [2 … 4]
i umieść go na początku tablicy [2 … 4]5 7 11 79 43
Znajdź minimalny element w tablicy sprawdzając indeksy od [3 … 4]
i umieść go na początku tablicy [3 … 4]5 7 11 43 79
Implementacja w kodzie C#
using System;
class Program
{
public static void Main()
{
int[] arr = { 79, 86, 97, 43, 64, 25, 12, 22, 11, 7, 23, 5 };
SelectionSort(arr);
Console.WriteLine("Posortowana tablica");
PrintArray(arr);
}
private static void SelectionSort(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
{
// Znajdź minimalny element w nieposortowanej tablicy
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Zamień znaleziony minimalny element na pierwszy element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
private static void PrintArray(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
}
Wyjście:
5 7 11 12 22 23 25 43 64 79 86 97