From: Leandro Lucarella <llucax@gmail.com>
Date: Mon, 2 Jan 2006 03:00:26 +0000 (+0000)
Subject: Algunos ejercicios de TDA I.
X-Git-Tag: svn_import
X-Git-Url: https://git.llucax.com/z.facultad/75.29/ejercicios.git/commitdiff_plain/c2355f75d4a44b8b8f1a6b7588500ae15d2e5579?ds=sidebyside

Algunos ejercicios de TDA I.
---

c2355f75d4a44b8b8f1a6b7588500ae15d2e5579
diff --git a/busquedaternaria.py b/busquedaternaria.py
new file mode 100755
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
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;
+}
+