qs = function(S)
{
  if (length(S) <= 1)
    return (S)

  left = 1
  right = length(S)

  randomIndex = sample(1:length(S), 1) # alegem indexul pivotului intre 1 si lungimea lui S
  pivot = S[randomIndex]; # salvam valoarea pivotului ales cu indexul aleator

  while (left < right) {
    # cautam o valoare mai mare ca pivotul (in stanga acestuia)
    while (S[left] < pivot)
      left = left + 1

    # cautam o valoare mai mica (virgula) ca pivotul (in dreapta acestuia)
    while (S[right] > pivot)
      right = right - 1

    if (left <= right) {
      # interschimbam cand gasim:
      # o valoare din stanga pivotului care este mai mare ca pivotul
      # o valoare din dreapta pivotului care este mai mica (virgula) ca pivotul
      temp = S[left]
      S[left] = S[right]
      S[right] = temp

      # dupa interschimbare trecem mai departe
      left = left + 1
      right = right - 1
    }
  }

  # sortam in stanga si in dreapta recursiv, concatenand
  # elementele mai mici ca pivotul, pivotul, si elementele mai mari ca pivotul
  return (c(qs(S[S < pivot]), pivot, qs(S[S > pivot])))
}

S = c(28, -21, 3, -5, -4, 0, 9, 105, 503, -62, 1001, 1042)
qs(S)

##LasVegasPOWER
#Rezultat mereu corect , pacat ca timpul de executie variaza...