/* Created to demonstrate multiple sort methods: merge, insertion, bubble, quick, heap, and counting. */ import java.util.Random //=================================================== // Demonstrate the merge sort based on the algorithm // documented on the following site: // https://en.m.wikipedia.org/wiki/Merge_sort fun mergeSort() { // Merge the source array in left and right // halves into the destination. The left source // half is [begin:middle-1]. The right source // half is [middle:end-1]. The destination // result is [begin:end-1]. fun topDownMerge(source: Array, begin: Int, middle: Int, end: Int, destination: Array) { // Display debugging information and setup the // indexes to the current element in both halves. println("TopDownMerge: processing $begin to "+ "${end-1}") var left = begin var right = middle // While there are elements in the left or right // half, figure out which one is next. for (index in begin until end) { // If left half head exists and is less than // or equal to the existing right half head, // it's next so display the move we are making // and move it. if (left < middle && (right >= end || source[left] <= source[right])) { println(" moving ${source[left]} from "+ "$left into $index") destination[index] = source[left++] // Otherwise, the right half head is next so // display and move it. } else { println(" moving ${source[right]} from "+ "$right into $index") destination[index] = source[right++] } // if } // for // Output the existing state of the array marking // the elements we merged. print("Current array: ") for (index in 0 until destination.size) { if (index == begin) print("<") if (index == end-1) print("${destination[index]}> ") else print("${destination[index]} ") } // for println() } // topDownMerge // If the range is 1 element, it is sorted. // Otherwise, split it in half and recurse // on each half. Once the halves are sorted, // merge them together. fun topDownSplitMerge(source: Array, begin: Int, end: Int, destination: Array) { // If there is only one element, this range is // sorted so return. if (end-begin < 2) return // Find the middle point of the range and // display what we got. val middle = (end+begin)/2 println("topDownSplitMerge: left $begin to "+ "${middle-1}; right $middle to ${end-1}") // Recursively sort both halves from array A // into B. topDownSplitMerge(destination, begin, middle, source) topDownSplitMerge(destination, middle, end, source) // Merge the halves from array B into A. topDownMerge(source, begin, middle, end, destination) } // topDownSplitMerge // Make a copy of the source array into the work // array and start the sort. Source has the // items to sort and destination is a working // array. Both arrays end up sorted. fun topDownMergeSort(source: Array) { val destination = Array(source.size) { source[it] } topDownSplitMerge(destination, 0, source.size, source) } // topDownMergeSort // Allocate the source array and output it. val array = arrayOf(9, 5, 0, 2, 8, 1, 7, 3, 4, 6) print("\nMerge Sort initial array: ") for (value in array) print("$value ") println() // Perform the sort and output the resulting array. topDownMergeSort(array) print("Merge Sort ending array: ") for (value in array) print("$value ") println() } // mergeSort //=================================================== // Demonstrate the insertion sort based on the // algorithm documented on the following site: // https://en.wikipedia.org/wiki/Insertion_sort fun insertionSort() { // Perform a recursive sort. fun sort(array: Array, position: Int) { // If there are two or more elements to sort, // do so. if (position > 0) { // Save the data the needs to be moved and // decrement the position we are playing // with as our top end index. Put these // first so the index can be passed into // our recursive call. Sort the bottom // elements of the array first. val data = array[position] var index = position-1 sort(array, index) // Given the bottom is now sorted, we move // elements up, until we find the spot our // data belongs. Once there, we insert our // value. while (index >= 0 && array[index] > data) { array[index+1] = array[index] index-- } // while array[index+1] = data // Print what we did. println("Shifting element ${index+1} up one"+ " spot for ${position-index-1} elements") print(" so $data can be inserted ") for (index in 0..position) print("${array[index]} ") println() } // if } // sort // Allocate the source array and output it. val array = arrayOf(9, 5, 0, 2, 8, 1, 7, 3, 4, 6) print("\nInsertion Sort initial: ") for (value in array) print("$value ") println() // Perform the sort and output the resulting array. sort(array, array.size-1) print("Insertion Sort ending: ") for (value in array) print("$value ") println() } // insertionSort //=================================================== // Demonstrate the bubble sort by sorting 3 arrays // showing it's optimizations in effect. Based on // the algorithm documented on the following site: // https://en.wikipedia.org/wiki/Bubble_sort fun bubbleSort() { // Print the pass number, last element to check, // and the array contents like: // 0:4->10,20,30,40,50 // p l e e e e e // a a l l l l l // s s m m m m m // s t 1 2 3 4 5 // This code is able to handle any size array, // but it should break up the output lines on // larger ones. fun print(pass: Int, array: Array, last: Int) { // Output the pass number, last element to check, // and for each element in the array display // either a comma or "->" (when first element // is being processed) plus the current element. // After the last element, output the end of line. print("$pass:$last") for (index in 0 until array.size) { if (index == 0) print("->") else print(",") print(array[index]) } // for println() } // print // Perform the bubble sort on the array. Note, // while the comments talk about a 5 element // array, the code can handle any number of // elements. // // Note: the 'pass' varable and debugging array // printing aren't required for this code to be // reused. If you use my code, please give me // credit in the comments. fun sort(array: Array) { var last = 0 // The last element swapped var num = // Number of elements to check array.size-1 var pass = 0 // Number of passes made // Output pass 0 (before any sorting is done), // last element to check, and the contents of // the array. print(pass, array, num) // For every possibly needed pass, perform a // swap as needed. If the data is completely // in reverse order, we need to process the // swap for 4 passes to handle our 5 element // array. If the data is already sorted, we // don't need to perform any passes. Of // course, any number of passes between 0 and // 4 could be required. We optimize this to // keep track of the last swap as everything // beyond that point is sorted. do { // Each pass moves the highest element // to the last position. Therefore, // we can avoid processing what we know // to be sorted. Also, as pointed out // in the pass loop comment, the data // may be sorted already. Therefore, // assume we are sorted by initializing // 'last' to zero and increment our pass // number. For every element that might // need a swap, check it. For our 5 // element array, this means 4 checks // on the first pass. After that, we // only check to where our last swap // was made. last = 0 pass++ for (index in 0 until num) { // If the current element is greater // than the next one, swap them and note // that we swapped this element. if (array[index] > array[index+1]) { array[index] = array[index+1].also { array[index+1] = array[index] } last = index } // if } // for // Output the current pass number, the // last element to check, and contents of // the array. Change the last element to // check for the next pass to be the last // one swapped and if we need to perform // another pass, loop. print(pass, array, last) num = last } while (num > 0) } // sort val array1 = // Array in reverse order arrayOf(90, 81, 67, 43, 12) val array2 = // Array in sorted order arrayOf(12, 43, 67, 81, 90) val array3 = // Partially sorted array arrayOf(12, 90, 67, 43, 81) // Process the array in reverse order. println("\nBubble Sort of reverse ordered data.") sort(array1) // Process the array in sorted order. println("\nBubble Sort of sorted ordered data.") sort(array2) // Process the array in reverse order. println("\nBubble Sort of partially sorted data.") sort(array3) } // bubbleSort //=================================================== // Demonstrate the quicksort based on the algorithm // documented on the following site: // https://en.wikipedia.org/wiki/Quicksort fun quickSort() { // Partition the array. Pick a value and move all // the lower values to the bottom leaving the // higher at the top. The selected value gets // placed into it's final position in between // them. Return the position it ended up in. // Display debugging for each swap and the // final state on exit. fun partition(array: Array, low: Int, high: Int): Int { val pivot = array[high] var bottom = low for (index in low until high) if (array[index] < pivot) { println("Swaping $bottom and $index") array[bottom] = array[index].also { array[index] = array[bottom] } bottom++ } // if array[bottom] = array[high].also { array[high] = array[bottom] } println("Swaping $bottom and $high") println("Pivot is $bottom in $low to $high") print("Updated array: ") for (index in 0 until array.size) { if (index == low) print("[") if (index == bottom) if (index == high) print("<${array[index]}>] ") else print("<${array[index]}> ") else if (index == high) print("${array[index]}] ") else print("${array[index]} ") } // for println() return bottom } // partition // Recursive function to perform the sort. If we // have elements, find the pivot point moving // the lower numbers below it and the higher // above it. It is left in it's final position. // Follow up by performing the sort on both // sets of elements. fun sort(array: Array, low: Int, high: Int) { if (low < high) { val pivot = partition(array, low, high) sort(array, low, pivot-1) sort(array, pivot+1, high) } // if } // sort // Allocate the source array and output it. val array = arrayOf(9, 5, 0, 2, 8, 1, 7, 3, 4, 6) print("\nQuicksort initial: ") for (value in array) print("$value ") println() // Perform the sort and output the resulting array. sort(array, 0, array.size-1) print("Quicksort ending: ") for (value in array) print("$value ") println() } // quickSort //=================================================== // Demonstrate the heapsort algorithm based on: // https://en.wikipedia.org/wiki/Heapsort fun heapSort() { // This code emulates a binary tree in the array. // Element 0 is the tree root. It's left child // is element 1 and right child is element 2. // The following functions return the parent and // left child index in the array for any node. // The right child is leftChild(node)+1, but we // never use it in our sort so it isn't coded. fun parent(index: Int) = (index-1)/2 fun leftChild(index: Int) = 2*index+1 // Repair the heap whose root element is at // start. We are assuming the heaps rooted at // its children are valid. The root of the // heap becomes it's largest value. fun siftDown(array: Array, start: Int, end: Int) { // While the root has at least one child, // decide if any swapping is necessary. var root = start while (leftChild(root) <= end) { val child = leftChild(root) var swap = root // If the left child is greater than our // root, it might be the one to swap. if (array[swap] < array[child]) swap = child // If there is a right child and that child // is greater than our current pick to // swap, it becomes our choice. if (child+1 <= end && array[swap] < array[child+1]) swap = child+1 // If nothing to swap, we are done. if (swap == root) return // Otherwise, swap them, display what we did, // and move our root. else { print("Swapping $root with $swap") println(" (exchanging ${array[root]} and "+ "${array[swap]})") array[root] = array[swap].also { array[swap] = array[root] } root = swap } // if } // while } // siftDown fun sort(array: Array, count: Int) { // Find the parent of the last element. While // there are more elements to process, sift // them generating our heap. var start = parent(count-1) while (start >= 0) siftDown(array, start--, count-1) // Starting at the end move the heap's root // (highest value) to the last unsorted spot, // display what we did, sift the remaining // heap elements as needed, and repeat for // the smaller heap. var end = count-1 while (end > 0) { array[end] = array[0].also { array[0] = array[end] } print("Placing root value at $end via swap") println(" (exchanging ${array[0]} and "+ "${array[end]})") print("Updated array: ") for (value in array) print("$value ") println() siftDown(array, 0, --end) } // while } // sort // Allocate the source array and output it. val array = arrayOf(9, 5, 0, 2, 8, 1, 7, 3, 4, 6) print("\nHeapsort initial: ") for (value in array) print("$value ") println() // Perform the sort and output the resulting array. sort(array, array.size) print("Heapsort ending: ") for (value in array) print("$value ") println() } // heapSort //=================================================== // Counting sort demonstration based on this // algorithm: // https://en.wikipedia.org/wiki/Counting_sort fun countingSort() { // Just using half it's value as it's key. This // shows the handling of duplicate key values. // The pairs of even/odd numbers are maintained // in their original order. fun key(value: Int) = value/2 // Perform the actual sorting. This sort doesn't // sort in place. It returns a new array with // the values sorted. fun sort(input: Array, keyMax: Int): Array { // Count the values of each possible key. val count = Array(keyMax) {0} for (value in input) count[key(value)] += 1 // Assign the starting index for values with // the various keys. Display what we do. var total = 0 for (index in 0 until keyMax) { val oldCount = count[index] count[index] = total total += oldCount println("Key of $index has a count of "+ "$oldCount values will be stored at "+ "${count[index]}") } // for // Create the output array, display where the // value is going, and put it there. val output = Array(total) {0} for (value in input) { println( "Storing $value at ${count[key(value)]}") output[count[key(value)]++] = value } return output } // sort // Allocate the source array and output it. Making // use of the fact that this sort supports // duplicate keys with different values. Ordered // the key pairs so the even is first. var array = arrayOf(18, 4, 0, 2, 19, 1, 17, 3, 5, 6) print("\nCounting Sort initial: ") for (value in array) print("$value ") println() // Perform the sort and output the resulting array. // Note: second argument must be maximum key plus // one and we are using the element value as the // key. array = sort(array, 10) print("Counting Sort ending: ") for (value in array) print("$value ") println() } // countingSort //=================================================== // Run 3 of the sorting algorithms together based on // a random number, since timelimit error is reached // during the fourth. fun main(args: Array) { if (Random().nextInt(2) == 0) { println("First half of algorithms...") mergeSort() insertionSort() bubbleSort() } else { println("Second half of algorithms...") quickSort() heapSort() countingSort() } // if } // main

sort mn sr