Sortowania Według Wyboru

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ątku
5 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

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *