Algunos ejercicios de TDA I.

diff --git a/busquedaternaria.py b/busquedaternaria.py
new file mode 100755 (executable)
index 0000000..10d6e5d
--- /dev/null
+++ b/busquedaternaria.py
@@ -0,0 +1,41 @@
+#!/usr/bin/env python
+
+import sys
+
+def buster(lista, valor):
+
+       def busrec(ini, fin):
+               if ini >= fin:
+                       try:
+                               if lista[ini] == valor:
+                                       return ini
+                       except IndexError:
+                               if lista[fin] == valor:
+                                       return fin
+                       return None
+               seg = (fin - ini) / 3
+               a = ini + seg
+               b = a + seg
+               if a == b:
+                       b += 1
+               if valor == lista[a]:
+                       return a
+               if valor < lista[a]:
+                       return busrec(ini, a - 1)
+               if valor == lista[b]:
+                       return b
+               if valor < lista[b]:
+                       return busrec(a + 1, b - 1)
+               return busrec(b + 1, fin)
+
+       return busrec(0, len(lista))
+
+
+print dict([(i, int(n)) for i, n in enumerate(sys.argv[2:])]), int(sys.argv[1])
+print buster([int(n) for n in sys.argv[2:]], int(sys.argv[1]))
+
+# Orden:
+#
+# T(N) = 1 * T(N/3) + O(1)  (A = 1, B = 3, k = 0)
+#
+# => O(T(N)) = O(N^0 * log3 N) = O((1 / log 3) * log N) = O(log N)

diff --git a/quicksort.cpp b/quicksort.cpp
new file mode 100644 (file)
index 0000000..170483d
--- /dev/null
+++ b/quicksort.cpp
@@ -0,0 +1,48 @@
+
+#include <vector>
+#include <string>
+#include <iterator>
+#include <iostream>
+#include <algorithm>
+
+using namespace std;
+
+int pivote(vector<int>& v, int val, int ini, int fin)
+{
+       int i = ini + 1;
+       int p = fin - 1;
+       while (v[i] <= val && i < fin) ++i;
+       while (v[p] > val) --p;
+       while (i < p)
+       {
+               swap(v[i], v[p]);
+               while (v[i] <= val) ++i;
+               while (v[p] > val) --p;
+       }
+       swap(v[ini], v[p]);
+       return p;
+}
+
+void quicksort(vector<int>& v, int ini, int fin)
+{
+       if (ini < fin)
+       {
+               int p = pivote(v, v[ini], ini, fin);
+               quicksort(v, ini, p);
+               quicksort(v, p+1, fin);
+       }
+}
+
+int main()
+{
+       int n;
+       vector<int> v;
+       while (cin >> n)
+       {
+               v.push_back(n);
+       }
+       quicksort(v, 0, v.size());
+       copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
+       return 0;
+}
+