TECHY360
Everything You Need To Know About Tech

Sorting: Algorithms and data structures for beginners

0 25

In this part, we look at the five basic algorithms for sorting data in an array. Let’s start with the simplest — bubble sorting — and finish with “quick sort” (quicksort).

For each algorithm, in addition to explaining its work, we also indicate its complexity in memory and time in the worst, best and average case.

Swap method

To simplify the code and improve readability, we introduce a method Swapthat will swap the values ​​in the array by index.

void Swap (T [] items, int left, int right)
{
    if (left! = right)
    {
        T temp = items [left];
        items [left] = items [right];
        items [right] = temp;
    }
}

Bubble Sort

ComplexityBest caseAverageWorst case
TimeO (n)O (n 2 )O (n 2 )
MemoryO (1)O (1)O (1)

Bubble sorting is the easiest sorting algorithm. It passes through the array several times, at each stage moving the highest value from the unsorted to the end of the array.

For example, we have an array of integers:

During the first pass through the array, we compare values ​​3 and 7. Since 7 is greater than 3, we leave them as they are. After that, we compare 7 and 4. 4 less than 7, so we change their places, moving the seven one position closer to the end of the array. Now it looks like this:

Since there was at least one exchange of values, we need to go through the array again. As a result of this passage, we move the number 6 into place.

And again at least one exchange was made, which means we are going through the array again.

The next pass through the exchange is not performed, which means that our array is sorted, and the algorithm has completed its work.

public void Sort(T[] items)
{
    bool swapped;
 
    do
    {
        swapped = false;
        for (int i = 1; i < items.Length; i++) {
            if (items[i - 1].CompareTo(items[i]) > 0)
            {
                Swap(items, i - 1, i);
                swapped = true;
            }
        }
    } while (swapped != false);
}

Sort Inserts

ComplexityBest caseAverageWorst case
TimeO (n)O (n 2 )O (n 2 )
MemoryO (1)O (1)O (1)

Sorting inserts works by passing through the array and moving the desired value to the beginning of the array. After the next position has been processed, we know that all the positions before it are sorted, but not after it.

Important point: sorting by inserts processes the elements of the array in order. As the algorithm goes through the elements from left to right, we know that everything to the left of the current index is already sorted. This figure shows how the sorted part of the array increases with each pass:

Gradually sorted part of the array grows, and, in the end, the array will be ordered.

Let’s take a look at a specific example. Here is our unsorted array, which we will use:

The algorithm starts with index 0 and value 3. Since this is the first index, the array before it is inclusive is considered sorted.

Next, we go to the number 7. Because 7 is greater than any value in the sorted part, we go to the next element.

At this stage, elements with indices 0..1 are sorted, but about elements with indices 2..n nothing is known.

Next, the value 4 is checked. Since it is less than seven, we must move it to the correct position in the sorted part of the array. The question remains: how to define it? This is done by the method FindInsertionIndex. He compares the value passed to him (4) with each value in the sorted part, until he finds a place to insert.

So, we found the index 1 (between values ​​3 and 7). The method Insert inserts, deletes the inserted value from the array and shifts all values, starting from the index to insert, to the right. Now the array looks like this:

Now the part of the array, starting from the zero elements and ending with the element with index 2, is sorted. The next pass begins with index 3 and value 4. As the algorithm works, we continue to make such inserts.

When there are no more possibilities for inserts, the array is considered to be completely sorted, and the algorithm is finished.


public void Sort (T [] items)
{
    int sortedRangeEndIndex = 1;
 
    while (sortedRangeEndIndex <items.Length)
    {
        if (items [sortedRangeEndIndex] .CompareTo (items [sortedRangeEndIndex - 1]) <0)
        {
            int insertIndex = FindInsertionIndex (items, items [sortedRangeEndIndex]);
            Insert (items, insertIndex, sortedRangeEndIndex);
        }
 
        sortedRangeEndIndex ++;
    }
}
 
private int FindInsertionIndex (T [] items, T valueToInsert)
{
    for (int index = 0; index <items.Length; index ++) {
        if (items [index] .CompareTo (valueToInsert)> 0)
        {
            return index;
        }
    }
 
    throw new InvalidOperationException ("The insertion index was not found");
}
 
