Complexity: O(n)

Algorithm

2 pointers: i and j

The pointer i is maintained while another pointer j is scanning through the array, from its starting all the way to the end (up to the pivot element). The scan ensures that any element e₀ that is present from the starting point of the array to the (i-1)ᵗʰ index is lesser than the pivot element in terms of value and the elements present at any index ranging from i to j are equal to or bigger than the pivot element in terms of value.

• To demonstrate the working of the Lomuto Partition Scheme through quicksort, let us take an array: A = [4, 2, 7, 3, 1, 9, 6, 0, 8]

while (j != ARRAY_SIZE) {
	if (array[j] > pivot) {
		// do until finding element, which is <= pivot:
		i++;
		if (foundSuchElement) {
			swap(array[j], array[i]); 
		} else {
			swap(array[j], pivot); 
			exitPartition(); 
		}
	} else {
		// all ok, pivot >= array[j] is true, just increment j index and check next
	}
	j++; 
}

https://iq.opengenus.org/lomuto-partition-scheme/

• Choosing our pivot element as pivot = 8 and placing our initial pointers i and j (the arrow above the array is the for the i pointer whereas the arrow below the array is for the j pointer), we get:

https://iq.opengenus.org/lomuto-partition-scheme/

• Now we have to simply follow the algorithm for the partition. The elements at the jth pointer will be compared to the pivot element continuously throughout the various iterations. Since pivot >= 4 (first element, where the pointers are pointing), we'll move the pointers ahead for the next comparison.

https://iq.opengenus.org/lomuto-partition-scheme/

• Once again, since pivot >= 2, we move ahead for the next comparison.

  

  https://iq.opengenus.org/lomuto-partition-scheme/

• Here pivot >= 7 as well, so we keep on moving until we reach 9 element (5th index) of the array. Here, 9 >= pivot, and so we place one of our pointers at this index (5) until we reach another index that contains a value that is ≤ pivot:

https://iq.opengenus.org/lomuto-partition-scheme/

• Moving ahead, we find that the element at the 6th index (6) is smaller than 9 (where we placed one of our pointers).

https://iq.opengenus.org/lomuto-partition-scheme/

A swapping operation is performed.

https://iq.opengenus.org/lomuto-partition-scheme/

• This process is repeated until we reach the pivot element, and so we will further go on and swap the values of 9 and 0, and then finally swap the values of 9 and the pivot element (8) itself. After the first pass, we get the following array:

https://iq.opengenus.org/lomuto-partition-scheme/