Algorithm for generating a nearly sorted list on predefined data

Note: This is part 1 of a 2 part question.

Part 2 here

I'm wanting to more about sorting algorithms and what better way to do than then to code! So I figure I need some data to work with.

My approach to creating some "standard" data will be as follows: create a set number of items, not sure how large to make it but I want to have fun and make my computer groan a little bit :D

Once I have that list, I'll push it into a text file and just read off that to run my algorithms against. I should have a total of 4 text files filled with the same data but just sorted differently to run my algorithms against (see below).

Correct me if I'm wrong but I believe I need 4 different types of开发者_如何学运维 scenarios to profile my algorithms.

• Randomly sorted data (for this I'm going to use the knuth shuffle)
• Reversed data (easy enough)
• Nearly sorted (not sure how to implement this)
• Few unique (once again not sure how to approach this)

This question is for generating a nearly sorted list.

Which approach is best to generate a nearly sorted list on predefined data?

To "shuffle" a sorted list to make it "almost sorted":

1. Create a list of functions you can think of which you can apply to parts of the array, like:

   Negate(array, startIndex, endIndex);
Reverse(array, startIndex, endIndex);
Swap(array, startIndex, endIndex);

2. For i from zero to some function of the array's length (e.g. Log(array.Length):

   1. Randomly choose 2 integers*
   2. Randomly choose a function from the functions you thought of
   3. Apply that function to those indices of the array

*Note: The integers should not be constricted to the array size. Rather, choose random integers and "wrap" around the array -- that way the elements near the ends will have the same chance of being modified as the elements in the middle.

Answering my own question here. All this does is taking a sorted list and shuffling up small sections of it.

    public static T[] ShuffleBagSort<T>(T[] array, int shuffleSize)
    {
        Random r = _random;
        for (int i = 0; i < array.Length; i += shuffleSize)
        {
            //Prevents us from getting index out of bounds, while still getting a shuffle of the 
            //last set of un shuffled array, but breaks for loop if the number of unshuffled array is 1
            if (i + shuffleSize > array.Length)
            {
                shuffleSize = array.Length - i;

                if (shuffleSize <= 1) // should never be less than 1, don't think that's possible lol
                    continue;
            }

            if (i % shuffleSize == 0)
            {
                for (int j = i; j < i + shuffleSize; j++)
                {
                    // Pick random element to swap from our small section of the array.
                    int k = r.Next(i, i + shuffleSize);
                    // Swap.
                    T tmp = array[k];
                    array[k] = array[j];
                    array[j] = tmp;
                }
            }
        }

        return array;
    }

1. Sort the array.
2. Start sorting it in descending order with bubble sort
3. Stop after a few iterations (depending how much 'dis-sorted' you want the array to be
4. Add some randomness (each time when bubblesort wants to swap two elements toss a coin and perform that operation or not depending on the result, or use a different probability than 50/50 for that)

This will give you an array which will be roughly equally modified across its whole range, preserving most of the order (the begining will hold the least elements, the end the greatest). That's because the changes performed by bubblesort with a random test will be rather local. It won't mix the whole array at once so much that it wouldn't resemble the original.

If you want to you can also completely randomly shuffle whole parts of the array (but keep the parts not to big because, you'll completely loose the ordering).

Or you may also randomly swap whole sorted parts of the array. That would be an interesing test case, for example:

[1,2,3,4,5,6,7,8] -> [1,2,6,7,8,3,4,5]

The almost sorted list is the reason why Timsort (python) is so efficient in the real world is because data is typically "almost sorted" . There is an article about it explaining the math behind the entropy of data.