Introduction to Sorting and Sorting Algorithms

Introduction to Sorting and Sorting Algorithms - Printable Version

+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: Coding (https://sinister.li/Forum-Coding--71)
+--- Thread: Introduction to Sorting and Sorting Algorithms (/Thread-Introduction-to-Sorting-and-Sorting-Algorithms)

Pages: 1 2 3 4

Introduction to Sorting and Sorting Algorithms - Ex094 - 08-23-2013

*Bold items indicate importance

Hello HC!

Today I will introduce to an important topic in Computer Science and that is Sorting, I will try to explain as easy as I can for user understanding. We will also be explaining 2 related algorithms that make our work more easier but be aware that I've written the Algorithm code in Python 3.3 so be sure to have a Python understanding. So first lets see what Sorting is?

What is Sorting?

Lets take an example of a List of Names:

Code:
names = ['Deque', 'bluedog.tar.gz', 'Arkphaze', 'HC', 'noize', 'Linuxephus']

Now you can see that each name has a different length and can be arranged by either placing them from Short Length to Long Length,

Hence Sorting can be defined as:

The process of placing (or arranging) elements from a collection (or a List of items) in some kind of order

So if we Sort out the names on the basis of Length of each individual then the correct sorted list would be:

Code:
['HC', 'Deque', 'noize', 'Arkphaze', 'Linuxephus', 'bluedog.tar.gz']

Now that you've understood about the term Sorting, lets discuss about some Sorting Algorithms that make your work easier. But first we need to know how a sorting algorithm works.

How a Sorting Algorithm Works

A Sorting Algorithm analyzes the sorting process such that it arranges the elements of a list in a certain order. In the process of Sorting we need to devise a way or a system which will then compare certain values and put them in the right order. Sorting also involves comparing 2 adjacent values, evaluating whether the former one is large or small or vice versa. As the values in the beginning are not in order, we also need to make a system that will correct the position of the items using the principle stated above. This process of exchanging item position is also known as Swapping and once the items are swapped and no more items are swappable, then the list is said to be Sorted i.e it's in order.

Efficiency of Sorting Algorithm

It is to be remembered that the total number of all the possible swaps done by the algorithm are responsible in evaluating the efficiency of the particular algorithm.

Usage of Sorting Algorithms

Since the beginning of computing, Sorting of data has been a complex task and has required complex program to do such work, A complete application of sorting algorithms is present in this site http://algs4.cs.princeton.edu/25applications/

Sorting Algorithms

We will now discuss Sorting Algorithms, I will go in depth as far as I can to make them understandable to my users. In this tutorial we will study:

Bubble Sort Algorithm

1) Bubble Sort Algorithm

This is a simple most and easy to implement sorting algorithm, it works by going repeatedly through the list elements and comparing the adjacent elements. If the adjacent elements are in the wrong order, they are Swapped. This process is repeated till the time that there is no swapping left meaning that the List is now Sorted.

For Example, consider a list containing numbers in unsorted form

Code:
[50, 4, 90]

First the bubble sort will compare the first two values i.e 50 and 4. As the second item is smaller than the first one, their position gets swapped
so

Code:
[50, 4, 90, 12]

Becomes

Code:
[4, 50, 90, 12]

But still this list is unsorted, it was just to make you understand the Swap case. Now we shall study it step by step

Explanation

To understand this algorithm step by step, we have a list of numbers which 8 students obtained in their entry test out of 200. Our task is to sort out the list, the list is:

Code:
[122, 190, 102, 90, 75, 120, 105, 109]

Lets start with the first 2 adjacent items which are 122 and 190. These two values are in order and the former is smaller than the later hence no swapping is required so we move to the next value which is 190 and 102. The latter being smaller than the former one hence their positions are swapped so it becomes:

Code:
[122, 190, 102, 90, 75, 120, 105, 109] ===>[122, 102, 190, 90, 75, 120, 105, 109]

Now, the algorithm moves to 190 and 90. The same case as the latter is smaller than the former one and their position gets swapped. The list is now:

Code:
[122, 102, [190, 90], 75, 120, 105, 109] ===>[122, 102, [90, 190], 75, 120, 105, 109]

[122, 102, 90, [190, 75], 120, 105, 109] ===>[122, 102, 90, [75, 190], 120, 105, 109] 75 < 190 Position Swapped

[122, 102, 90, 75, [190, 120], 105, 109] ===>[122, 102, 90, 75, [120, 190], 105, 109] 120 < 190 Position Swapped

[122, 102, 90, 75, 120, [190, 105], 109]  ===>[122, 102, 90, 75, 120, [105, 190], 109] 105 < 190 Position Swapped

[122, 102, 90, 75, 120, [190, 105], 109]  ===>[122, 102, 90, 75, 120, 105, 190, 109] 105 < 190 Position Swapped

[122, 102, 90, 75, 120, 105, [190, 109]]  ===>[122, 102, 90, 75, 120, 105, [109, 190]] 109 < 190 Position Swapped

Till here our first Phase is complete, still the list is not sorted hence the algorithm will again go through the list items and swap them.

Code:
[[122, 102], 90, 75, 120, 105, 109, 190]  ===>[[102, 122], 90, 75, 120, 105, 109, 190] 102 < 122 Position Swapped

[102, [122, 90], 75, 120, 105, 109, 190]  ===>[102, [90, 122], 75, 120, 105, 109, 190] 90 < 122 Position Swapped

[102, 90, [122, 75], 120, 105, 109, 190]  ===>[102, 90, [75, 122], 120, 105, 109, 190] 75 < 122 Position Swapped

[102, 90, 75, [122, 120], 105, 109, 190]  ===>[102, 90, 75, [120, 122], 105, 109, 190] 120 < 122 Position Swapped

[102, 90, 75, 120, [122, 105], 109, 190]  ===>[102, 90, 75, 120, [105, 122], 109, 190] 105 < 122 Position Swapped

[102, 90, 75, 120, 105, [122, 109], 190]  ===>[102, 90, 75, 120, 105, [109, 122], 190] 109 < 122 Position Swapped

[102, 90, 75, 120, 105, 109, [122, 190]]  ===>[102, 90, 75, 120, 105, 109, 122, 190] 190 > 122 In order already, No swap needed

This completes our second phase, but again the list is still out of order hence the algorithm will repeat the process again.

Code:
[[102, 90], 75, 120, 105, 109, 122, 190]  ===>[[90, 102], 75, 120, 105, 109, 122, 190] 90 < 102 Position Swapped

[90, [102, 75], 120, 105, 109, 122, 190]  ===>[90, [75, 102], 120, 105, 109, 122, 190] 75 < 102 Position Swapped

[90, 75, [102, 120], 105, 109, 122, 190]  ===>[90, 75, 102, [120, 105], 109, 122, 190] No Shift Needed

[90, 75, 102, [120, 105], 109, 122, 190]  ===>[90, 75, 102, [105, 120], 109, 122, 190] 105 < 120 Position Swapped

[90, 75, 102, 105, [120, 109], 122, 190]  ===>[90, 75, 102, 105, [109, 120], 122, 190] 109 < 120 Position Swapped

[90, 75, 102, 105, 109, 120, [122, 190]]  ===>[90, 75, 102, 105, 109, 120, 122, 190] No Swaps possible, Sorted List

This ends our third phase and this was the final stage. After this stage no other swaps are possible hence the List of the numbers are now Sorted

You can clearly see that the algorithm has sorted out the items in the list to the correct order:

Code:
[90, 75, 102, 105, 109, 120, 122, 190]

Python Implementation

Being a Python Coder, I've coded a Python Implementation for Bubble Sort. Here's the code:

Code:
def bubblesort(items):

	length = len(items) - 1 #Length of the list to be sorted
 
	swapped = False #Swapping set to False as Default

	while swapped != True:

		for i in range(0, length):

			if items[i] > items[i + 1]: //Compare the adjacent Items

				a,b = items.index(items[i]), items.index(items[i + 1]) //Stores the items index number for swap

				items[b], items[a] = items[a], items[b] //Swaps the items place

				print(items) //Prints the swapped condition

				swapped = True //Repeat

				pass

			swapped = False

			pass

		pass

You will get similar result as an output when you'll use my Python Implementation on the example we discussed above, Here's a Screen Shot

[Image: KKyNc6h.png]

Insertion Sort

This is a simple sorting algorithm which works by going through one item at a time
in the list as it iterates, at the last presenting an array of the sorted elements.

Insertion Sort Advantages:

Code:
* Simple implementation

* Efficient for (quite) small data sets

* Adaptive (i.e., efficient) for data sets that are already substantially sorted the time complexity is O(n + d), where d is the number of inversions

* More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)

* Stable; i.e., does not change the relative order of elements with equal keys

* In-place; i.e., only requires a constant amount O(1) of additional memory space

* Online; i.e., can sort a list as it receives it

Explanation:

As the process starts, the list picks an item from the list say List[i]th Item. It then compares that item with the largest elements in the list. If the item previously checked is larger than the selected one (i.e the element currently selected), then the position is swapped. If you still don't understand have a look at this diagram:

Now if the chosen value is smaller than the selected value, No swap will be required and the algorithm moves to the next value.

Here's a good animation of Insertion sort:

[Image: Insertion-sort-example-300px.gif]

Pseudo Code:

Code:
def insertion_sort(item):

	for i in range(1, len(item)): #The first item is considered to be sorted

		val = item[i] #Save the current value for insertion

		j = i - 1 #Decrease the value till val is greate than J (i.e the hole reaches the start of the list)

		while j >= 0 and item[j] > val: #Iteration

			item[j + 1] = item[j] #If condition persists, swap the greater value

			j = j - 1 #Value down

		item[j + 1] = val #Insert value to the hole

	return item #Return Sorted List

Code Explanation:

Consider this list:

Code:
[3,7,4,9]

As the code is executed, i attains the value 1 so the value of the variable val becomes 7 (As 1 is the index for 7). Here our value has been stored for insertion later when the suitable place has been found. The condition of the while loop becomes false because the item[j]th (i.e 3) is not greater than val (i.e 7), and the value of val remains same as the second last line is executed.

At the second loop, i becomes 2 and the value of val becomes 4 (i.e the index number of 4 in the list), the value of j becomes 1 (as j = i - 1 => 2 - 1 => 1), so the loop condition is satisfied as follows:

Code:
1) J (1) greater than 0 [Which is True so first condition satisfied]
2) item[1] (7) is greater than the val (4) [Which is also true]

As stated, if the previously checked item (7) is greater than the selected one (4), then their positions will be swapped and hence 4 will be inserted before 7. But not so fast! As the 11th line is executed, the 4 becomes a 7 too and the code moves on to the next line, J becomes 0 again, so we goto the 2nd last line. This is the part where we insert the value stored in the variable Val (i.e 4).

Code:
item[j + 1] = val

Means that:

Code:
item[0 + 1] = 4 => item[1] = 4 #Replace item[1]th item with 4

So our list becomes:

Code:
[3, 4, 7, 9]

And hence our list is now sorted out!

RE: Introduction to Sorting and Sorting Algorithms - Deque - 08-23-2013

