• API
• FAQ
• Tools
• Archive
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.
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;
30.       while (iterator < aLength) {
31.         val value = valueArray(iterator);
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.
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.

Top