Dada una array , arr[] de tamaño N cuyos elementos, de izquierda a derecha, deben leerse como un flujo entrante de enteros, la tarea es clasificar el flujo de enteros e imprimir en consecuencia.
Ejemplos:
Entrada: arr[] = {2, 4, 1, 7, 3}
Salida: 1 2 3 4 7
Explicación:
Primer elemento de la secuencia: 2 → Lista ordenada: {2}
Segundo elemento de la secuencia: 4 → Lista ordenada : {2, 4}
Tercer elemento del flujo: 1 → Lista ordenada: {1, 2, 4}
Cuarto elemento del flujo: 7 → Lista ordenada: {1, 2, 4, 7}
Quinto elemento del flujo: 3 → Lista ordenada: {1, 2, 3, 4, 7}Entrada: arr[] = {4, 1, 7, 6, 2}
Salida: 1 2 4 6 7
Explicación:
Primer elemento de la secuencia: 4 → Lista ordenada: {4}
Segundo elemento de la secuencia: 1 → Lista ordenada : {1, 4}
Tercer elemento del flujo: 7 → Lista ordenada: {1, 4, 7}
Cuarto elemento del flujo: 6 → Lista ordenada: {1, 4, 6, 7}
Quinto elemento del flujo: 2 → Lista ordenada: {1, 2, 4, 6, 7}
Enfoque ingenuo: el enfoque más simple es <a href=”https://www.geeksforgeeks.org/c-program-to-traverse-an-array/”>recorrer la array y, para cada elemento de la array, escanear linealmente la array y encuentre la posición correcta de ese elemento y colóquelo en la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to sort a stream of integers
void Sort(vector<int>& ans, int num)
{
// Stores the position of
// array elements
int pos = -1;
// Traverse through the array
for (int i = 0; i < ans.size(); i++) {
// If any element is found to be
// greater than the current element
if (ans[i] >= num) {
pos = i;
break;
}
}
// If an element > num is not present
if (pos == -1)
ans.push_back(num);
// Otherwise, place the number
// at its right position
else
ans.insert(ans.begin() + pos, num);
}
// Function to print the sorted stream of integers
void sortStream(int arr[], int N)
{
// Stores the sorted stream of integers
vector<int> ans;
// Traverse the array
for (int i = 0; i < N; i++) {
// Function Call
Sort(ans, arr[i]);
// Print the array after
// every insertion
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << endl;
}
}
// Driver Code
int main()
{
int arr[] = { 4, 1, 7, 6, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
sortStream(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to sort a stream of integers
static void Sort(Vector<Integer> ans, int num)
{
// Stores the position of
// array elements
int pos = -1;
// Traverse through the array
for(int i = 0; i < ans.size(); i++)
{
// If any element is found to be
// greater than the current element
if (ans.get(i) >= num)
{
pos = i;
break;
}
}
// If an element > num is not present
if (pos == -1)
ans.add(num);
// Otherwise, place the number
// at its right position
else
ans.add(pos, num);
}
// Function to print the sorted stream of integers
static void sortStream(int arr[], int N)
{
// Stores the sorted stream of integers
Vector<Integer> ans = new Vector<Integer>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Function Call
Sort(ans, arr[i]);
// Print the array after
// every insertion
for(int j = 0; j < ans.size(); j++)
{
System.out.print(ans.get(j) + " ");
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 1, 7, 6, 2 };
int N = arr.length;
sortStream(arr, N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python program for the above approach # Function to sort a stream of integers def Sort(ans, num): # Stores the position of # array elements pos = -1; # Traverse through the array for i in range(len(ans)): # If any element is found to be # greater than the current element if (ans[i] >= num): pos = i; break; # If an element > num is not present if (pos == -1): ans.append(num); # Otherwise, place the number # at its right position else: ans.insert(pos,num); return ans; # Function to print the sorted stream of integers def sortStream(arr, N): # Stores the sorted stream of integers ans = list(); # Traverse the array for i in range(N): # Function Call ans = Sort(ans, arr[i]); # Print the array after # every insertion for j in range(len(ans)): print(ans[j], end = " "); print(); # Driver Code if __name__ == '__main__': arr = [4, 1, 7, 6, 2]; N = len(arr); sortStream(arr, N); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to sort a stream of integers
static void Sort(List<int> ans, int num)
{
// Stores the position of
// array elements
int pos = -1;
// Traverse through the array
for(int i = 0; i < ans.Count; i++)
{
// If any element is found to be
// greater than the current element
if (ans[i] >= num)
{
pos = i;
break;
}
}
// If an element > num is not present
if (pos == -1)
ans.Add(num);
// Otherwise, place the number
// at its right position
else
ans.Insert(pos, num);
}
// Function to print the sorted stream of integers
static void sortStream(int []arr, int N)
{
// Stores the sorted stream of integers
List<int> ans = new List<int>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Function Call
Sort(ans, arr[i]);
// Print the array after
// every insertion
for(int j = 0; j < ans.Count; j++)
{
Console.Write(ans[j] + " ");
}
Console.WriteLine();
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 4, 1, 7, 6, 2 };
int N = arr.Length;
sortStream(arr, N);
}
}
// This code is contributed by 29AjayKumar
4 1 4 1 4 7 1 4 6 7 1 2 4 6 7
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar una búsqueda binaria para encontrar la posición correcta de cada elemento en la lista ordenada. Siga los pasos a continuación para resolver el problema:
- Inicialice una array ans[] para almacenar el flujo final de números ordenados.
- Recorra la array arr[] como un flujo de números usando una variable i y realice los siguientes pasos:
- Si la array ans está vacía, inserte arr[i] en ans .
- De lo contrario, encuentre la posición correcta de arr[i] en la array ya ordenada ans[] usando lower_bound() y presione arr[i] en su posición correcta.
- Después de completar los pasos anteriores, imprima la array ans[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to sort a stream of integers
void Sort(vector<int>& ans, int num)
{
// If the element is greater than
// all the elements in the sorted
// array, then it push at the back
if (lower_bound(ans.begin(),
ans.end(), num)
== ans.end()) {
ans.push_back(num);
}
// Otherwise, find its correct position
else {
int pos = lower_bound(ans.begin(),
ans.end(),
num)
- ans.begin();
// Insert the element
ans.insert(ans.begin() + pos,
num);
}
}
// Function to print the sorted stream of integers
void sortStream(int arr[], int N)
{
// Stores the sorted stream of integers
vector<int> ans;
// Traverse the array
for (int i = 0; i < N; i++) {
// Function Call
Sort(ans, arr[i]);
// Print the array after
// every insertion
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << endl;
}
}
// Driver Code
int main()
{
int arr[] = { 4, 1, 7, 6, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
sortStream(arr, N);
return 0;
}
4 1 4 1 4 7 1 4 6 7 1 2 4 6 7
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por punit_tiwari y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA