Logic of a sort-algorithm

Question

I try to get the logic of this sort algorithm but I really can't get it, maybe I'm not smart enough...

I have a list. This list is sorted, let's say I have 10 Items.

Now the user choose to place the 9th item to the 4th position.

What's to do?

My idea:

Take the 9. Item in a temporary object.
Put the 8 Item in Place 9
Put the 7 Item in Place 8
Put the 6 Item in Place 7
Put the 5 Item in Place 6
Put the 4 Item in Place 5
Put the 9 Item in Place 4

Is that idea correct?

This is not really a "Sort" algorithm, but more of a "Remove" and "Insert" algorithm combined together — Scott Chamberlain, Sep 21 '13 at 19:56
Looks like [List.Insert](http://msdn.microsoft.com/en-us/library/sey5k5z4.aspx)... Unclear what you are trying to achieve... — Alexei Levenkov, Sep 21 '13 at 20:04
possible duplicate of [Generic List - moving an item within the list](http://stackoverflow.com/questions/450233/generic-list-moving-an-item-within-the-list) — Sergey Kalinichenko, Sep 21 '13 at 20:04

score 1 · Accepted Answer · edited May 23 '17 at 12:11

1

It looks like you are talking about a rotation. Here's a post with several ideas and a decent discussion of the pros and cons of various approaches:

Easiest way to Rotate a List in c#

edited May 23 '17 at 12:11

Community

1
1

answered Sep 21 '13 at 20:04

Joe Mayo

7,501
7
41
60

Freeqaz · Answer 2 · 2013-09-21T20:28:58.880

Here's an example of using a SortedList. You can also just make a list and call Sort() on it.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace sorter
{
    class Program
    {
        static void Main(string[] args)
        {
            var list = new SortedList();
            var item = new SomeItem(1);
            list.Add(item.Value, item);
            item = new SomeItem(8);
            list.Add(item.Value, item);
            item = new SomeItem(2);
            list.Add(item.Value, item);
            item = new SomeItem(4);
            list.Add(item.Value, item);

            for (int i = 0; i < list.Count; i++)
            {
                Console.WriteLine(list.GetByIndex(i));
            }

            Console.ReadLine();
        }
    }

    public class SomeItem
    {
        public int Value;

        public SomeItem(int value)
        {
            Value = value;
        }

        public override string ToString()
        {
            return Value.ToString();
        }
    }
}

score 0 · Answer 3 · answered Sep 21 '13 at 20:13

Doing all those individual moves is going to be inefficient, a better way to do it is do the spans of objects in singular Array.Copy methods.

I am going to work with Arrays instead of Lists as if you are working with List<T> you can just use RemoveAt and Insert

public static void MoveIndex<T>(this T[] array, int sourceIndex, int destIndex)
{
    //Some sanity checks before we start.
    var arrayLength = array.Length;
    if(sourceIndex >= arrayLength || destIndex >= arrayLength || sourceIndex < 0 || destIndex < 0)
        throw new IndexOutOfRangeException("The indexes must be within the array);

    if(sourceIndex == destIndex)
        throw new ArgumentException("The two indexes must not have the same value");

    //Store for later useage
    var temp = array[sourceIndex];

    int offset;
    int length;

    //Figure out if we are moving left or right
    if(souceIndex < destIndex)
    {
        offset = -1;
        length = destIndex - sourceIndex;
    }
    else
    {
        offset = 1;
        length = sourceIndex - destIndex;
    }

    //"Move" the elements that need shifting
    Array.Copy(array, sourceIndex, array, sourceIndex + offset, length);

    //put back the item that we stored earlier;
    array[destIndex] = temp;

}

If you can make your collection a ObservableCollection<T> it has this built right in to it in its Move function

Logic of a sort-algorithm

3 Answers3