Seminar 2

Acest seminar propune mai multe tipuri de sortari precum si aplicatii ale acestora.

Insertion Sort

Complexitate: O(n2)

Iteram prin vector si la fiecare pas j avem sortat vectorul A[1..j-1] si cautam locul lui A[j].


for j = 2 to len
  key = A[j]
  i = j - 1
  while i > 0 and A[i] > key
      A[i + 1] = A[i] //deplasam totul la dreapta pt a-i face loc
      --i
   A[i + 1] = key

Merge Sort

Complexitate: O(n log n)

Foloseste paradigma divide and conquer divide: imparte inputul A[1..n] in 2 parti egale conquer: sortam recursiv cele doua jumatati combine: aplicam merge pe cele 2 subsiruri sortate (liniar)

  
  Merge_Sort(A, p, r)
  
    if p < r
      q = (p + r) / 2
      Merge_Sort(A, p, q)
      Merge_Sort(A, q + 1, r)
      Merge(A, p, q, r)

Quick Sort

Complexitate: O(n log n)

La fiecare pas gasim pozitia pivotului in sirul sortat

divide: partitioneaza inputul A[p..r] in A[p..q-1] si A[q+1..r] cu proprietatea ca A[p..q-1] <= A[q] si A[q] <= A[q+1..r] conquer: sortam ambele subsiruri apeland recursiv quicksortul combine: alipim sirurile

Partitia se poate face in mai multe moduri: -Hoare -Lomuto -cu pivot mobil -randomizat (mai eficient pe cazul mediu) -median of 3


Quick_Sort(A, p, r)
  q = Partition(A, p, r)
  Quick_Sort(A, p, q - 1)
  Quick_Sort(A, q+1, r)
  
Partition:
  pivot = A[r]
  i = p - 1
  for j = p to r - 1
    if A[j] <= pivot
      ++i
      swap A[i] A[j]
  swap A[i + 1] A[r]
  return i + 1

Bucket Sort

Complexitate: O(n)

presupune ca elementele sunt generate dupa o distributie uniforma in [0, 1)

Inputul este impartit in k bucketuri. Fiecare din bucket contine lementele din itervalul [i / k, (i+1) / k) si se sorteaza cu insertion sort

functioneaza cand suma patratelor dimensiunii bucketului e liniar

Counting Sort

Complexitate: O(n)

presupune ca elementele sunt in intervalul [0, k]

Se calculeaza frecventa elementelor. Punem elemente pe pozitia corespunzatoare,. c[x] - numarul de elemente <= x


Counting_Sort
  for j = 1 to n
    c[a[j]]++
  for i = 1 to k
    c[i] = c[i] + c[i - 1]
  for j = n to 1
    b[c[a[j]]] = a[j]
    c[a[j]]--;

Radix Sort

  • folosit in sortarea pachetelor de carti
  • folosit in sortarea elementelor cu multiple campuri

Se sorteaza numerele succesiv dupa cifre, de la cea mai nesemnificativa spre cea mai semnificativa. Sortarea folosita la fiecare pas trebuie sa fie stabila. (nu schimba ordinea cartilor apartinand anterior aceleiasi categorii)


Radix_Sort
  for i = 1 to d
    sortez stabil numerele dupa cifra a i-a in ordinea importantei

Probleme:

  • Rucsac discontinuu
  • sdo kth smallest
  • Inv click
  • Binar click
  • Puncte pe o dreapta: Se dau n puncte in plan. Care e numarul maxim de puncte aflate pe aceasi dreapta.
  • Numarul trapezelor Se dau n puncte in plan. Cate trapeze putem forma?
  • Sorting in wave click

Extra:

  • x si y astfel incat (x, y) minim si cmmdc se calculeaza in fix i pasi
  • find duplicate
  • The stolen breakfast drone - element fara pereche
  • Split Rectangle
  • Find element that apears once (others - 3 times)