Lesson 7

Objectives

By the end of this lesson you will be able to:

• Understand the need for sorting algorithms
• Understand and implement the bubblesort algorithm
• Understand and implement the quicksort algorithm
• Understand how to debug a program
• Understand how to sort an array

Introduction to Sorting Algorithms

Sorting algorithms, such as BubbleSort and QuickSort, arrange items in a list in a particular order. Understanding sorting algorithms can help you understand, analyze, and compare different methods of problem solving.

Sorting algorithms are algorithms that arrange the items in a list in a certain order. For example, you can use a sorting algorithm to sort a list of students in ascending order of their last name. In the early days of data processing, sorting was an important problem that attracted a lot of research. These days, you can find basic sorting capabilities already built into most popular libraries and data structures. For example, in the .NET Framework, you can make use of the Array.Sort method to sort an array. However, it is still important to look at sorting as a way to understand problem solving and algorithm analysis. Be sure to pay close attention to the comments in the coding examples used in this lesson. They are there to help you learn and understand how the code works step by step.

In this section, you will take a look at two common sorting algorithms, BubbleSort and QuickSort.

Visual Studio Solution for this tutorial (link will download zip file).

BubbleSort

The BubbleSort algorithm uses a series of comparison and swap operations to arrange the elements of a list in the correct order.

BubbleSort works by comparing two elements to check whether they are out of order; if they are, it swaps them. The algorithm continues to do this until the entire list is in the desired order. BubbleSort gets its name from the way the algorithm works: As the algorithm progresses, the smaller items are “bubbled” up.

Let’s visualize BubbleSort with the help of an example. Say you want to arrange all the items in the following list in ascending order: (20, 30, 10, 40). These items should be arranged from smallest to largest. The BubbleSort algorithm attempts to solve this problem in one or more passes, with each pass completely scanning the list of items. If the algorithm encounters out-of-order elements, it swaps them. The algorithm finishes when it scans the whole list without swapping any elements. If there were no swaps, then none of the elements were out of order and the list has been completely sorted.

 

As shown in Table 3-1, at the end of first pass, BubbleSort has performed one swap, and there is the possibility that the items are not yet completely sorted. Therefore, BubbleSort gives the list another pass, as depicted in Table 3-2.

 

At the end of second pass, BubbleSort has performed one more swap, so it can’t yet guarantee that the list is completely sorted. Thus, BubbleSort gives the list another pass, as shown in Table 3-3.

 

At the end of the third pass, BubbleSort didn’t perform any swaps. This guarantees that the list is now in sorted order and the algorithm can finish.

In C#, the BubbleSort algorithm can be expressed by the following method:

static int[] BubbleSort(int[] numbers)
{
    bool swapped;
    do
    {
        swapped = false;
        for (int i = 0; i < numbers.Length - 1; i++)
        {
            if (numbers[i] > numbers[i + 1])
            {
                //swap
                int temp = numbers[i + 1];
                numbers[i + 1] = numbers[i];
                numbers[i] = temp;
                swapped = true;
            }
        }
    } while (swapped == true);
    return numbers;
}

You can test the BubbleSort() method in a new C# Console application, by replacing the Main() method with this code:

static void Main(string[] args)
{
    int[] numbers = { 20, 30, 10, 40 };

    BubbleSort(numbers);

    for (int i = 0; i < 4; i++)
    {
        Console.WriteLine(numbers[i]);
    }

}

. . . and then copy and paste the BubbeSort() method in the same Program class right below the Main() method.

Bubble Sort Analysis

