CHAPTER 6 SORTING s 1 Preliminaries Sorting: There is a series of data in random order, we sort them depending a certain key word Datalist: an finity set of data waiting to be sorted Key: data object has many attribute areas, namely there are many data element, one of all these elements can be used to distinguish object, we use it as sorting key. we also call it sorting code
◼ Sorting: There is a series of data in random order, we sort them depending a certain key word. ◼ Datalist: an finity set of data waiting to be sorted. ◼ Key: data object has many attribute areas, namely there are many data element, one of all these elements can be used to distinguish object, we use it as sorting key. we also call it sorting code. CHAPTER 6 SORTING §1 Preliminaries
The stability of sorting method: if there are two objects r and rlil in the object series, and their sorting codes are k==klil,And before sorting, object rli is in front of object r[ji. If after the sorting, objectrlil is still in front of object rIil, then we call this sorting method stable, otherwise we call this sorting method unstable. Inner sort and outer sort: inner sort means in the sorting period, all the data objects are in the memory. Outer sort means in the sorting period, since the number of object is too large, and they cannot be put in the memory at the same time. We must move the sorting between inner and outer memory according to the demand
◼ The stability of sorting method: if there are two objects r[i] and r[j] in the object series, and their sorting codes are k[i] == k[j],And before sorting, object r[i] is in front of object r[j] .If after the sorting, object r[i] is still in front of object r[j] , then we call this sorting method stable, otherwise we call this sorting method unstable. ◼ Inner sort and outer sort: inner sort means in the sorting period, all the data objects are in the memory. Outer sort means in the sorting period, since the number of object is too large, and they cannot be put in the memory at the same time. We must move the sorting between inner and outer memory according to the demand
Time spending of sort: time spending of sort is an important standard to measure whether a method is good or not. Time spending of sort can be measured using data compare times and data moving times
◼ Time spending of sort: time spending of sort is an important standard to measure whether a method is good or not. Time spending of sort can be measured using data compare times and data moving times
TThe kinds of inner sort according to different principle insertion sort、 exchange sort、 selection sort、 merge sort.、 counting sort according to workload simple sort---time complexity o(n2) advanced sort--- time complexity o(n logn) base sort-- time complexity o(d n)
The kinds of inner sort • according to different principle insertion sort、exchange sort、selection sort、merge sort、counting sort. • according to workload simple sort---time complexity o(n2) advanced sort--- time complexity o(n logn) base sort--- time complexity o(d.n)
82 Insertion Sort )Direct Insertion sort 5 temp 21)(25)(49 35 6)(08 i=1 234 5 temp 21 21)(25)(49 5 08 i=2②5(@ 22(96 3②2②59 0 229 08
➢Direct Insertion sort i = 1 0 1 2 3 4 5 temp i = 2 0 1 2 3 4 5 temp 21 25 49 25* 16 08 21 25 49 25* 16 08 25 21 25 49 25* 16 08 21 25 49 25* 16 08 49 21 25 49 25* 16 08 i = 3 21 25 49 25* 16 08 25* 21 25 25* 49 16 08 §2 Insertion Sort