Sorting reminds me of the last two week’s lectures. Sorting
and efficiency are things we spend a long time to talk about in this period of
time. I would like to begin form ask myself, what actually the sorting is and how
can a sorting algorithm said to be efficient.
This is the definition of sorting on Wikipedia.
This is the definition of sorting on Wikipedia.
Sorting is any process of
arranging items according to a certain sequence or in different sets, and
therefore, it has two common, yet distinct meanings:
1. ordering:
arranging items of the same kind, class or nature, in some ordered sequence,
2.categorizing:
grouping and labeling items with similar properties together (by sorts).
To make it clear. Using my picture as an example of sorting.
You can see that my photos are listed in random and now I want to sort them into the order by age.
The result shown as follow
For
example, we can sort a list of integer from great to small or from small to
great or sort some apples form big size to small size. Those actions are all
sorting objects. Like we can call the python built-in method sort() to sort
number and letters.
>>>a
= [3,4,6,1,8,0]
>>>a.sort()
>>>a
[0,
1, 3, 4, 6, 8]
>>>b
= ['g','e','w','s']
>>>
b.sort()
>>>b
['e',
'g', 's', 'w']
However,
u can see that is method is only can sort specific things in specific order.
Therefore, we need other method and algorithm to help us sort things we want in
orders we want. Like selection sort, insertion sort and bubble sort and so on. Each sorting algorithm has their own way to sort objects and they may run different times to sort same object. Some algorithms good at sorting specific objects.
For example, to sort [54,26,93,17,77,31,44,55,20]
merge sort uses 297 steps
insertion sort uses 106 steps
gapinsertion sort uses 181 steps
selection sort uses 132 steps
bubble sort use 154 steps
Therefore, you can find there is a such big difference between those sorting algorithms for their efficiency.
Yes, EFFICIENCY. Now I would like to talk about that. For us, to decide using an algorithm to sort different objects depends on the efficiency. In that case, we need to know, when there are more and more objects contained in the list we sort, how the runtime grows according to the way each sorting method use to sort. To analysis the growing of runtime, we introduce Big-oh.
What is big O?
Big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.Big O notation is used to classify algorithms by how they respond to changes in input size.
For example, for 1<a<b, n^a in O(n^b), or a^n in O(a^b). These are sample examples.
To see a little bit complex example.Lets say that the function is T(n)
max=0 1
for i in range(0,n): 2
for j in range(i,n): 3
sum = 0 4
for k in range(i,j): 5
sum = sum+L[k] 6
if sum > max: 7
sum = max 8
We can say that T(n) is O(n^3)
The reasons are listed as follow.
Line 6 takes 1 step
The loop on lines 5-6 iterates at most n times, because i is from 0 to n-1 and j is from i to n-1, so the number of steps is less than n
Lines 4-8 add at most 4 steps.
However, the loop on 3-8 iterates at most n times and 2-8 iterates exactly n times.
line 1 add 1 step.
Therefore, the number of steps is <=2n^3+1 <=2n^3+n^3 <=3n^3 for n greater than 1
In the lab, we also ran some different functions and changed the size of input and then filled the chart to get the graph of the growing of each function. Next compared them to get the result in order to observe the change of the runtimes.
Sorting and Efficiency are really important in computer science. Not only because they can help us to solve problems easily, but also because they can help us to improve the efficiency of our program and function.
These are my understanding of Sorting and Efficiency. Hope I can learn more about it and have better understanding of it compare to now I have.
No comments:
Post a Comment