0

I have created two functions that sorts a list using bubble sort, but I would like to change the sort style to quick sort.

I found this quick sort algorithm

http://snipd.net/quicksort-in-c

These are my two functions:

    protected void sort_by_section_name()
    {
        int num1, num2;
        for (var i = section_names.Count - 1; i > 0; i -= 1)
        {
            for (var j = 0; j < i; j += 1)
            {
                num1 = get_number_from_section(section_names[j]);
                num2 = get_number_from_section(section_names[j + 1]);
                if (num1 > num2)
                {
                    swap_list_strings(section_names, j, j + 1);
                    swap_object_items(item_group_list, j, j + 1);
                }
            }
        }
    }

    protected void sort_items()
    {
        int num1, num2;
        List<SPListItem> temp;
        for (var k = 0; k < item_group_list.Count; k += 1)
        {
            temp = (List<SPListItem>)item_group_list[k];
            for (var i = temp.Count - 1; i > 0; i -= 1)
            {
                for (var j = 0; j < i; j += 1)
                {
                    num1 = Convert.ToInt32((temp[j])[ORDER_BY_COLUMN]);
                    num2 = Convert.ToInt32((temp[j + 1])[ORDER_BY_COLUMN]);
                    if (num1 > num2)
                    {
                        swap_list_items(temp, j, j + 1);
                    }
                }
            }
        }
    }

For sort_items, its an array of arrays, so the bubble sort stuff is in a for loop.

I don't understand how to change these two functions into using the quicksort.

Can someone please help me?

Improve this question
8
  • 2
    Do you realise the .NET framework has quicksort built in? Or is this for homework? Commented Aug 23, 2012 at 19:04
  • 5
    Outside of an academic environment you almost never need to write your own sort algorithm. Just use whatever the language's library uses unless you have a compelling reason not to. Commented Aug 23, 2012 at 19:04
  • Blah blah, reinventing the wheel. Commented Aug 23, 2012 at 19:04
  • the problem is the items in the array are SPListItems, and it needs to sort based on an attribute of the item. If I directly compare the item object it won't work. I need to extract the attribute value then compare those values as seen in my current bubble sort functions above. Commented Aug 23, 2012 at 19:09
  • @ Chris S. => this isn't homework, I just dont understand how to compare it and the reason why is in the above comment by me. Commented Aug 23, 2012 at 19:09

2 Answers 2

Reset to default
3

You don't need to write it yourself in .NET - you can use:

  1. Array.Sort for a basic array of items
  2. LINQ - OrderBy for example with a List<string> (make sure you have using System.Linq at the top of the class)
  3. If you're feeling adventurous, look into IComparable
  4. Use myItems.Sort() which sorts them in place.

For what you want, the easiest way to get started is using #2, here's an example:

List<SPListItem> myItems = GetSomeItems();
myItems = myItems.OrderBy(i => i["MyField"]).ToList();

foreach (var item in sortedItems)
    Console.WriteLine(item);

Without knowing the fields you're after, or much about the Sharepoint object that's a bit of a guess, there's are about 5 different ways of doing it in .NET with comparable interfaces (some more info here). As you can't change the SPListItem class then Sort or LINQ maybe easiest.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

so to use this in my example, what do I replace item with?
@omega can you post the definition of SPListItem
@ChrisS. msdn.microsoft.com/en-us/library/… It's for dealing with SharePoint. Queries return collections of SPListItems.
yes, but I did what Servy said it's now a lot easier to manage.
2

So you have a List<SPListItem> and you want them sorted, using an efficient sorting algorithm (aka not bubblesort) based on the numeric value of some field. This is easy, and doesn't involve you re-implementing quicksort.

List<SPListItem> list = ...;

var sortedData = list.OrderBy(item => Convert.ToInt32(item["fieldName"]));

It's also worth noting that when possible it's usually better to sort your data on the database, rather than on the webserver. You should be able to add an Order By clause to the CAML query generating those SPListItems and let it do the sort.

It appears that you're sorting two different data structures that are "parallel" (the item at the same index of both structures "belong" together). This is generally undesirable. While there are ways to perform a sort on both structures, what you really should be doing is making a single structure such that each item holds onto everything that logically represents that one item. In many cases this means creating a new class that has properties for each piece of data. You can then populate a collection of this new composite class and sort that.

Improve this answer

11 Comments

when I tried this, it says List<string> doesn't have a method .Orderby
You need to add using System.Linq as this uses an extension method from within that namespace. You also need to be on C# 3.5+. There are ways to do this from C# 1.0 that don't involve writing your own sort, but this is the shortest/most readable code.
I tried this section_names = section_names.OrderBy(item => get_number_from_section( item[SECTION_COLUMN].ToString() )); but it getting an error, invalid argument. What is the item variable? Where is it defined?
item => item is a "lambda", which means that it's a function that takes a parameter named 'item' and returns whatever is on the right hand side of the =>. The compiler is smart enough to infer it's Type based on context. It essentially means, "for each item in the list, use this function to get something (an int here) out of this SPListItem and use that as the sorting metric". As for the error, it it seems that the function you're using doesn't take just a string, or it doesn't return any value.
nvm my last comment, the section_names is a List<string> where each of it's strings begin with a number, and it needs to sort based on that. So now I tried section_names = section_names.OrderBy(item => get_number_from_section( item )); but i am getting a cast error, so i think i need to cast somewhere. But the other issue is, there is another array that needs to be in sync with this, i.e. when ever two things gets swaped it needs to occur with the other array as seen in my bubble sort code in the top.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.