SHARE
TWEET

Untitled

a guest Sep 21st, 2019 127 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Author: Tommi Junttila, Aalto University.
  2.  * Only for the use on the Aalto course CS-A1140.
  3.  * Redistribution not allowed.
  4.  */
  5.  
  6. package object radixSort {
  7.   /**
  8.    * Least-significant-digit-first radix sort for integer arrays.
  9.    * Sorts the argument array in ascending order.
  10.    * Assumes that all the integers are non-negative.
  11.    * Interpret 'digit' as 'byte' (8 bits) here and use bit-level operations
  12.    *  such as shifting (>> and <<) and masking (&) to extract 'digits'.
  13.    */
  14.   def lsdRadixSort(a: Array[Int]): Unit = {
  15.     val aLength = a.length
  16.     var valueArray = a;
  17.  
  18.     val M1 = 255;
  19.     val M2 = 65280;
  20.     val M3 = 16711680;
  21.     val M4 = -16777216;
  22.  
  23.     val masks = Array(M1, M2, M3, M4);
  24.     var rounds = 0;
  25.     while (rounds < 4) {
  26.       val countArray = Array.fill(256) {0}
  27.  
  28.       var iterator = 0;
  29.       val mask = masks(rounds);
  30.       while (iterator < aLength) {
  31.         val value = valueArray(iterator);
  32.         val maskedValue = value & mask;
  33.         val index = maskedValue >> (rounds * 8);
  34.         countArray(index) += 1
  35.         iterator += 1
  36.       }
  37.  
  38.       val locationTable = new Array[Int](256)
  39.       locationTable(0) = 0
  40.       var z = 1
  41.       while (z < 256) {
  42.         locationTable(z) = locationTable(z-1) + countArray(z -1);
  43.         z += 1
  44.       }
  45.  
  46.       val temporaryArray = new Array[Int](aLength)
  47.       var reverse = 0;
  48.       while (reverse <= aLength - 1)
  49.       {
  50.         val value = valueArray(reverse);
  51.  
  52.         val maskedValue = value & mask;
  53.         val index = maskedValue >> (rounds * 8);
  54.  
  55.         val offsetted = locationTable(index)
  56.         locationTable(index) += 1
  57.  
  58.         temporaryArray(offsetted) = value;
  59.         reverse += 1;
  60.       }
  61.       valueArray = temporaryArray;
  62.       rounds += 1;
  63.     }
  64.     for (i <- a.indices) a(i) = valueArray(i)
  65.   }
  66. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top