Алгоритам сортирања избора

У овом упутству ћете научити како сортирање избора функционише. Такође, наћи ћете радне примере сортирања избора у Ц, Ц ++, Јава и Питхон.

Сортирање избора је алгоритам који у свакој итерацији бира најмањи елемент са несортиране листе и тај елемент поставља на почетак несортиране листе.

Како функционише сортирање избора?

  1. Подесите први елемент као minimum. Изаберите први елемент као минимум
  2. Упоредите minimumса другим елементом. Ако је други елемент мањи од minimum, доделите други елемент као minimum.
    Упоредите minimumса трећим елементом. Опет, ако је трећи елемент мањи, доделите minimumтрећем елементу, у супротном не радите ништа. Процес се наставља до последњег елемента. Упоредите минимум са преосталим елементима
  3. После сваке итерације minimumставља се испред неразврстане листе. Замените прву са минимумом
  4. За сваку итерацију индексирање започиње од првог несортираног елемента. Кораци 1 до 3 се понављају све док се сви елементи не поставе на своје тачне положаје. Прва понављања Друга понављања Трећа понављања Четврта понављања

Алгоритам сортирања избора

 селецтионСорт (низ, величина) поновите (величина - 1) пута поставите први несортирани елемент као минимум за сваки од несортираних елемената ако је елемент <цуррентМинимум постављени елемент као нови минимални свап минимум са првом несортованом позицијом на крају селецтионСорт

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++ 
 # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
 // Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
 // Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )

Сложеност

Циклус Број поређења
1ст (н-1)
2нд (н-2)
3. (н-3)
… …
последњи 1

Број поређења: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2готово једнако .n2

Сложеност =O(n2)

Такође, можемо анализирати сложеност једноставним посматрањем броја петљи. Постоје 2 петље па је сложеност .n*n = n2

Сложеност времена:

  • Најгоре сложеност случаја: Ако желимо да сортирамо у растућем редоследу, а низ је у опадајућем, тада се дешава најгори случај.O(n2)
  • Сложеност најбољег случаја: Појављује се када је низ већ сортиранO(n2)
  • Просечна сложеност случаја: Појављује се када су елементи низа у помешаном редоследу (ни растући ни силазни).O(n2)

Временска сложеност врсте избора је у свим случајевима иста. На сваком кораку морате пронаћи минимални елемент и поставити га на право место. Минимални елемент није познат док се не постигне крај низа.

Сложеност простора:

Сложеност простора је O(1)зато што се користи додатна променљива temp.

Апликације за сортирање избора

Сортирање избора се користи када:

  • треба сортирати мали списак
  • трошкови замене нису битни
  • провера свих елемената је обавезна
  • трошкови писања у меморију су битни као у флеш меморији (број уписа / замена је O(n)у поређењу са мехурићима)O(n2)

Занимљиви Чланци...