11 replies to this topic

[lxp007]

Suppose you have an array of 1000 integers. The integers are in random order, but you know each of the integers is between 1 and 5000 (inclusive). In addition, each number appears only once in the array. Assume that you can access each element of the array only once. Describe an algorithm to sort it.
Hint: Pseudo code or any language with which you are familiar are acceptable


If you used auxiliary storage in your algorithm, can you find an algorithm that remains O(n) space complexity?

[DenKain]

Well if sorting is the issue here is a little example to help you out:

            int[] arrayList = new int[10];

            arrayList[0] = 8;
            arrayList[1] = 4;
            arrayList[2] = 3;
            arrayList[3] = 6;
            arrayList[4] = 9;
            arrayList[5] = 2;
            arrayList[6] = 1;
            arrayList[7] = 7;
            arrayList[8] = 5;
            arrayList[9] = 10;

            Array.Sort(arrayList);

            foreach (int i in arrayList)
            {
                MessageBox.Show(i + "");
            }

[Syne]

Wow. Just wow. This is what C# does to people.

I doubt someone is going to directly answer a school-type problem like this, but I doubt you are expected to come up with the algorithm on your own, so I'd advice you to just google 'count sort'.

[DenKain]

ummmm, I believe that I DID directly answer their question while giving them an example to learn from.......

[wim DC]

I think he needs to code the algorithm itself, not just use the predifined function for it ;)
Like bubble sort algorithm --> Bubble sort - Wikipedia, the free encyclopedia

[DenKain]

o.0

What kind of school would make you write an algorithm if you were not in a math degree program??

[BlaineSch]

DenKain said:

o.0

What kind of school would make you write an algorithm if you were not in a math degree program??

CS Degree? MIS Degree? Math Education (that doesn't count as math, right?)

[DenKain]

Heck, I got a B.S. in Software Engineering and they didn't expect us to reinvent the wheel.

[BlaineSch]

But could you? Probably.

I learned about sorting algorithms in a class called 'data structures'. The teacher basically said if the tool is there then to use it, but be sure you know how to recreate it just in case.

[zoranh]

Counting sort is an extreme case of bucket sort. I've posted a working code for that in another topic:
http://forum.codecal...efficiency.html.

[zoranh]

DenKain said:

Heck, I got a B.S. in Software Engineering and they didn't expect us to reinvent the wheel.

If you want to be a coder than you need almost nothing at all from software engineering. But if you want to be a software engineer than "reinventing the wheel" is not what you think about it. For example, .NET framework has no support for counting sort, bucket sort, radix sort, heap structure, priority queue and many many other "wheels". If you think that picking a third-party library for radix sort is a solution, then you're so wrong, because adding third party libraries is typically not an option when designing production code. I would suggest you to learn more and to be less proud of having .NET Framework at hand because its limits are so close so many times.

[zoranh]

DenKain said:

Well if sorting is the issue here is a little example to help you out:

            int[] arrayList = new int[10];

            arrayList[0] = 8;
            arrayList[1] = 4;
            arrayList[2] = 3;
            arrayList[3] = 6;
            arrayList[4] = 9;
            arrayList[5] = 2;
            arrayList[6] = 1;
            arrayList[7] = 7;
            arrayList[8] = 5;
            arrayList[9] = 10;

            Array.Sort(arrayList);

            foreach (int i in arrayList)
            {
                MessageBox.Show(i + "");
            }

Here is the benchmark which compares O(n) sorting algorithm to Array.Sort - it is 7 times faster than Array.Sort when sorting a million items in range limited to 100,000 different values.

using System;

namespace CountSort
{
    class Program
    {
        static void Main(string[] args)
        {

            int maxValue = 100000;
            int inputValuesCount = 1000000;
            int[] sortedCount = new int[maxValue + 1];
            int[] input = new int[inputValuesCount];
            int[] input2 = new int[inputValuesCount];

            Random rnd = new Random();
            for (int i = 0; i < inputValuesCount; i++)
                input[i] = input2[i] = rnd.Next(maxValue + 1);

            DateTime t1 = DateTime.Now;

            // Now comes the sort
            for (int i = 0; i < input.Length; i++)
                sortedCount[input[i]]++;

            // Now put it back to input array
            int pos = 0;
            for (int i = 0; i < sortedCount.Length; i++)
                for (int j = 0; j < sortedCount[i]; j++)
                    input[pos++] = i;

            DateTime t2 = DateTime.Now;

            Array.Sort<int>(input2);

            DateTime t3 = DateTime.Now;

            Console.WriteLine(t2.Subtract(t1).TotalMilliseconds);
            Console.WriteLine(t3.Subtract(t2).TotalMilliseconds);

        }
    }
}