Given an array, arr[] of size N whose elements from left to right, must be read as an incoming stream of integers, the task is to sort the stream of integers and print accordingly.
Examples:
Input: arr[] = {2, 4, 1, 7, 3}
Output: 1 2 3 4 7
Explanation:
First element in the stream: 2 ? Sorted list: {2}
Second element in the stream: 4 ? Sorted list: {2, 4}
Third element in the stream: 1 ? Sorted list: {1, 2, 4}
Fourth element in the stream: 7 ? Sorted list: {1, 2, 4, 7}
Fifth element in the stream: 3 ? Sorted list: {1, 2, 3, 4, 7}Input: arr[] = {4, 1, 7, 6, 2}
Output: 1 2 4 6 7
Explanation:
First element in the stream: 4 ? Sorted list: {4}
Second element in the stream: 1 ? Sorted list: {1, 4}
Third element in the stream: 7 ? Sorted list: {1, 4, 7}
Fourth element in the stream: 6 ? Sorted list: {1, 4, 6, 7}
Fifth element in the stream: 2 ? Sorted list: {1, 2, 4, 6, 7}
Naive Approach: The simplest approach is to traverse the array and for each array element, linearly scan the array and find the right position of that element and place it in the array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to sort a stream of integersvoid 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 integersvoid 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 Codeint 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 approachimport java.util.*;class GFG{// Function to sort a stream of integersstatic 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 integersstatic 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 Codepublic 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 integersdef 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 integersdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function to sort a stream of integersstatic 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 integersstatic 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 Codepublic 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 |
Javascript
<script>// Javascript program for the above approach// Function to sort a stream of integersfunction Sort(ans, num){ // Stores the position of // array elements let pos = -1; // Traverse through the array for (let i = 0; i < ans.length; 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(num); // Otherwise, place the number // at its right position else ans.splice(pos, 0, num);}// Function to print the sorted stream of integersfunction sortStream(arr, N){ // Stores the sorted stream of integers // Stores the sorted stream of integers let ans = new Array(); // Traverse the array for(let i = 0; i < N; i++) { // Function Call Sort(ans, arr[i]); // Print the array after // every insertion let res = []; for(let j = 0; j < ans.length; j++) { res.push(ans[j]); } console.log(res); res = []; } }// Driver Codelet arr = [ 4, 1, 7, 6, 2 ];let N = arr.length;sortStream(arr, N);// This code is contributed by akashish__</script> |
Output:
4 1 4 1 4 7 1 4 6 7 1 2 4 6 7
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use a Binary Search to find the correct position of each element in the sorted list. Follow the steps below to solve the problem:
- Initialize an array ans[] to store the final sorted stream of numbers.
- Traverse the array arr[] as a stream of numbers using a variable i and perform the following steps:
- If array ans is empty, push arr[i] to ans.
- Otherwise, find the correct position of arr[i] in the already sorted array ans[] using lower_bound() and push arr[i] at its correct position.
- After completing the above steps, print the array ans[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to sort a stream of integersvoid 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 integersvoid 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 Codeint main(){ int arr[] = { 4, 1, 7, 6, 2 }; int N = sizeof(arr) / sizeof(arr[0]); sortStream(arr, N); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { public static int lowerBound(ArrayList<Integer> v, int num) { int ans = -1; for (int i = 0; i < v.size(); i++) { if (v.get(i) >= num) { ans = i; break; } } return ans; } // Function to sort a stream of integers public static void Sort(ArrayList<Integer> ans, int num) { // If the element is greater than // all the elements in the sorted // array, then it push at the back if (lowerBound(ans, num) == -1) { ans.add(num); } // Otherwise, find its correct position else { int pos = lowerBound(ans, num); // Insert the element ans.add(pos, num); } } // Function to print the sorted stream of integers public static void sortStream(int[] arr, int N) { // Stores the sorted stream of integers ArrayList<Integer> ans = new ArrayList<Integer>(); for (int i = 0; i < N; i++) { // Function Call Sort(ans, arr[i]); // Print the array after // every insertion ArrayList<Integer> res = new ArrayList<Integer>(); for (int j = 0; j < ans.size(); j++) { res.add(ans.get(j)); } for (int k = 0; k < res.size(); k++) { System.out.print(res.get(k)); System.out.print(" "); } System.out.println(""); res.clear(); } } 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 akashish__ |
Python3
# Python3 program for the above approachdef lowerBound(v, num): ans = -1 for i in range(0,len(v)): if (v[i] >= num): ans = i break return ans# Function to sort a stream of integersdef Sort(ans, num): # If the element is greater than # all the elements in the sorted # array, then it push at the back if (lowerBound(ans, num) == -1): ans.append(num) # Otherwise, find its correct position else: pos = lowerBound(ans,num) # Insert the element ans.insert(pos,num)# Function to print the sorted stream of integersdef sortStream(arr, N): # Stores the sorted stream of integers ans = [] # Traverse the array for i in range(0,N): # Function Call Sort(ans, arr[i]) # Print the array after # every insertion for i in range(0,len(ans)): print(ans[i] , end = " ") print("")# Driver Codearr = [ 4, 1, 7, 6, 2 ]N = len(arr)sortStream(arr, N)# This code is contributed by akashish__ |
C#
using System;using System.Collections.Generic;public class GFG { public static int lowerBound(List<int> v, int num) { int ans = -1; for (int i = 0; i < v.Count; i++) { if (v[i] >= num) { ans = i; break; } } return ans; } // Function to sort a stream of integers public static void Sort(List<int> ans, int num) { // If the element is greater than // all the elements in the sorted // array, then it push at the back if (lowerBound(ans, num) == -1) { ans.Add(num); } // Otherwise, find its correct position else { int pos = lowerBound(ans, num); // Insert the element ans.Insert(pos, num); } } // Function to print the sorted stream of integers public static void sortStream(int[] arr, int N) { // Stores the sorted stream of integers List<int> ans = new List<int>(); for (int i = 0; i < N; i++) { // Function Call Sort(ans, arr[i]); // Print the array after // every insertion List<int> res = new List<int>(); for (int j = 0; j < ans.Count; j++) { res.Add(ans[j]); } for (int k = 0; k < res.Count; k++) { Console.Write(res[k]); Console.Write(" "); } Console.WriteLine(""); res.Clear(); } } // Driver Code static public void Main() { int[] arr = { 4, 1, 7, 6, 2 }; int N = arr.Length; sortStream(arr, N); }}// This code is contributed by akashish__ |
Javascript
<script>// Javascript program for the above approachfunction lowerBound(v, num) { let ans = -1; for (let i = 0; i < v.length; i++) { if (v[i] >= num) { ans = i; break; } } return ans;}// Function to sort a stream of integersfunction Sort(ans, num) { // If the element is greater than // all the elements in the sorted // array, then it push at the back if (lowerBound(ans, num) == -1) { ans.push(num); } // Otherwise, find its correct position else { let pos = lowerBound(ans, num); // Insert the element ans.splice(pos, 0, num); }}// Function to print the sorted stream of integersfunction sortStream(arr, N) { // Stores the sorted stream of integers ans = []; // Traverse the array for (let i = 0; i < N; i++) { // Function Call Sort(ans, arr[i]); // Print the array after // every insertion let res = []; for (let j = 0; j < ans.length; j++) { res.push(ans[j]); } console.log(res); res = []; }}// Driver Codelet arr = [4, 1, 7, 6, 2];let N = arr.length;sortStream(arr, N);// contributed by akashish__</script> |
Output:
4 1 4 1 4 7 1 4 6 7 1 2 4 6 7
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
