DOC PREVIEW
SJSU CS 146 - Sorting

This preview shows page 1-2-3-25-26-27-28-50-51-52 out of 52 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 52 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

SortingRefresher on Big-OGeneric running timesO(N log N) vs. O(N^2)Two Common CategoriesFor small values of NO(N^2) SortsBubble SortPowerPoint PresentationSlide 10Slide 11Slide 12Selection SortSlide 14Slide 15Insertion SortSlide 17Slide 18O(N log N) SortsHeap SortSlide 21Forming the heap from an unsorted arraySlide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Merge SortSlide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Quick SortSlide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46What’s the pointBinary SearchingBinary SearchingSlide 50Slide 51Conclusion…SortingAlgorithms and AnalysisRobert DuncanRefresher on Big-ORefresher on Big-OO(2^N) ExponentialO(N^2) QuadraticO(N log N) Linear/LogO(N) LinearO(log N) LogO(1) ConstantHierarchy of Big-O functions from slowest to fastestGeneric running times Generic running times N O(log N) O(N) O(N log N) O(N^2) O(2^N)1 0 1 0 1 28 3 8 24 64 256128 7 128 896 163843.4x10^381024 10 1024 10240 10485761.8x10^308O(N log N) vs. O(N^2)O(N log N) vs. O(N^2)050001000015000200000 1000O(N log N) O(N^2)Two Common CategoriesTwo Common CategoriesSorting Algorithms of O(N^2)Bubble SortSelection SortInsertion SortSorting Algorithms of O(N log N)Heap SortMerge SortQuick SortFor small values of NFor small values of NIt is important to note that all algorithms appear to run equally as fast for small values of N. For values of N from the thousands to the millions, The differences between O(N^2) and O(N log N) become dramatically apparentO(N^2) SortsO(N^2) SortsEasy to programSimple to understandVery slow, especially for large values of NAlmost never used in professional softwareBubble SortBubble SortThe most inefficient of the O(n^2) algorithmsSimplest sorting algorithm availableWorks by comparing sequential items, and swapping them if the first one is larger than the second. It makes as many passes through an array as are needed to complete the sortBubble Sort – Pass 1236415236415234615234165234156Bubble Sort – Pass 2234156234156231456231456231456Bubble Sort – Pass 3231456213456213456213456213456Bubble Sort – Pass 4123456123456123456123456123456Selection SortSelection SortMore efficient than Bubble Sort, but not as efficient as Insertion SortWorks by finding the largest element in the list and swapping it with the last element, effectively reducing the size of the list by 1.Selection Sort – Pass 1-36 8 10 2 46 8 4 2 106 2 4 8 10Selection Sort – Pass 4-54 2 6 8 102 4 6 8 102 4 6 8 10Insertion SortInsertion SortOne of the most efficient of the O(n^2) algorithmsRoughly twice as fast as bubble sortWorks by taking items from unsorted list and inserting them into the proper place.Insertion Sort2222 3522 35 48Insertion Sort13 22 35 488 13 22 35 488 13 22 27 35 48O(N log N) SortsO(N log N) SortsFastEfficientComplicated, not easy to understandMost make extensive use of recursion and complex data structuresHeap SortHeap SortSlowest O(N log N) algorithm.Although the slowest of the O(N log N) algorithms, it has less memory demands than Merge and Quick sort.Heap SortHeap SortWorks by transferring items to a heap, which is basically a binary tree in which all parent nodes have greater values than their child nodes. The root of the tree, which is the largest item, is transferred to a new array and then the heap is reformed. The process is repeated until the sort is complete.Forming the heap from an unsorted arrayForming the heap from an unsorted array11 26 14 2 19 32 7322147111926Populating the new arrayPopulating the new array322147111926Reforming the heapReforming the heap321927111426Reforming the heapReforming the heap322627111419Repeat the processRepeat the process32 2627111419Repeat the processRepeat the process32 2614711219Repeat the processRepeat the process32 2619711214Repeat the processRepeat the process32 26 19711214Merge SortMerge SortUses recursion. Slightly faster than heap, but uses twice as much memory from the 2nd array.Sometimes called “divide and conquer” sort.Works by recursively splitting an array into two equal halves, sorting the items, then re-merging them back into a new array.11 26 14 2 32 18 7 2132 18 7 2111 26 14 211 26 14 2 32 18 7 2111 26 2 14 18 32 7 2118 32 7 2111 26 2 1411 26 2 14 18 32 7 217 18 21 322 11 14 262 11 14 26 7 18 21 327 18 21 322 11 14 262 11 14 26 7 18 21 322 7 11 14 18 21 26 32Quick SortQuick SortThe most efficient O(N log N) algorithm availableWorks by first randomly choosing a pivot point which is hopefully a median element in the array. All elements less than the pivot are transferred to a new array, and all elements greater are transferred to a second array.Quick SortQuick SortThese new arrays are recursively quick sorted until they have been split down to a single element. The sorted elements smaller than the pivot are placed in a new array, then the pivot is placed after, and finally the elements greater than the pivot. These elements are now sorted.Quick SortQuick SortNote: Although it is the quickest sorting algorithm, a badly chosen pivot may cause Quick Sort to run at O(N^2). Different versions of quick sort address this problem in different ways.For example, one way is to randomly choose 3 elements, then use the median element as the pivot.11 26 14 2 32 18 7 21 5Pivot11 26 14 2 32 18 7 21 511 2 7 5Pivot11 2 7 5Pivot11 26 14 2 32 18 7 21 511 26 14 2 32 18 7 21 511 2 7 52 5Pivot11 26 14 2 32 18 7 21 52 5 711 2 7 52 5 2 5Pivot11 26 14 2 32 18 7 21 52 5 7 1111 2 7 52 5 2 5What’s the pointWhat’s the pointBinary Searching Binary Searching Binary searches achieve O(log N) efficiency on sorted dataSimilar to High-Low gameEach execution eliminates half of the elements to search forAlthough hashing offers a quicker search of O(1), binary searches are simpler, and use much less memory.Binary SearchingBinary Searching2 7 11 14 16 23 26 29 32 37 4314?Binary SearchingBinary Searching2 7 11 14 16 23 26 29 32 37 4314?Binary SearchingBinary Searching2 7 11 14 16 23 26 29 32 37 4314Conclusion…Conclusion…O(N^2) algorithms are almost never used in professional softwareQuick sort is generally considered to be the best overall sorting algorithm currently


View Full Document

SJSU CS 146 - Sorting

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?