# WPMII 27 XI

## plan zajęć:
---
## ZŁOŻONOŚĆ OBLICZENIOWA
:::success
Złożoność obliczeniową deniniujemy jako rząd wielkośći liczby operacji wykonywanych przez algorytm
:::

https://www.youtube.com/watch?v=22lK4v6MsWU

---
## ITERACJA VS REKURENCJA

:::success
Procedura lub funkcja jest rekurencyjna, gdy zawiera odołanie do samej siebie.
:::

#### SILNIA
**rekurencyjna** definicja silni:
$$ n! = \begin{cases}
1 & \text{dla }\ n=1 \\ n \cdot (n-1)! & \text{dla}\ n>1
\end{cases}
$$

int silnia_rek(int n) 
{
  if(n == 0) return 1;
  else return n * silnia_rek(n-1);
}

**klasyczna (iteracyjna)** definicja silni:
$n! = 1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot (n-1) \cdot n$

int silnia_iter(int n)
{
  int wynik = 1;
  for(int i = 1; i <= n; i++) {
    wynik *= i;
  }
  return wynik;
}

#### SUMA CYFR

int suma_cyfr_rek(int n)
{
  if(n == 0) return 0;
  else
  {
    int ostc = n % 10;
    int uciety = n / 10;
    return ostc + suma_cyfr_rek(uciety);
  }
}

int suma_cyfr_iter(int n)
{
  int w  = 0;
  while(n > 0) {
    int ostc = n % 10;
    int uciety = n / 10;
    w += ostc;
    n = uciety;
  }
  return w;
}

#### ZADANIE MATURLANE (maj 2019)

---

## OPERACJE NA TEKSTACH

#### STRING(napis) czyli tablica CHAR(znaków)

---

#### ANAGRAM
:::success
Anagram - wyraz utworzony przez przestawienie liter innego wyrazu.
:::

##### Metoda 1
Zliczamy wystąpenia poszczególnych liter w jednym oraz drugim wyrazie i sprawdzamy czy poszczególne loitery miały taką samą liczbe wystąpień.

void zlicz_litery(string wyraz, int tablica[])
{
    for(int i=0; i<wyraz.length(); i++)
    {
        int idx = (int)wyraz[i];
        idx -= (int)'a';
        tablica[idx] += 1;
    }
}

bool czy_anagram(string wyraz1, string wyraz2)
{
    int tablica1[26] = {0};
    int tablica2[26] = {0};
    zlicz_litery(wyraz1, tablica1);
    zlicz_litery(wyraz2, tablica2);
    for(int i=0; i<26; i++)
    {
        if(tablica1[i] != tablica2[i])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    if(czy_anagram("hhelouyuw", "wlehoh"))
    {
        cout << "to sa anagramy ;D";
    }
    return 0;
}

##### Metoda 2
Zauważmy, że aby sprawdzić czy dwa wyrazy są anagramami najłatwiej będzie posortować wyrazy (czy właściwie litery w wyrazach) alfabetycznie i sprawdzić czy dwa powstałe wyraz są takie same.

#include <algorithm>
...
bool czy_anagram(string wyraz1, string wyraz2)
{
   sort(wyraz1.begin(), wyraz1.end());
   sort(wyraz2.begin(), wyraz2.end());
   return wyraz1 == wyraz2;
}

#### PALINDROM
:::success
Palindrom - wyraz lub zdanie brzmiące tak samo przy czytaniu od lewej strony do prawej, jak i odwrotnie, np. kajak.
:::

bool palindrom(string wyraz)
{
    int n = wyraz.length();
   for (int i=0; i<n/2; i++)
   {
       if (wyraz[i] != wyraz[n-i-1])
       {
           return false;
       }
   }
   return true;
}

#### ZADANIE MATURALNE (maj 2018)
zadanie 4 -- WEGA

---

## KONWERSJE SYSTEMOW LICZBOWYCH
https://towarzystwo.edu.pl/assets/prace_matematyczne/sm_14_kaczowka_makowski_rajs_szlubowski.pdf

## SORTOWANIE

:::danger
**UWAGA:** Wszystkie poniższe opisy i implementacje algorytmów przyjmują założenie, że tablicę chcemy posortować rosnąco.
:::

### Sortowanie bąbelkowe

- Dzielimy tablicę na część nieposortowaną i posortowaną (która na początku jest pusta) - nieposortowana po lewej, posortowana po prawej
- Największy element "wypływa" na wierzch tablicy nieposortowanej jak bąbelek
- Przechodzimy przez całą tablicę nieposortowaną i zamieniamy miejscami dwa sąsiadujące elementy, jeśli nie są ustawione w docelowej kolejności
- Powtarzamy dopóki cała tablica nie jest posortowana
- Jeśli w trakcie pojedynczej iteracji ani razu nie zamienimy dwóch elementów miejscami, to możemy zakończyć algorytm
- Złożoność:
- Optymistyczna: $O(n)$ dla tablicy wejściowej posortowanej rosnąco
- Pesymistyczna: $O(n^2)$ dla tablicy wejściowej posortowanej malejąco

#### C++

void bubbleSort(int arr[], int size) {
  for (int i = 1; i < size; i++) {
    bool swapped = false;
    for (int j = 0; j < size - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
        swapped = true;
      }
    }
    if (!swapped) {
      return;
    }
  }
}

