Cheatsheet за контролното по информатика на 19/11/2018

Тази страница съдържа информация за алгоритмите, които може да се паднат на контролното по информатика на 19/11/2018, а именно:

• Bubble Sort (Метод на мехурчето)

• Selection Sort (Метод на пряката селекция)

• Insertion Sort (Метод на прякото вмъкване)

Bubble Sort (Метод на мехурчето)

Принцип на действие:

1. Взимаме първият елемент на масива
и го сравняваме със следващият (втория в нашия случай)
и разменяме стойностите им, ако първият е по – голям от
втория.

2. След това сравняваме вторият елемент с третия
и пак разменяме, ако има нужда.
Ако нашият масив е от 10 елемента, след 9
такива сравнения най – отгоре
ще изплува най – голямата стойност.

3. Започваме отново да сравняваме като
пак взимаме първият елемент и сравняваме
с вторият и така нататък.

На практика:

    bool isSorted = false;
    while(!isSorted) 
    {
        isSorted = true;

        for(int i = 1; i < arr.Length; i++) 
        {
            if(arr[i-1] > arr[i]) 
            {
                int temp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = temp;
                isSorted = false;
            }
        }
    }

Selection Sort (Метод на пряката селекция)

Принцип на действие:

1. Намира най-малкия елемент в списъка като 
сравнява първият елемент с всички останали

2. Разменя го с елемента на първа позиция

3. Повтаря горните две стъпки за всеки следващ
елемент

На практика:

    for(int i = 0; i < arr.Length; i++) 
    {
        int min = i;
        for(int j = i + 1; j < arr.Length; j++) 
        {
            if(arr[j] < arr[min]) 
            {
                min = j;
            }
        }

        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }

Insertion Sort (Метод на прякото вмъкване)

Принцип на действие:

1. Списъкът с елементи, които ще бъдат
сортирани се разделя на две части: частта
със сортираните елементи и частта с несортираните

2. При всяка стъпка се взема първият елемент от
несортирания списък и се вмъква на правилната
позиция в сортираната част от списъка

3. Сортирането продължава докато елементите от
несортираната част на списъка се изчерпят

На практика:

    for(int i = 1; i < arr.Length; i++) 
    {
        int key = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > key) 
        {
            arr[j+1] = arr[j];
            arr[j] = key;
            j--;
        }
    }

Любо Любчев