Search code examples
c#sortinggenericsquicksorticomparable

Creating a quick sort using recursion and generics


I want to ask about the sort generic class I created. I used a lot of different concepts I learned this year and combined it into a nice class which I can use to sort anything (granted that if its a class the class has a CompareTo method)

public class Sort<T> where T : IComparable<T>
    {
        private List<T> toSort;
        public Sort(List<T> sortList)
        {
            toSort = sortList;
            quickSort();
        }
        public void quickSort()
        {
            qSort(toSort, 0, toSort.Count - 1);
        }
        private void qSort(List<T> toSort, int left, int right)
        {
            //set the indexes
            int leftIndex = left;
            int rightIndex = right;

            //get the pivot
            var pivot = toSort[left + (right - left) / 2];
            while (leftIndex <= rightIndex)
            {
                //check left values
                while (toSort[leftIndex].CompareTo(pivot)<0)
                {
                    leftIndex++;
                }
                //check right values
                while (toSort[rightIndex].CompareTo(pivot) >0)
                {
                    rightIndex--;
                }
                //swap
                if (leftIndex <= rightIndex)
                {
                    var tmp = toSort[leftIndex];
                    toSort[leftIndex] = toSort[rightIndex];
                    toSort[rightIndex] = tmp;

                    //move towards pivot
                    leftIndex++;
                    rightIndex--;
                }
            }
            //continues to sort left and right of pivot
            if (left < rightIndex)
            {
                qSort(toSort, left, rightIndex);
            }
            if (leftIndex < right)
            {
                qSort(toSort, leftIndex, right);
            }
        }


    }

I just have one question, the quickSort I used I got on the internet and then converted it to use generics by myself. I understand how the actual sorting works. I just want to know, why don't I have to return something. I am a bit confused. I see it is actually switching the values of the lists, but I wonder how it accesses the list I sent. Because where I call it I can just do this

List<string> toSort = new List<string> { "C", "B", "A" };
                Sort<string> sort = new Sort<string>(toSort);
                cbxAlphabet.DataSource = toSort;

So I just use the original list and it will have A, B and C in the comboBox.

If anybody can explain this I would really appreciate it!

EDIT:

 public static class Sort<T> where T : IComparable<T>
    {
        public static void quickSort(List<T> sortList)
        {
            qSort(sortList, 0, sortList.Count - 1);
        }
        private static void qSort(List<T> toSort, int left, int right)
        {
            //set the indexes
            int leftIndex = left;
            int rightIndex = right;

            //get the pivot
            var pivot = toSort[left + (right - left) / 2];
            while (leftIndex <= rightIndex)
            {
                //check left values
                while (toSort[leftIndex].CompareTo(pivot)<0)
                {
                    leftIndex++;
                }
                //check right values
                while (toSort[rightIndex].CompareTo(pivot) >0)
                {
                    rightIndex--;
                }
                //swap
                if (leftIndex <= rightIndex)
                {
                    var tmp = toSort[leftIndex];
                    toSort[leftIndex] = toSort[rightIndex];
                    toSort[rightIndex] = tmp;

                    //move towards pivot
                    leftIndex++;
                    rightIndex--;
                }
            }
            //continues to sort left and right of pivot
            if (left < rightIndex)
            {
                qSort(toSort, left, rightIndex);
            }
            if (leftIndex < right)
            {
                qSort(toSort, leftIndex, right);
            }
        }


    }

Solution

  • It is because List<T> is a Reference Type.

    There are two kinds of types in C#: reference types and value types. Variables of reference types store references to their data (objects), while variables of value types directly contain their data. With reference types, two variables can reference the same object; therefore, operations on one variable can affect the object referenced by the other variable. With value types, each variable has its own copy of the data, and it is not possible for operations on one variable to affect the other (except in the case of in, ref and out parameter variables; see in, ref and out parameter modifier).

    In your example, the variable toSort and the private field Sort.toSort both reference the exact same list.