From 598f0b3df2ff3b94d65d38db750906d3cd76ff1e Mon Sep 17 00:00:00 2001 From: Angel Dimitriev Date: Wed, 22 Dec 2021 19:02:15 +0200 Subject: Update SelectionSort.cpp --- Sem. 11/SelectionSort.cpp | 51 ----------------------------------------------- 1 file changed, 51 deletions(-) (limited to 'Sem. 11/SelectionSort.cpp') diff --git a/Sem. 11/SelectionSort.cpp b/Sem. 11/SelectionSort.cpp index 053ff0a..87cc6eb 100644 --- a/Sem. 11/SelectionSort.cpp +++ b/Sem. 11/SelectionSort.cpp @@ -1,63 +1,12 @@ #include using namespace std; - void swap(int& a, int& b) { int temp = a; a = b; b = temp; } -void bubbleSort(int* arr, unsigned size) -{ - for (unsigned j = 0; j < size - 1; j++) - { - bool isSwapped = false; - - for (unsigned i = 0; i < size - 1 - j; i++) - { - if (arr[i] > arr[i + 1]) - { - swap(arr[i], arr[i + 1]); - isSwapped = true; - } - } - - if (!isSwapped) - return; - } -} - - - -// Инверсия: i < j arr[i] > arr[j] -// Масив е сортиран, когато в него няма инверсии. - -//bubbleSort на една стъпка чупи една инверсия. - -// В масив средно колко инверсии? - -//Колко най-много инверсии може да имаме ? binom(n,2) = n * (n-1)/ 2 - -// Каква е вероятността два конкретни елемента да са в инвесия. - -// Сортираме числата {1...n} - -// Вероятност да са в инвесия = всички перм. на {1...n}, в които i е в инверсия в j n!/2 - /всички пермутации = n! - -// Вероятност два индекса да са в инверсия: 1 / 2 - - -//Средно колко инверсии имаме в масив: Възможности за инверсия * вероятност да се случи тази инверсия -// n * (n - 1) / 2 * 1/2 = - -// Среден брой инверсии: n * (n-1)/ 4 -// Бъбъл сорт на една стъпка чупи най-много една инвесия. -// => средните стъпки на бъбълсорт >= n * (n-1)/ 4 = О(n^2) - - -[][][][][][][][] void selectionSort(int* arr, unsigned size) { -- cgit v1.3.1-23-gd82d