#### Python

def bubbleSort(arr, size):
  for i in range(1, size):
    swapped = False
    for j in range(size - i):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
        swapped = True
    if not swapped:
      return

### Sortowanie przez wybór

- Dzielimy tablicę na część nieposortowaną i posortowaną (która na początku jest pusta) - nieposortowana po prawej, posortowana po lewej
- Wybieramy najmniejszy element w części nieposortowanej i zamieniamy go miejscami z pierwszym elementem tej części
- Po każdej iteracji pętli zewnętrznej tablica posortowana powiększa sie o jeden element
- Złożoność: $O(n^2)$ - mamy dwie pętle przchodzące tablicę, algorytmu nigdy nie kończymy wcześniej niż po zakończeniu wszystkich iteracji

#### C++

void selectSort(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    int minIndex = i;
    for (int j = i; j < size; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    swap(arr[i], arr[minIndex]);
  }
}

#### Python

def selectSort(arr, size):
  for i in range(size):
    minIndex = i
    for j in range(i, size):
      if arr[j] < arr[minIndex]:
        minIndex = j
    arr[i], arr[minIndex] = arr[minIndex], arr[i]

### Sortowanie przez wstawianie

- Dzielimy tablicę na część nieposortowaną i posortowaną (która na początku jest pusta) - nieposortowana po prawej, posortowana po lewej
- Bierzemy pierwszy element z części posortowanej i wstawiamy go w odpowiednie miejsce w części posortowanej - tak żeby pozostała posortowana
- Po każdej iteracji pętli zewnętrznej tablica posortowana powiększa sie o jeden element
- Złożoność:
- Optymistyczna: $O(n)$ dla tablicy wejściowej posortowanej rosnąco - każda wewnętrzna pętla wykona się tylko raz
- Pesymistyczna: $O(n^2)$ dla tablicy wejściowej posortowanej malejąco - z każdym elementem będziemy musieli przejść przez całą tablicę posortowaną

#### C++

void insertSort(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    int j = i - 1;
    while (j >= 0) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
      j -= 1;
    }
  }
}

#### Python

def insertSort(arr, size):
  for i in range(size):
    j = i - 1
    while j >= 0:
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
      j -= 1

### Sortowanie przez scalanie

- Stosujemy strategię _dziel i zwyciężaj_
- Dzielimy tablicę na dwie części, które niezależnie sortujemy (też przez scalanie), po czym scalamy posortowane części w jedną
- Podczas scalania iterujemy się niezależnie po dwóch posortowanych tablicach. Wybieramy mniejszy z elementów, które aktualnie sprawdzamy, przepisujemy go na kolejne miejsce w tablicy wynikowej i przechodzimy do kolejnego elementu w tablicy, z której go wybraliśmy. Jeśli z jednej z tablic przepiszemy wszystkie elementy - wybieramy element z drugiej.
- Złożoność: $O(n log\ n)$ - mamy $log\ n$ poziomów rekurencji (bo dzielimy na dwa) i w każdym z nich łącznie $n$ elementów do scalenia. Scalanie ma złożoność liniową.

#### C++

void merge(int arr[], int l, int m, int r) {
  int lSize = m - l + 1;
  int rSize = r - m;

  int lArr[lSize];
  int rArr[rSize];

  for (int i = 0; i < lSize; i++) {
    lArr[i] = arr[l + i];
  }

  for (int i = 0; i < rSize; i++) {
    rArr[i] = arr[m + 1 + i];
  }

  int lIndex = 0;
  int rIndex = 0;

  for (int i = 0; i < lSize + rSize; i++) {
    if (rIndex >= rSize || (lIndex < lSize && lArr[lIndex] < rArr[rIndex])) {
      arr[l + i] = lArr[lIndex];
      lIndex += 1;
    } else {
      arr[l + i] = rArr[rIndex];
      rIndex += 1;
    }
  }
}

void mergeSort(int arr[], int l, int r) {
  if (l >= r) {
    return;
  }

  int m = (l + r) / 2;

  mergeSort(arr, l, m);
  mergeSort(arr, m + 1, r);
  merge(arr, l, m, r);
}

#### Python

def merge(arr, l, m, r):
  lSize = m - l + 1
  rSize = r - m

  # Fajna, krótka implementacja przepisywania części tablicy
  # do nowej z użyciem tablic składanych.
  # Robi to samo, co linijki 11-18.
  # lArr = [arr[i] for i in range(l, l + lSize)]
  # rArr = [arr[i] for i in range(m + 1, m + 1 + rSize)]
  
  lArr = []
  rArr = []

  for i in range(lSize):
    lArr.append(arr[l + i])

  for i in range(rSize):
    rArr.append(arr[m + 1 + i])

  lIndex = 0
  rIndex = 0

  for i in range(lSize + rSize):
    if rIndex >= rSize or (lIndex < lSize and lArr[lIndex] < rArr[rIndex]):
      arr[l + i] = lArr[lIndex]
      lIndex += 1
    else:
      arr[l + i] = rArr[rIndex]
      rIndex += 1

def mergeSort(arr, l, r):
  if l >= r:
    return
  
  m = floor((l + r) / 2)

  mergeSort(arr, l, m)
  mergeSort(arr, m + 1, r)
  merge(arr, l, m, r)

<p style="font-size:4px;"> Robert Lewandowski to giga kox </p>