Simple Selection Sort won't sort-CodePudding

I'm new to algorithms and I tried to write a selection sort. With some help from the internet I have a script that should work, but doesn't. The result after the sort method is a list that is still unsorted.

I'm not sure if I missed anything and my code looks the same as the ones online.

Product.cs

public class Product
{
    public string Name { get; set; }
    public double Price { get; set; }
}

Order.cs

    public class Order
    {
        public List<Product> listOfProducts = new List<Product>(){
            new Product(){ Name="Item1", Price=2.55 },
            new Product(){ Name="Item2", Price=1.92 },
            new Product(){ Name="Item3", Price=2.12 }
        };

        public List<Product> GetAllProducts(){

            return this.listOfProducts;

        }

    
        public void SortProductsByPrice(){
                int min = 0;
                for (int i = 0; i < this.listOfProducts.Count - 1; i  )
                {
                    min = i;
                    for (int j = 0; j < this.listOfProducts.Count; j  )
                    {
                        if (listOfProducts[j].Price < listOfProducts[min].Price)
                        {
                            min = j;
                        }
                    }
    
                    Product temporary = listOfProducts[min];
                    listOfProducts[min] = listOfProducts[i];
                    listOfProducts[i] = temporary;
                }
        }
    
    }

Program.cs

static void Main(string[] args)
        {
            Order order = new Order();

            // unsorted list
            foreach (Product pro in order.GetAllProducts())
            {
                Console.WriteLine(pro.Price);
            }
            Console.WriteLine("------------------------------------------");
            order.SortProductsByPrice();

            // sorted list
            foreach (Product pro in order.GetAllProducts())
            {
                Console.WriteLine(pro.Price);
            }
            Console.ReadLine();
        }

CodePudding user response：

The problem in your code is in the nested loop.

If you take a closer look at the algorithm, you'll see that:

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

You're re-comparing your values with what you've already sorted, which you should not do. You're not getting a sorted list because by the end of your code, the values are being swapped over and over until they get back to their original order. A simple fix is by changing the nested for loop like this:

public void SortProductsByPrice()
{
    int min = 0;
    for (int i = 0; i < this.listOfProducts.Count - 1; i  )
    {
        min = i;
        for (int j = i   1; j < this.listOfProducts.Count; j  )
        {
            if (listOfProducts[j].Price < listOfProducts[min].Price)
            {
                min = j;
            }
        }

        Product temporary = listOfProducts[min];
        listOfProducts[min] = listOfProducts[i];
        listOfProducts[i] = temporary;
    }
}

So precisely, we just changed 1 line:

for (int j = i   1; j < this.listOfProducts.Count; j  )  
             ^^^^^

If you take another look at the pseudo-code in the above link, you'll see that this function now resembles it:

procedure selection sort 
    list  : array of items
    n     : size of list

    for i = 1 to n - 1
        /* set current element as minimum*/
        min = i    
  
        /* check the element to be minimum */

        for j = i 1 to n 
            if list[j] < list[min] then
                min = j;
            end if
        end for

      /* swap the minimum element with the current element*/
        if indexMin != i  then
            swap list[min] and list[i]
        end if
    end for
    
end procedure