Of Selection Sort

Sortowania według wyboru ( Of Selection Sort )

Algorytm sortowania sortuje tablicę, wielokrotnie znajdując minimalny element z nieposortowanej części tablicy i umieszczając go na początku.
Algorytm utrzymuje dwie podrzędne tablice w danej tablicy.

1) Podtablica, która jest już posortowana.
2) Pozostała 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:
tablica[] = 64 47 12 33 11

Znajdź minimalny element w tablicy sprawdzając indeksy od [0 … 4]
i umieść go na początku
11 47 12 33 64

Znajdź minimalny element w tablicy sprawdzając indeksy od [1 … 4]
i umieść go na początku tablicy [1 … 4]
11 12 47 33 64

Znajdź minimalny element w tablicy sprawdzając indeksy od [2 … 4]
i umieść go na początku tablicy [2 … 4]
11 12 33 47 64

Znajdź minimalny element w tablicy sprawdzając indeksy od [3 … 4]
i umieść go na początku tablicy [3 … 4]
11 12 33 47 64

using System;

class Program 
{
	// sortowania według wyboru  ( Of Selection Sort )
	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;
		}
	}

	static void PrintArray(int[] arr)
	{
		int n = arr.Length;

		for (int i = 0; i < n; ++i)
			Console.Write(arr[i] + " ");

		Console.WriteLine();
	}

	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);
	}
}

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *