using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Merge_sort
{
class Program
{
static void Main(string[] args)
{
int T = Convert.ToInt32(Console.ReadLine());
while(T>0)
{
int a;
List<int> unsorted = new List<int>();
List<int> sorted;
var s = Console.ReadLine().Split(' ');
for(int i=0;i<s.Length;i++)
{
if(int.TryParse(s[i],out a))
{
unsorted.Add(a);
}
}
Console.WriteLine("Original array elements:" );
for(int i = 0; i< unsorted.Count;i++){
Console.Write(unsorted[i]+" ");
}
Console.WriteLine();
sorted = MergeSort(unsorted);
Console.WriteLine("Sorted array elements: ");
foreach (int x in sorted)
{
Console.Write(x+" ");
}
Console.Write("\n");
T--;
}
}
private static List<int> MergeSort(List<int> unsorted)
{
if (unsorted.Count <= 1)
return unsorted;
List<int> left = new List<int>();
List<int> right = new List<int>();
int middle = unsorted.Count / 2;
for (int i = 0; i < middle;i++) //Dividing the unsorted list
{
left.Add(unsorted[i]);
}
for (int i = middle; i < unsorted.Count; i++)
{
right.Add(unsorted[i]);
}
left = MergeSort(left);
right = MergeSort(right);
return Merge(left, right);
}
private static List<int> Merge(List<int> left, List<int> right)
{
List<int> result = new List<int>();
while(left.Count > 0 || right.Count>0)
{
if (left.Count > 0 && right.Count > 0)
{
if (left.First() <= right.First()) //Comparing First two elements to see which is smaller
{
result.Add(left.First());
left.Remove(left.First()); //Rest of the list minus the first element
}
else
{
result.Add(right.First());
right.Remove(right.First());
}
}
else if(left.Count>0)
{
result.Add(left.First());
left.Remove(left.First());
}
else if (right.Count > 0)
{
result.Add(right.First());
right.Remove(right.First());
}
}
return result;
}
}
}
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Merge_sort
{
class Program
{
static void Main(string[] args)
{
int T = Convert.ToInt32(Console.ReadLine());
while(T>0)
{
int a;
List<int> unsorted = new List<int>();
List<int> sorted;
var s = Console.ReadLine().Split(' ');
for(int i=0;i<s.Length;i++)
{
if(int.TryParse(s[i],out a))
{
unsorted.Add(a);
}
}
Console.WriteLine("Original array elements:" );
for(int i = 0; i< unsorted.Count;i++){
Console.Write(unsorted[i]+" ");
}
Console.WriteLine();
sorted = MergeSort(unsorted);
Console.WriteLine("Sorted array elements: ");
foreach (int x in sorted)
{
Console.Write(x+" ");
}
Console.Write("\n");
T--;
}
}
private static List<int> MergeSort(List<int> unsorted)
{
if (unsorted.Count <= 1)
return unsorted;
List<int> left = new List<int>();
List<int> right = new List<int>();
int middle = unsorted.Count / 2;
for (int i = 0; i < middle;i++) //Dividing the unsorted list
{
left.Add(unsorted[i]);
}
for (int i = middle; i < unsorted.Count; i++)
{
right.Add(unsorted[i]);
}
left = MergeSort(left);
right = MergeSort(right);
return Merge(left, right);
}
private static List<int> Merge(List<int> left, List<int> right)
{
List<int> result = new List<int>();
while(left.Count > 0 || right.Count>0)
{
if (left.Count > 0 && right.Count > 0)
{
if (left.First() <= right.First()) //Comparing First two elements to see which is smaller
{
result.Add(left.First());
left.Remove(left.First()); //Rest of the list minus the first element
}
else
{
result.Add(right.First());
right.Remove(right.First());
}
}
else if(left.Count>0)
{
result.Add(left.First());
left.Remove(left.First());
}
else if (right.Count > 0)
{
result.Add(right.First());
right.Remove(right.First());
}
}
return result;
}
}
}
Comments
Post a Comment