private void Insert (T [] itemArray, int indexInsertingAt, int indexInsertingFrom)
{
    // itemArray = 0 1 2 4 5 6 3 7
    // insertingAt = 3
    // insertingFrom = 6
    //
    // Actions:
    // 1: Save current index to temp
    // 2: Replace indexInsertingAt with indexInsertingFrom
    // 3: Replace indexInsertingAt with indexInsertingFrom at position +1
    // Move the items left one.
    // 4: Write the temp to the position in the array + 1.
    
 
    // Step 1.
    T temp = itemArray [indexInsertingAt];
 
    // Step 2.
 
    itemArray [indexInsertingAt] = itemArray [indexInsertingFrom];
 
    // Step 3.
    for (int current = indexInsertingFrom; current> indexInsertingAt; current--)
    {
        itemArray [current] = itemArray [current - 1];
    }
 
    // Step 4.
    itemArray [indexInsertingAt + 1] = temp;
}

Sort by selection

ComplexityBest caseAverageWorst case
TimeO (n)O (n 2 )O (n 2 )
MemoryO (1)O (1)O (1)

Sorting by choice is a kind of hybrid between bubble and sorting inserts. Like bubble sorting, this algorithm traverses the array time after time, moving one value to the correct position. However, unlike bubble sorting, it selects the smallest unsorted value instead of the largest. As with the sorting of inserts, the ordered part of the array is located at the beginning, while in the bubble sorting it is at the end.

Let’s look at the sorting work of choice on our unsorted array.

During the first pass, the algorithm uses the method FindIndexOfSmallestFromIndexto find the smallest value in the array and move it to the beginning.

Having such a small array, we can immediately say that the smallest value is 3, and it is already in the correct position. At this stage, we know that the smallest value is in the first position in the array (index 0), therefore, the beginning of the array is already sorted. Therefore, we begin the second pass – this time on indices from 1 to n – 1.

In the second pass, we determine that the smallest value is 4. We change it in places with the second element, the seven, after which 4 takes its right position.

Now, the unsorted part of the array begins with index 2. It grows by one element with each pass of the algorithm. If we have not made a single exchange on any pass, it means that the array is sorted.

After two more passes, the algorithm completes its work:

Related Posts
1 of 7
public void Sort(T[] items)
{
    int sortedRangeEnd = 0;
 
    while (sortedRangeEnd < items.Length)
    {
        int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd);
        Swap(items, sortedRangeEnd, nextIndex);
 
        sortedRangeEnd++;
    }
}
 
private int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEnd)
{
    T currentSmallest = items[sortedRangeEnd];
    int currentSmallestIndex = sortedRangeEnd;
 
    for (int i = sortedRangeEnd + 1; i < items.Length; i++)
    {         
        if (currentSmallest.CompareTo(items[i]) > 0)
        {
            currentSmallest = items[i];
            currentSmallestIndex = i;
        }
    }
 
    return currentSmallestIndex;
}

Merge sort

ComplexityBest caseAverageWorst case
TimeO (n · log n)O (n · log n)O (n · log n)
MemoryO (n)O (n)O (n)

Divide and rule

So far, we have considered linear algorithms. They use a little extra memory, but they have quadratic complexity. On the example of merge sort algorithm, we look at the type of “divide and rule» (the divide and Conquer) .

Algorithms of this type work by dividing a large problem into smaller ones that are easier to solve. We use them every day. For example, a search in the phone book is one example of such an algorithm.

If you want to find a man by the name of Petrov, you will not begin to search, starting with the letter A and turning one page at a time. You, most likely, will open the book somewhere in the middle. If you fall on the letter T, turn a few pages back, perhaps too much – to the letter O. Then you will go forward. Thus, turning back and forth an ever smaller number of pages, you will eventually find the one you need.

How effective are these algorithms?

Suppose the phonebook has 1000 pages. If you open it in the middle, you drop 500 pages that don’t have the person you are looking for. If you do not hit the desired page, you select the right or left side and again leave half of the available options. Now you need to view 250 pages. Thus, we divide our task in half again and again and can find a person in the phone book in just 10 views. This is 1% of the total number of pages that we would have to look through in a linear search.

Merge sort

In merge sorting, we split the array in half until each segment becomes one element in length. Then these areas return to the site (merge) in the correct order.

Let’s look at this array:

Divide it in half:

And we will divide each part in half until there are parts with one element left:

Now that we have divided the array into the shortest possible sections, we merge them in the correct order.

