Sort Algorithms (C#)

Quick sort

The quick sort function starts its work by selecting a random value from the unsorted list. This value is called the pivot value. Then we remove the pivot value from the unsorted list.
Now each element x in the unsorted list is compared with this pivot. We have two other lists 'Less' and 'Greater'.
if any element is less than the pivot, it is placed in the 'Less' list and if it is greater than the pivot value, it is placed in the 'Greater' list. Then we call the concat function with three arguments in it.
1.List name 'Less'
2.Variable Pivot
3.List Name 'Greater

Using System;
Using System.Collection.Generic;
Using System.Linq;
Using System.Text;

namespace SortAlgorithms
{
class Quicksort
{
public List QuickSort1(List a)
{
List Less = new List();
List Greater = new List();
if (a.Count<=1)
return a;
Random R = new Random();
int pos = R.Next(0,a.Count);
int pivot = a[pos];
a.RemoveAt(pos);
foreach(int i in a)
{
if  (i < pivot)
{
Less.Add(i);
}
else
{
Greater.Add(i);
}
}
return Concat(QuickSort1(Less), pivot, QuickSort1(Greater);

 

/* The concat function here performs a very important role, the quicksort algorithm uses the recursive approach throgh concat function. 

Here concat function receives the three arguments, two lists and pivot value.  

We have defined a new list of integers here name sorted.  

It concats the less, pivot and greater all together in sorted list and then returns this sorted list to quicksort method.  

The quicksort method receives this sorted list and then returns the sorted list to the function  

which sends the unsorted list to quicksort method.*/

 

public List Concat(List Less, int pivot, List Greater)
{
List Sorted = new List(Less);
Sorted.Add(pivot);
foreach (int g in Greater)
{
Sorted.Add(g);
}
return Soretd;
}
}
}
------------------------------------------------------------------------------------------------------------

Merge Sort

Merge Sort is able to rearrange elements of a list in ascending order. Merge sort works as a divide and conquer algorithm. It recursively divide the list into two halves until one element left, and merge the already sorted halves into a sorted one list.

------------------------------------------------------------------------------------------------------------

Bubble Sort

In bubble sort, each element of the unsorted list is compared to the next element and if the value of first element is greater than the value of the second element, then they are swapped. The same is applied again and again until every element gets compared with the whole list.
The result may have ascending or descending sorted elements.The bubble sort consists on the passes. The number of passes depends on the number of elements in the list. More elements means more passes.
It consists of the two loops - a main loop and a nested loop. The main loop describes the number of passes and the nested loops defined the number of comparisons.
The bubblesort is easy to implement but it is a slow sorting algorithm. It traverses each and every element of the unsorted list in every case. That's why it has the worst case and average case complexity as 0(n2).

using System;
using System.Collection.Generic;
using System.Linq;
using System.Text;

namespace SortAlgorithms
{
class BubbleSort
{
public List BubbleSort1(List Input)
{
int temp;
for (int i =1; i < Input.Count; i++)
{
for (int j=0; j< Input.count - 1; j++)
{
if (Input[j] > Input [j+1])
{
temp =Input[j];
Input[j] = Input [j+1];
Input[j+1] = temp;
}
}
}
return Input;
}
}
}

 

 

 

 

Write a method to find how many times a substring occurs in a string (C#)

//
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Configuration;
namespace Excercises
{
 class Program
{
 static void Main(string[] args)
{
 //Write a method to find how many times a substring occurs in a string
string find = "and";
string input = "ROME — Italy's high court on Tuesday faulted the appeals court that acquitted American student Amanda Knox of murdering her roommate, saying its ruling was full of deficiencies, contradictions and illogical conclusions and ordering the new appeals court to look at all the evidence to determine whether Knox helped kill the teen";
char[] delimiters = { ' ', ',', '.', ';', '-' };
string[] words = input.Split(delimiters);
int count = 0;
foreach (var word in words)
{
 if (word.ToLower() == find.ToLower())
{
count++;
}
}
Console.WriteLine("The word '{0}' was found {1} times", find, count);
Console.ReadKey();
}
}
}

Using SQL, on a database with user logins, report the top 10 users that have logged in the most number of times in a given duration along with a count of the items created by them in that duration.

Question :

Using SQL, on a database with user logins, report the top 10 users that have logged in the most number of times in a given duration along with a count of the items created by them in that duration.

 

Example:

Using SupportDB, report the top 10 agents that have logged in the last 'n' days and the number of ServiceRequests created by each of those agents.

 

The output should look like:

 

________________________________________________

Agent Name| Last Logged Date| Log Count | SRs Created

-----------------|------------------------|----------------|---------------------

agent name | 4/20/2013T12:0.. | 23               | 109

__________|_______________|__________|____________

Solution

select UL.FullName, UL.LastLogin, temp.CountOfSRs from UserList UL
join (select top 10 SR.AuditCreatedByPuid,COUNT(SR.id) AS CountOfSRs FROM dbo.ServiceRequest SR (nolock)
where SR.AuditCreatedByPuid in (
select UL.AuditCreatedByPuid from dbo.Userlist UL
where LastLogin >= dateadd(day,- 7,GetUTCDate())
group by SR.AuditCreatedByPuid
order by CountOfSRs desc) temp on UL.PUID = temp.AuditCreatedByPuid

Write a SQL script to convert XML data (in SQL XML data type) to a table.(SQL)

Question:

Write a SQL script to convert XML data (in SQL XML data type) to a table. Each attribute of an element in the XML should be converted to a column in the resulting table.
Example:
if the XML looks like:
...

...
then the script should produce the result as:

Table

-----------------------

attr1 | attr2 |

______|_______|

| |

value1 | value 2 |

______|_______|

Using query() and value() methods:

DECLARE @table_temp TABLE (yourXML XML)
DECLARE @xmlDoc XML

SET @xmlDoc =
(
SELECT XCol
FROM dbo.XTable WHERE ID=1
FOR XML RAW, TYPE
)
INSERT INTO @table_temp
SELECT @xmlDoc

SELECT
--t.yourXML,
--r.c.query('.'),
r.c.value('(//@PersonID)[1]', 'varchar (50)') AS PersonID,
r.c.value('(//@LastName)[1]', 'varchar(50)') AS LastName,
r.c.value('(//@PersonID)[2]', 'varchar (50)') AS PersonID,
r.c.value('(//@LastName)[2]', 'varchar(50)') AS LastName
FROM @table_temp t
CROSS APPLY t.yourXML.nodes('row') as r(c)

Using OpenXML Transact-SQL build in function

DECLARE @idoc int, @doc XML;
SET @doc =(
--You can also load a XML here from the table XML field

);
--Create an internal representation of the XML document.
EXEC sp_xml_preparedocument @idoc OUTPUT, @doc;
-- SELECT stmt using OPENXML rowset provider
SELECT *
--flag=1 is attribute centric, 2 is element centric. More info at this link : http://msdn.microsoft.com/en-us/library/ms186918(v=sql.105).aspx
FROM OPENXML (@idoc,'/row/XCol/people/person',1)
WITH (PersonID int,
LastName varchar(10)
);

Write a C# method to implement a change dispenser.

Question :

Write a C# method to implement a change dispenser. The change dispenser takes in a number of higher denomination and returns the smallest number of lower denominations to dispense. The method should return the denominations and the counts of those denominations.

Example: if the dispenser has $1 and $5 denominations only and the method is called with $19, then it should return 3 * $5 and 4 * $1 instead of 19 * $1 denominations as it means fewer notes. So it should return both the above denominations and their counts to the caller.

For the implementation, assume you have $1, $2, $5 and $10 denominations only, and find the least number of denominations to break a given higher denomination. Assume only whole number denominations. No need to specify '$' in the method as it is used only for representation.

Solution:
namespace Excercises
{
class Program
{
static void Main(string[] args)
{
Console.Write("Please enter the money you need the change for :");
string value = Console.ReadLine();

int TotalMoney = Int32.Parse(value);
if (TotalMoney <= 0) { Console.WriteLine("Invalid number entered. Please try again"); } if (TotalMoney > 0)
{
ChangeDispenser(TotalMoney);
}


Console.ReadKey();
}

public static void ChangeDispenser(int n)
{
//avaialble denominations $10, $5, $2, $1
int numOfTens = 0;
int numOfFives = 0;
int numOfTwos = 0;
int numOfOnes = 0;

if (n >= 10)
{
numOfTens = n / 10;
n= n%10;
}
if (n >= 5)
{
numOfFives = n / 5;
n = n % 5;
}
if (n >= 2)
{
numOfTwos = n / 2;
n = n % 2;
}
numOfOnes = n;

Console.WriteLine("Number of 10s: {0}, Number of 5s : {1}, Number of 2s : {2}, Numer of 1s : {3}", numOfTens, numOfFives, numOfTwos, numOfOnes);

}
}
}

C# Program simulating a slot machine

Question :

Write a C# program to simulate a slot machine draw. Each draw consists of 4 characters (2 alternating letters 2 numbers, like a1b2, c3x4, f5e3 etc.)

Have a method (say, 'ChaChing') which returns a random 4 characters in the above format. However, if a draw has occurred in the last 10 tries, then return a different draw.

In order for a jackpot, the draw will need to have both letters and numbers to be the same, i.e. a1a1, b4b4, h9h9 etc. Ensure that there is at least one jackpot in every 30 draws.


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Collections;
namespace examples
{
    class Program
    {
        static void Main(string[] args)
        {
           
            Queue myQueue = new Queue();
 Random r = new Random();
int JackpotNumber = r.Next(30);
 for (int i = 0; i < 30; i++)
 {
     if (i == JackpotNumber)
     {
         string queueString = pattern(true);
         myQueue.Enqueue(queueString);
     }
     else
     {
         string NonJP = pattern(false);
         if (myQueue.Contains(NonJP))
         {
             string NonJP2 = pattern(false);
             myQueue.Enqueue(NonJP2);
             Console.WriteLine(NonJP2); }
         else
         {
             myQueue.Enqueue(NonJP);
             Console.WriteLine(NonJP);
         }
     }
 } Console.ReadKey();
           
            if (myQueue.Count > 30)
 {
myQueue.Dequeue();
 }
        }
        public static string pattern(bool IsJackpot)
        {
            Random random = new Random();
            int i = random.Next(9);
            int j = random.Next(9);
            string[] strArr = new string[] { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" };
            StringBuilder str = new StringBuilder();
            if (IsJackpot)
            {
                int index = random.Next(25);
                str.Append(strArr[index]);
                str.Append(i);
                str.Append(strArr[index]);
                str.Append(i);
                return str.ToString();
            }
            else
            {
                int index = random.Next(25);
                int index1 = random.Next(25);
                if (index == index1 && i == j)
                {
                    str.Append(strArr[index + 1]);
                    str.Append(i + 1);
                    str.Append(strArr[index]);
                    str.Append(i);
                }
                else
                {
                    str.Append(strArr[index]);
                    str.Append(i);
                    str.Append(strArr[index1]);
                    str.Append(j);
                }
                return str.ToString();
            }


        }
    }
}
 

Write a C# function to find the number of occurrences of a given word in a file.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace examples
{
class Program
{
static void Main(string[] args)
{
string find = "tax";
Dictionary myDic = new Dictionary();
StreamReader InputStream = new StreamReader(@"FilePath");
StringBuilder build = new StringBuilder();
build.Append(InputStream.ReadToEnd());
string[] strArr = build.ToString().Split(' ');
for (int i = 0; i < strArr.Length; i++)
{
if (strArr[i].ToLower() == find.ToLower())
{
if (myDic.ContainsKey(find.ToLower()))
{
myDic[strArr[i]]++;
}
else
{
myDic.Add(find.ToLower(), 1);
}
}
}
foreach (var v in myDic)
{
Console.WriteLine("'{0}' occurs {1} times in the input file", find, v.Value);
}
Console.ReadKey();
}
}
}