static int[] BubbleSort(int[] numbers)
{
    bool swapped;
    do
    {
        swapped = false;
        //loops through numbers array
        //comparing each left element's value to value of element on its right
        for (int i = 0; i < numbers.Length - 1; i++)
        {
            if (numbers[i] > numbers[i + 1]) //compares left value to right value
            {
                //swap
                int temp = numbers[i + 1]; //temporarily hold right value
                numbers[i + 1] = numbers[i]; //changes right value to left value
                numbers[i] = temp; //changes left value to right value
                swapped = true; //indicates a swap was made during this pass
                    //once the for loop completes if swap is still true,
                    //swap is set back to false
                    //and for loop comparison on entire array is run again.
            }
        }
    } while (swapped == true);
    //if no numbers have been swapped in the last pass, sort is ended
    return numbers; //returns sorted array
}        

Watch the bubble sort in action in Visual Studio by adding a break to the BubbleSort method and then run it in debug mode (F5), once you hit the break step through the BubbleSort method (F11) line by line keeping an eye on the Locals tab in the Locals window as shown in this figure.

QuickSort

The QuickSort algorithm uses the partitioning and comparison operations to arrange the elements of a list in the correct order. The QuickSort algorithm uses the divide-and-conquer technique to continually partition a list until the size of the problem is small and hardly requires any sorting. The following steps explain this process in greater detail:

• A list of size zero or one is always sorted by itself.
• For a bigger list, pick any element in the list as a pivot element. Then, partition the list in such a way that all elements smaller than or equal to the pivot element go into the left list and all elements bigger than the pivot element go into the right list. Now, the combination of the left list, pivot element, and right list is always in sorted order if the left and the right list are in sorted order.
• The problem is now partitioned into two smaller lists, the left list and the right list.
• Both these lists are solved using the technique described in the bullets above.
• Finally, all the small sorted lists are merged in order to create the final complete sorted list. The following table explains the QuickSort algorithm with a brief example.

So far, the main shortcoming of the QuickSort algorithm might appear to be the additional memory required by the creation of separate smaller lists. However, creating separate lists is not necessary. Using a slightly modified technique, the array can be partitioned in place, as shown in the following code listing:

static int Partition (int[] numbers, int left, int right, int pivotIndex)
{
    int pivotValue = numbers[pivotIndex];
    // move pivot element to the end
    int temp = numbers[right];
    numbers[right] = numbers[pivotIndex];
    numbers[pivotIndex] = temp;
    // newPivot stores index of the first number bigger than pivot
    int newPivot = left;
    
    for (int i = left; i < right; i++)
    {
        if (numbers[i] <= pivotValue)
        { 
            temp = numbers[newPivot];
            numbers[newPivot] = numbers[i];
            numbers[i] = temp;
            newPivot++;
        }
    }

    //move pivot element to its sorted position
    temp = numbers[right];
    numbers[right] = numbers[newPivot];
    numbers[newPivot] = temp;

    return newPivot;
} 

With this technique, first the pivot element is moved to the end of the array. Then, all the elements less than or equal to the pivot element are moved to the front of the array. Finally, the pivot element is placed just before the element greater than itself, effectively partitioning the array.

This partitioning algorithm can then be used by QuickSort to partition the list, reduce the problem to smaller problems, and recursively solve it:

static int[] QuickSort(int[] numbers, int left, int right)
{
    if (right > left)
    {
        int pivotIndex = left + (right - left) / 2;
        //partition the array
        pivotIndex = Partition(numbers, left, right, pivotIndex);
        //sort the left partition
        QuickSort(numbers, left, pivotIndex - 1);
        // sort the right partition
        QuickSort(numbers, pivotIndex + 1, right);
    }
    
    return numbers;
}            

Because of its partitioning approach, the QuickSort algorithm is much faster than the BubbleSort algorithm.

Array Sorting Example

int counter = 0;
string[] array = new string[10];

while (counter < 10)
{
    Console.Write("Enter a Number:");
    array[counter] = Console.ReadLine();
    counter++;
}

Array.Sort(array);
counter = 0;

while (counter < 10)
{

    Console.WriteLine(array[counter]);
    counter++;
}
                    
                                 
            

Summary

In this lesson you learned about the need for sorting algorithms, how to implement the bubblesort algorithm, how to implement the quicksort algorithm, how to debug a program, and how to sort an array