First, we get groups of two sorted elements, then we “assemble” them into groups of four elements and at the end, we collect everything together into a sorted array.

For the algorithm to work, we must implement the following operations:

  1. Operation for recursive division of an array into groups (method Sort).
  2. Merge in the right order (method Merge).

It should be noted that, unlike linear sorting algorithms, merge sorting will divide and glue the array, regardless of whether it was originally sorted or not. Therefore, despite the fact that in the worst case, it will work faster than the linear, at best, its performance will be lower than that of the linear. Therefore, merge sorting is not the best solution when it is necessary to sort a partially ordered array.

public void Sort(T[] items)
{
    if (items.Length <= 1)
    {
         return;
    }       

    int leftSize = items.Length / 2;
    int rightSize = items.Length - leftSize;
    T[] left = new T[leftSize];
    T[] right = new T[rightSize];
    Array.Copy(items, 0, left, 0, leftSize);
    Array.Copy(items, leftSize, right, 0, rightSize);
    Sort(left);
    Sort(right);
    Merge(items, left, right);
}   

private void Merge(T[] items, T[] left, T[] right)
{
    int leftIndex = 0;
    int rightIndex = 0;
    int targetIndex = 0;
    int remaining = left.Length + right.Length;
    while(remaining > 0)
    {
        if (leftIndex >= left.Length)
        {
            items[targetIndex] = right[rightIndex++];
        }
        else if (rightIndex >= right.Length)
        {
            items[targetIndex] = left[leftIndex++];
        }
        else if (left[leftIndex].CompareTo(right[rightIndex]) < 0)
        {
            items[targetIndex] = left[leftIndex++];
        }
        else
        {
            items[targetIndex] = right[rightIndex++];
        }
 
        targetIndex++;
        remaining--;
    }
}

Quick sort

ComplexityBest caseAverageWorst case
TimeO (n · log n)O (n · log n)O (n 2 )
MemoryO (1)O (1)O (1)

Quick Sort is another “divide and conquer” algorithm. It works by recursively repeating the following steps:

  1. Select a key index and divide by it an array into two parts. This can be done in different ways, but in this article we use a random number.
  2. Move all elements greater than the key to the right side of the array, and all elements less than the key to the left. Now the key element is in the correct position – it is larger than any element on the left and less than any element on the right.
  3. Repeat the first two steps until the array is completely sorted.

Let’s look at the work of the algorithm on the following array:

First, we randomly select a key element:

int pivotIndex = _pivotRng.Next (left, right);

Now, when we know the key index (4), we take the value located on this index (6) and transfer the values ​​in the array so that all numbers greater than or equal to the key are in the right side, and all numbers less than the key are in the left . Please note that in the process of transferring values, the index of the key element may change (we will see it soon).

Moving values ​​is done by the method partition.

At this stage, we know that value 6 is in the correct position. Now we repeat this process for the right and left parts of the array.

We recursively call a method quicksorton each of the parts. The key element in the left part is the five. When moving values, it will change its index. The main thing is to remember that it is the key value that is important for us, not its index.

Again, use the quicksort:

Once again:

We have one unsorted value left, and since we know that everything else is already sorted, the algorithm terminates.

Random _pivotRng = new Random();
 
public void Sort(T[] items)
{
    quicksort(items, 0, items.Length - 1);
}
 
private void quicksort(T[] items, int left, int right)
{
    if (left < right)
    {
        int pivotIndex = _pivotRng.Next(left, right);
        int newPivot = partition(items, left, right, pivotIndex);
 
        quicksort(items, left, newPivot - 1);
        quicksort(items, newPivot + 1, right);
    }
}
 
private int partition(T[] items, int left, int right, int pivotIndex)
{
    T pivotValue = items[pivotIndex];
 
    Swap(items, pivotIndex, right);
 
    int storeIndex = left;
 
    for (int i = left; i < right; i++)
    {
        if (items[i].CompareTo(pivotValue) < 0)
        {
            Swap(items, i, storeIndex);
            storeIndex += 1;
        }
    }
 
    Swap(items, storeIndex, right);
    return storeIndex;
}

Conclusion

This concludes our series of articles on algorithms and data structures for beginners. During this time, we looked at linked lists, dynamic arrays, binary search tree and sets with examples of C # code.

Get real time updates directly on you device, subscribe now.

Comments
Loading...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More