Introduction to Computer Science Searching & Sorting PDF

Introduction to Computer Science Searching & Sorting Dr. Christian Krätzer 1 🚀 by Decker Sorting algorithms - Divide and Conquer 2  Overview Search Sorting Prelim...

Introduction to Computer Science Searching & Sorting Dr. Christian Krätzer 1 🚀 by Decker Sorting algorithms - Divide and Conquer 2  Overview Search Sorting Preliminary considerations Selection Sort, Insertion Sort, Bubblesort Quicksort Mergesort Remarks Divide and conquer approaches 3  Mergesort: Sorting by “shuffling” Applying the divide and conquer principle 1. Divide sequence into two equal parts 2. Sort both parts independently of each other 3. Merge the sorted subsequences Sorting is done recursively based on the same rule Merge (mix): Compare the two smallest entries ‘Set’ the smaller one first (i.e. as the smallest one of the new sequence) Consequence: Requires intermediate memory (out-of-place) 4  Observations on Mergesort If several people want to sort something together, they probably intuitively use Mergesort – but without recursion In contrast to quicksort always best possible division Entries in subsequences are processed sequentially, i.e. always one ( ) after the next ( ). 5  Merging Merging two sorted sequences and merge() returns sorted sequence from all entries of static void merge(int[] a, int[] b, int[] c) { assert (c.length >= a.length + b.length); int i = 0, j = 0; for (int k=0; k < a.length + b.length; ++k) { if (i >= a.length) c[k] = b[j++]; else if (j >= b.length) c[k] = a[i++]; else if (a[i] 1) mergesort(a); // recursive... if (b.length > 1) mergesort(b); //... sort merge(a, b, c); // merge } 7  Recursion in Mergesort: split 1. Step: Split In this implementation, each field shown here is created (as a copy) 8  Merge the recursively sorted parts 2. Step: Merge In this implementation, each field shown here is generated by merge() 9 Disadvantages of implementation attempt 1 The algorithm is simple, but… is split in every recursion step Memory for and is requested again each time This is too much and unnecessary! Assumption: We sort a sequence of length Then one field of length is sufficient as a buffer! For all recursion steps Delimitation left/right with indices as with Quicksort 10 Approach for the 2nd implementation attempt We copy the input into the additional field We need auxiliary functions that process parts/areas Split works recursively and ‘only’ calculates indices that delimit areas Merge writes entries from two areas in one field into an area of the other public static void mergesort(int[] a) { n = a.length; int[] b = new int[n]; // copy a into b for (int i=0; i < n; ++i) b[i] = a[i]; mergesort(a, 0, n, b); // sort b into a } 11  2nd attempt: split // Sort source b[left...right-1] into destination a[left...right-1]. // Note that right bound is _excluded_! static void mergesort(int[] a, int left, int right, int[] b) { if (right - left = mid) a[k] = b[j++]; else if (j >= right) a[k] = b[i++]; else if (b[i]