Lomutos and Hoares algorithms are used for partitioning, which for instance the famous sorting algorithm Quicksort is built on-top of. Lomuto's is a simpler solution but less efficient, while Hoare's is a little more sophisticated and was invented by the Quicksort man himself - Tony Hoare, hence the name.
In these algorithms we want to partition a given array around something that we call the pivot, which is basically just an element in the array (and can be chosen differently).
Overview
Let $ A[p] $ be our pivot element. Then we want to partition the array such that $$ A[0..p-1] A[p] A[p+1..n-1] $$
where all elements in $ A[0..p-1] $ are smaller than $ A[p] $ and $ A[p+1..n-1] $ are greater.
For example, assume that we have the array $$ A = [4, 6, 2, 1, 3] $$
And that we choose the last element, $ 3 $, as pivot element. Then we want to partition the array so that all elements smaller than $ 3 $ are to the left of it, and all greater elements are to the right. Note that, it doesn't matter if the elements left of $ 3 $ or right of $ 3 $ would be in the wrong order. For example, this can be a result that we're looking for:
$$ A[2, 1, 3, 6, 4] $$
Using Lomuto's algorithm
Lomuto's algorithm is fairly simple. We scan the whole array and use a variable $ i $ that you can think of as a marker where we put all elements smaller than our pivot behind. So whenever we find a smaller element we just increment $ i $ and put the element there and move on to the next element in list. This particular pseudocode uses the last element as pivot.
Example
Let's see how the algorithm works with the following array!
$$ A[7, 3, 2, 9, 5] $$
$ 5 $ is the last element so $ A[4] $ is the pivot. Here we have $ l = 0 $ and $ r $ is the last element of the list.
A bold element is the current element that's being compared to pivot, e.g. the element $ j $ is pointing at. An underlined element is the element $ i $ is pointing at, i.e. the marker.
$ i = -1 $, $ j = 1 $ A[7, 3, 2, 9, 5]: Is $ 3 \leq 5 $? Yes. Increment $ i $ and swap $ A[j], A[i] $. Increment $ j $. $ i = 0 $, $ j = 2 $
A[3, 7, 2, 9, 5]: Is $ 2 \leq 5 $? Yes. Increment $ i $ and swap $ A[j], A[i] $. Increment $ j $.
swap(i + 1, r) where we put the pivot element at its right place. Since the $ i $th element will be smaller than the pivot, it's obvious that $ A[i+1] $ will be greater, so it doesn't matter if we put it in the end of the list.
Not surprisingly, Lomuto's algorithm runs in linear time, i.e. $ \Theta(n) $.
Pseudocode
function lomuto_partition(A[l..r]): pivot = A[r] i = l - 1 from j = l to r: if A[j] <= pivot: i += 1 swap a[i] with a[j] swap(i + 1, r) // return split position return i + 1
Using Hoare's algorithm
Instead of just scanning from left to right or right to left (like in Lumoto's algorithm), Hoare's approach scans from both ends. From the left end, we use a pointer $ i $ and scans until we find an equal or greater element than the pivot. From right end, we use a pointer $ j $ and try to find an equal or smaller element than the pivot. If $ i $ and $ j $ haven't crossed i.e. $ i < j $, then we just swap the elements because we want the smaller to the left and greater to the right.
Pseudocode
The pseudocode is pretty straight forward. In this pseudocode, we use the first element as the pivot. Then we just scan from both ends like described above to find what elements to swap to their right places. It will happen that $ i \geq j $ so we need to undo the last swap. Finally, we swap our pivot element $ A[p] $ with $ A[j] $ and put it at its right place.
function hoare_partition(A[l..r]): p = A[l] i = l j = r - 1 while i ≤ j: while A[i] ≤ p and i ≤ j : i++ while A[j] ≥ p and j ≥ i: j++ swap A[i] with A[j] // undo last swap when i ≥ j swap(A[i], A[j]) swap(A[l], A[j]) return j+1
Implementations in Python
Only suggestions. Feel free to come up with your implementation :)
def lomuto_partition(a, l, r): pivot = a[r] i = l - 1 for j in range(l, r): if a[j] <= pivot: i += 1 swap(a, i, j) swap(a, i + 1, r) return i + 1 def hoare_partition(a, start, end): pivot = a[end] left = start right = end - 1 while left <= right: while a[left] <= pivot and left <= right: left += 1 while a[right] >= pivot and right >= left: right -= 1 swap(a, left, right) # undo last swap when i >= j swap(a, left, right) swap(a, end, left) return right + 1 def swap(a, i, j): temp = a[i] a[i] = a[j] a[j] = temp
Example usage
test = t = [5, 7, 2, 1, 0, 9, 3] hoare_partition(test, 0, len(test)-1) #lomuto_partition(test, 0, len(test)-1)</u>
Sombras nada más, de José María Contursi y Francisco Lomuto, interpretada por José Luis Ordóñez, tenor, y el Mariachi de Santiago, del CD México en mi Corazó...
Sombras nada más, de José María Contursi y Francisco Lomuto, interpretada por José Luis Ordóñez, tenor, y el Mariachi de Santiago, del CD México en mi Corazón.
La #Pratica, Mercoledì 18 Febbraio, presenta: Una serata con… Francisco Lomuto!
I mercoledì, dopo Practicamos Juntos (21:00) ci sarà la consueta pratica dell’Officna.
E alle 20:00 per la postura di noi tangueri un oretta di Pilates studiato appositamente!
Ogni mercoledì lo dedicheremo all’ascolto di uno dei grandi maestri del Tango i cui brani occuperanno circa il 50% delle tande, così da provare anche con le orecchie! Perché il Tango è, prima di tutto, musica!
For today we're back to the orchestra of Lomuto, this time some instrumentals. Lomuto, if you remember, is mostly quite old (late 20s to 40s I would say). Rather old-fashioned, although experimenting with different instruments - similar to Canaro. I feel the music is very heavy, like all the orchestra (big mass) is moving together under great effort ;).
Here's a few more links:
http://www.youtube.com/watch?v=bHyCXYN47eA
http://www.youtube.com/watch?v=3VYVCqT54OU
http://www.youtube.com/watch?v=LGQ1Zu2HAbw
http://www.youtube.com/watch?v=HyW9lu0XBN0
In fact, i realize, these songs are all late 20s. One can hear a little the old milonga rhythm, in the sense that the stress is on 1 and 3 rather than all 4 beats (or I think in Tango terminology this is expressed differently... this is how I understand it though ;)). If you remember, there's something called d'Arienzo revolution, which I think is precisely about transforming that rhythm into what we're familiar with from newer tangos - but no guarantee on this statement! Have a listen yourself :-)
The orchestra is Lomuto, and this recording is from 1936. Notice that the singer, Jorge Omar, has a minor role here and only sings the refrain. This is the 30s, and he's a estribillista.
Lomuto was a pianist, but not an outstanding one, so at some stage he decided to just go for orchestra conducting and leave the piano to someone else. He also composed quite a few tangos, the earliest when he was only 13 I think.
Now, he was good friends with Canaro, so before setting up his own orchestra, Lomuto asked him if he could play in Canaro's orchestra for a while to learn from him. In fact, he picked up a lot there, it seems. The styles of the two orchestras are quite similar in many ways: conservative, rhythmical, danceable, rather simple... but then and again experimenting with instruments, including some that were otherwise not so popular in tango. For Lomuto it was most notably the bass clarinet: whenever you hear it, it's clear that the orchestra is Lomuto. In the above video, you can hear it in the very beginning, around 0:30 and again at 2:55.
Lomuto's orchestra played a lot in theatres, a good source of income for orchestras.
Now to the singer, Jorge Omar: very particular voice, simple to recognize. His main success was with Lomuto in late 30s and early 40s. Lomuto anyway was one of the most successful orchestras back then, so it was very lucky for Omar to sing there.
http://www.youtube.com/watch?v=lVxnw_0PLc4 (clarinet at 1:02)
PARQUE PATRICIOS - Orquesta Z (2011) como Lomoto (1941)
Parque Patricios was written, I believe, in 1929 by Argentinian composer Antonio Radicci, lyrics by Francisco Laino.
Francisco Lomuto was a contemporary of Canaro's, who in the 1920's and 30's added jazz instruments, like Canaro, to his band, like the clarinets in this piece. Lomuto called his orchestra "típica y jazz band" from the 20's on. I'm always rather amused by some of my contemporaries who believe that "golden era" precludes enriching tango with new instrumentals and even new instruments, when in fact the history of tango speaks of great musicians incorporating new elements daily to their music, so that tango constantly evolves.
This orchestration I took from Lomuto (1893-1950) who himself was born in the southern neighborhood of Buenos Aires called Parque de Los Patricios, or simply Parque Patricios, the Park of the Patricians. It was an older neighborhood, which suffered in the early history of Buenos Aires from the yellow fever epidemic. Nevertheless, the composer is reminded of his old neighborhood, the sounds of music, and the joy of singing in his beloved neighborhood.
Just browsing the web yesterday, I saw "El Flaco" Dany dancing to this piece and I even added the name of the piece and orchestra that played it. Some sites have this listed as Canaro, but indeed it's from the original, interesting Lomoto version. I thought it was worth learning and adding it to my scores that I'm composing for my orchestra Orquesta Z here in the San Francisco Bay Area.
So for your pleasure, here's my version of Parque Patricios.
Bendrew Jong
[email protected]
