Unformatted text preview:

?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

ROCHESTER CSC 172 - Sorting

Documents in this Course
Load more
Download Sorting
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Sorting and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Sorting 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?