Popište algoritmy SelectSort, BubbleSort a InsertSort a jejich časové složitosti. U jednoho z nich diskutujte jeho korektnost a uveďte jeho časovou složitost

SelectSort

• třídící algoritmus pracující v čase O(n^2)

Vlastnosti:

• datově necitlivý - množství již seřazených prvků neovlivňuje počet kroků, které musí algoritmus udělat k seřazení celé posloupnosti.
• in-place - použitá paměť nezavisí na velikosti vstupu
• nestabilní - seřazená posloupnost si nezachovala pozici stejně velkých prvků
  • (nestabilní je uvedeno v přednáškách, ale snadno se dá implementovat i stabilní verze)

Je založen na opakovaném vybírání nejmenšího prvku.

void selectSort(vector<int>& nums) {
        
        for(int i = 0; i < nums.size(); i++)
        {
            int min_pos = i;
            for(int j = i+1; j < nums.size(); j++ )
            {
                if(nums[min_pos] > nums[j])
                    min_pos = j;
                
            }
            swap(nums[i], nums[min_pos]);
        }

    }

BubbleSort

• třídící algoritmus pracující v čase O(n^2)

Vlastnosti:

• datově citlivý - množství již seřazených prvků ovlivňuje počet kroků, které musí algoritmus udělat k seřazení celé posloupnosti.