Dada una array y un rango [ lowVal , highVal ], divida la array alrededor del rango de manera que la array se divida en tres partes.
- Todos los elementos más pequeños que lowVal vienen primero.
- Todos los elementos en el rango lowVal a highVal vienen a continuación.
- Todos los elementos mayores que highVal aparecen al final.
Los elementos individuales de tres conjuntos pueden aparecer en cualquier orden.
Ejemplos:
Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}
lowVal = 14, highVal = 20
Output: arr[] = {1, 5, 4, 2, 1, 3, 14, 20, 20, 98, 87, 32, 54}
Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}
lowVal = 20, highVal = 20
Output: arr[] = {1, 14, 5, 4, 2, 1, 3, 20, 20, 98, 87, 32, 54}
Una solución simple es ordenar la array. Esta solución realiza muchos reordenamientos adicionales y requiere tiempo O(n Log n).
Una solución eficiente se basa en QuickSort basado en la bandera nacional holandesa . Atravesamos los elementos dados de la array desde la izquierda. Realizamos un seguimiento de dos punteros, primero (llamado inicio en el código a continuación) para almacenar la siguiente posición del elemento más pequeño (menor que el rango) desde el principio; y segundo (llamado final en el código a continuación) para almacenar la siguiente posición del elemento mayor desde el final.
Implementación:
C++
// C++ program to implement three way partitioning
// around a given range.
#include<iostream>
using namespace std;
// Partitions arr[0..n-1] around [lowVal..highVal]
void threeWayPartition(int arr[], int n,
int lowVal, int highVal)
{
// Initialize next available positions for
// smaller (than range) and greater elements
int start = 0, end = n-1;
// Traverse elements from left
for (int i=0; i<=end;)
{
// If current element is smaller than
// range, put it on next available smaller
// position.
if (arr[i] < lowVal)
{
//if i and start are same in that case we can't swap
//swap only if i is greater than start
if(i==start)
{
start++;
i++;
}
else
swap(arr[i++], arr[start++]);
}
// If current element is greater than
// range, put it on next available greater
// position.
else if (arr[i] > highVal)
swap(arr[i], arr[end--]);
else
i++;
}
}
// Driver code
int main()
{
int arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87,
98, 3, 1, 32};
int n = sizeof(arr)/sizeof(arr[0]);
threeWayPartition(arr, n, 10, 20);
cout << "Modified array \n";
for (int i=0; i<n; i++)
cout << arr[i] << " ";
}
Java
// Java program to implement three way partitioning
// around a given range.
import java.io.*;
class GFG
{
// Partitions arr[0..n-1] around [lowVal..highVal]
public static void threeWayPartition(int[] arr, int lowVal, int highVal)
{
int n = arr.length;
// Initialize ext available positions for
// smaller (than range) and greater elements
int start = 0, end = n-1;
// Traverse elements from left
for(int i = 0; i <= end;)
{
// If current element is smaller than
// range, put it on next available smaller
// position.
if(arr[i] < lowVal)
{
int temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i++;
}
// If current element is greater than
// range, put it on next available greater
// position.
else if(arr[i] > highVal)
{
int temp = arr[end];
arr[end] = arr[i];
arr[i] = temp;
end--;
}
else
i++;
}
}
public static void main (String[] args)
{
int arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32};
threeWayPartition(arr, 10, 20);
System.out.println("Modified array ");
for (int i=0; i < arr.length; i++)
{
System.out.print(arr[i] + " ");
}
}
}
//This code is contributed by Dheerendra Singh
Python3
# Python3 program to implement three way
# partitioning around a given range.
# Partitions arr[0..n-1] around [lowVal..highVal]
def threeWayPartition(arr, n, lowVal, highVal):
# Initialize ext available positions for
# smaller (than range) and greater elements
start = 0
end = n - 1
i = 0
# Traverse elements from left
while i <= end:
# If current element is smaller than
# range, put it on next available smaller
# position.
if arr[i] < lowVal:
arr[i], arr[start] = arr[start], arr[i]
i += 1
start += 1
# If current element is greater than
# range, put it on next available greater
# position.
elif arr[i] > highVal:
arr[i], arr[end] = arr[end], arr[i]
end -= 1
else:
i += 1
# Driver code
if __name__ == "__main__":
arr = [1, 14, 5, 20, 4, 2, 54,
20, 87, 98, 3, 1, 32]
n = len(arr)
threeWayPartition(arr, n, 10, 20)
print("Modified array")
for i in range(n):
print(arr[i], end = " ")
# This code is contributed by
# sanjeev2552
C#
// C# program to implement three way
// partitioning around a given range.
using System;
class GFG {
// Partitions arr[0..n-1]
// around [lowVal..highVal]
public static void threeWayPartition(int[] arr,
int lowVal, int highVal)
{
int n = arr.Length;
// Initialize ext available positions for
// smaller (than range) and greater elements
int start = 0, end = n - 1;
// Traverse elements from left
for (int i = 0; i <= end;) {
// If current element is smaller than
// range, put it on next available smaller
// position.
if (arr[i] < lowVal) {
int temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i++;
}
// If current element is greater than
// range, put it on next available greater
// position.
else if (arr[i] > highVal) {
int temp = arr[end];
arr[end] = arr[i];
arr[i] = temp;
end--;
}
else
i++;
}
}
// Driver code
public static void Main()
{
int[] arr = { 1, 14, 5, 20, 4, 2, 54,
20, 87, 98, 3, 1, 32 };
threeWayPartition(arr, 10, 20);
Console.WriteLine("Modified array ");
for (int i = 0; i < arr.Length; i++) {
Console.Write(arr[i] + " ");
}
}
}
// This article is contributed by vt_m.
Javascript
<script>
// JavaScript program to implement three
// way partitioning around a given range.
// Partitions arr[0..n-1] around [lowVal..highVal]
function threeWayPartition(arr, n, lowVal, highVal)
{
// Initialize ext available positions for
// smaller (than range) and greater elements
let start = 0, end = n - 1;
// Traverse elements from left
for(let i = 0; i <= end;)
{
// If current element is smaller than
// range, put it on next available smaller
// position.
if (arr[i] < lowVal)
{
let temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i++;
}
// If current element is greater than
// range, put it on next available greater
// position.
else if(arr[i] > highVal)
{
let temp = arr[end];
arr[end] = arr[i];
arr[i] = temp;
end--;
}
else
i++;
}
}
// Driver code
let arr = [ 1, 14, 5, 20, 4, 2, 54,
20, 87, 98, 3, 1, 32 ];
let n = arr.length;
threeWayPartition(arr, n, 10, 20);
document.write("Modified array <br>");
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by Surbhi Tyagi.
</script>
Producción
Modified array 1 5 4 2 1 3 14 20 20 98 87 32 54
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Preguntado en Yahoo
Este artículo es una contribución de Roshni Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA