清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter8 Sorting

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

22)49O的8 162因25(9@9 16 25)25(49 i=5 08(四21(252549
i = 4 i = 5 21 25 25* 49 16 08 16 16 21 25 25* 49 08 16 21 25 25* 49 08 08 16 21 25 25* 49 08

Direct Insertion Sort Algorithm void Insertion Sort( ElementType A[], int N) ElementType Tmp; for(P=1;P≤N;P++){ Tmp=A[P]: the next coming card*/ for(j=P; j>0&&A[j-1]> Tmp; j-) A[j]=A[j-1]; shift sorted cards to provide a position for the new coming card"/ A[j]= Tmp;/ place the new card at the proper position*/ 3 /end for-P-loop * The worst case: Input al is in reverse order. T(N)=O(N2) The best case: Input al is in sorted order. T(N)=O(N)
Direct Insertion Sort Algorithm void InsertionSort ( ElementType A[ ], int N ) { int j, P; ElementType Tmp; for ( P = 1; P 0 && A[ j - 1 ] > Tmp; j-- ) A[ j ] = A[ j - 1 ]; /* shift sorted cards to provide a position for the new coming card */ A[ j ] = Tmp; /* place the new card at the proper position */ } /* end for-P-loop */ } The worst case: Input A[ ] is in reverse order. T( N ) = O( N2 ) The best case: Input A[ ] is in sorted order. T( N ) = O( N )

)Binary Insertion sort Basic idea: there are number of n sequential objects vIOL vIIL,.,VIn-l in the seqlist, Insertion sort makes use of the fact that elements in position 0 through i-I are already in sorted order. use binary search to find the inserting position of vi when insert element vi Algorithm of binary insertion sort
➢Binary Insertion sort Basic idea: there are number of n sequential objects V[0], V[1], …, V[n-1] in the SeqList,Insertion sort makes use of the fact that elements in position 0 through i-1 are already in sorted order. use binary search to find the inserting position of V[i] when insert element v[i]. Algorithm of binary insertion sort

typedef int SortData; void BinInssort( SortData VI, int n)i SortData temp; int Left, Right; for(int i=l; i= Left; k--)VIk+1=VIk 记录后移 VLLeft=temp;插入
typedef int SortData; void BinInsSort ( SortData V[ ], int n ) { SortData temp; int Left, Right; for ( int i = 1; i = Left; k-- ) V[k+1] = V[k];// 记录后移 V[Left] = temp; //插入 } }

Binary insertion sort 234 5 temp 2(5 5 0 2 4 5 temp i=22( 3 i=4(34⑤2(8(8 i=5(3((8②0的 ③3④46(8662
Binary insertion sort 0 1 2 3 4 5 temp i = 1 i = 2 0 1 2 3 4 5 temp 5 21 3 3 i = 3 5 5 3 5 21 21 4 4 i = 4 3 5 21 8 8 i = 5 3 5 8 21 16 16 4 4 3 4 5 8 16 21
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter7 Search.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter6 Graph Algorithms.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter5 trees.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter4 Stacks Queues.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter3 Lists.ppt
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 2 ALGORITHM ANALYSIS.ppt
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 8 THE DISJOINT SET ADT.ppt
- 华中师范大学计算机科学系:《数据结构》第6章 二叉树和树.ppt
- 华中师范大学计算机科学系:《数据结构》第2章 线性表.ppt
- 华中师范大学计算机科学系:《数据结构》第8章 查找表.ppt
- 华中师范大学计算机科学系:《数据结构》第7章 图和广义表.ppt
- 华中师范大学计算机科学系:《数据结构》第5章 串和数组.ppt
- 华中师范大学计算机科学系:《数据结构》第4章 栈与队列.ppt
- 华中师范大学计算机科学系:《数据结构》第3章 排序.ppt
- 华中师范大学计算机科学系:《数据结构》第1章 绪论(王敬华).ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)实验一.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第四章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第六章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第二章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter9 String.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验二.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)二叉树试验三.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验一.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验四.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验模板.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验五.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)复习2007级.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)2004级计算机B卷.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第九章 排序.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第1章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第2章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第3章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第4章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组和广义表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第6章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第七章 图.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)动态查找结构.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第9章 查找(静态查找表 二叉排序树 平衡二叉树(AVL树)).ppt