?CSC 172 Data Structures and AlgorithmsEustrat ZhupaMarch 19, 2019?SortingThe ProblemIInput: A sequence of n numbers ha0, a1, . . . , an−1i.IOutput: A permutation (reordering) ha00, a01, . . . , a0n−1i of theinput s.t. a00≤ a01≤ . . . ≤ a0n−1.The input sequence is usually an n-element array.In 7 3 2 6 3Out 2 3 3 6 7?Sorting PropertiesStable SortingA sorting algorithm is said to be stable if it does not change therelative ordering of elements with identical key values.Input 7 3(1)2 6 3(2)Output 2 3(1)3(2)6 7In Place SortingA sorting algorithm sorts in place if only a constant number ofelements of the input array are ever stored outside the array.?SortingInsertion SortDescription: Iterate one input element per repetition. Move it tothe right position in the sorted subarray. (wiki)?Insertion Sort1 v o i d S ort (E [ ] A) {2 f o r ( i n t i =1; i <A . l e n g t h ; i ++) // I n s e r t i ’ th r e c o r d3 f o r ( i n t j=i ; ( j >0) && (A [ j ] . compareTo (A [ j −1]) < 0); j −−)4 D S u t i l . swap (A, j , j −1);5 }How many swaps? What ab out comparisons?Is it ’stable’?Is it ’in place’??Bubble SortBubble SortBubble Sort repeatedly steps through the list to be sorted,compares each pair of adjacent items and swaps them if they are inthe wrong order. (wiki)?Bubble Sort1 v o i d S o r t (E [ ] A) {2 f o r ( i n t i =0; i <A . l e n g t h −1; i++)3 f o r ( i n t j=A . l e n g t h −1; j > i ; j −−)4 i f ( ( A [ j ] . compareTo (A [ j −1]) < 0 ) )5 D S u t i l . swap (A, j , j −1);6 }How many swaps? What about comparisons?Is it ’stable’?Is it ’in place’??Selection SortSelection SortThe i-th pass of Selection Sort selects the i-th smallest key in thearray, placing that record into position i .?Selection Sort (Code)1 v o i d S o r t (E [ ] A) {2 f o r ( i n t i =0; i <A . l e n g t h −1; i++) { // S e l e c t i ’ th r e c o r d3 i n t l o w i n d e x = i ; // Remember i t s i n d e x4 f o r ( i n t j=A . l e n g t h −1; j > i ; j −−) // Fin d t he l e a s t v a l u e5 i f (A [ j ] . compareTo (A [ lo w i n d e x ] ) < 0)6 l o w i n d e x = j ; // Put i t i n p l a c e7 DS u t i l . swap (A, i , l o w i n d e x ) ;8 }9 }How many swaps? What about comparisons?Is it ’stable’?Is it ’in
View Full Document