Thank you. You are the first Dev to write a tutorial about algorithms for our project (if I am not mistaken and haven't overlooked one).
Your explanations are good. You can add some words about stability as this is an important characteristic of sorting algorithms.

I don't think the time complexity is that important. Most people don't understand how to use it correctly and think they should always take the algorithm with the best time complexity. So it doesn't matter to me if you add that.

The bubblesort can be made more efficient which is explained on wikipedia too: https://en.wikipedia.org/wiki/Bubblesort (see under optimizing bubble sort)
It is just a little change that is worth knowing.

RE: Introduction to Sorting and Sorting Algorithms - Psycho_Coder - 08-23-2013

Nice and clean thread. The examples are good and the gif animation is a charm.

Efficiency of any sorting algorithm depends on resource usage and the time taken to complete the sort. We consider three cases Worst case, average case and best base for the analysis for any algorithm. In case of bubble sort the efficiency depends on the looping pattern. We have got two nested loops.

Code:
for(int x=0; x<n; x++)
	{
		for(int y=0; y<n-1; y++)
		{
			if(array[y]>array[y+1])
			{
				int temp = array[y+1];
				array[y+1] = array[y];
				array[y] = temp;
			}
		}
	}

Have a look at the above code, in order to determine the complexity of this loop, we calculate the number of comparisons that have to be made. On the first iteration of the outer loop we are trying to place the largest element and so there have to be n - 1 comparisons, the first comparison is made between the first and second elements, the second is made between the second and third elements, and so on until the n-1th comparison is made between the n-1th and the nth element.

On the second iteration of the outer loop, there is no need to compare the against the last element of the list, because it was already put in the correct place on the previous pass. Therefore, the second iteration requires only n-2 comparisons. This pattern continues until the second-to-last iteration of the outer loop when only the first two elements of the list are unsorted; clearly in this case, only one comparison is necessary.

The total number of comparisons is:-

(n - 1) + (n - 2)...(2) + (1) = n(n - 1)/2 or O(n^2) .

There is also a Modified bubble sort in which the best case time complexity is O(n) and you have implemented this in your thread.

Code:
private static int[] bubbleSort(int[] array) {
    boolean swapped = true;
    for(int i = array.length - 1; i > 0 && swapped; i--) {
        swapped = false;
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                swapped = true;
            }
        }
    }
    return array;
}

Have a look :- http://doyle.wcdsb.ca/ICS3MI/Notes/sort%20and%20search/notes%20sort%20modified%20bubble.htm

Have a look for efficiency related things :- http://users.soe.ucsc.edu/~sbrandt/13H/slides/DSChapter9.pdf

If you need more explanation or resources to study algorithmic analysis then please do tell.

Another suggestion, before explaining Quicksort explain selection sort, insertion sort and then the concept of Divide and conquer technique and then discuss quick sort

Code:
for(int x=0; x<n; x++)
	{
		for(int y=0; y<n-1; y++)
		{
			if(array[y]>array[y+1])
			{
				int temp = array[y+1];
				array[y+1] = array[y];
				array[y] = temp;
			}
		}
	}

Code:
private static int[] bubbleSort(int[] array) {
    boolean swapped = true;
    for(int i = array.length - 1; i > 0 && swapped; i--) {
        swapped = false;
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                swapped = true;
            }
        }
    }
    return array;
}

RE: Introduction to Sorting and Sorting Algorithms - Ex094 - 08-23-2013

@Deque @Psycho_Coder Thank you for your replies and tips guys, And yes I'll be adding more stuff to this tutorial as it's just the half of my HC Dev Project

RE: Introduction to Sorting and Sorting Algorithms - Psycho_Coder - 08-23-2013

The title of the thread is a bit misleading. According to the present title a user will guess and it will appear to him that He is gonna get a theoretical explanation of sorting and various sort algorithms and general techniques whereas this thread mainly focuses on Bubble sort. So the title imho should be "Introduction to Sorting : Bubble Sort" as this will tell the user that he is going to get details on bubble sort and general sorting theory. I hope I made myself clear.

Thank you,
Sincerely,
Psycho_Coder

RE: Introduction to Sorting and Sorting Algorithms - Ex094 - 08-23-2013

(08-23-2013, 06:16 AM)Psycho_Coder Wrote: The title of the thread is a bit misleading. According to the present title a user will guess and it will appear to him that He is gonna get a theoretical explanation of sorting and various sort algorithms and general techniques whereas this thread mainly focuses on Bubble sort. So the title imho should be "Introduction to Sorting : Bubble Sort" as this will tell the user that he is going to get details on bubble sort and general sorting theory. I hope I made myself clear.

Will be adding more details to this article as I said previously