Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 28th, 2020 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Task 1: figuring out the complexity
  2. -----------------------------------
  3.  
  4. Insertion.java on:
  5.   random inputs: n²
  6.   reversed inputs: n²
  7.   95% sorted inputs: n²
  8.   sorted inputs: n 
  9.  
  10. Quick.java on:
  11.   random inputs: n log n
  12.   reversed inputs: n²
  13.   95% sorted inputs: n log n
  14.   sorted inputs: n²       
  15.  
  16. Merge.java on:
  17.   random inputs: n log n
  18.   reversed inputs: n log n
  19.   95% sorted inputs: n log n
  20.   sorted inputs: n         
  21.  
  22. Arrays.sort on:
  23.   random inputs: n log n
  24.   reversed inputs: n           
  25.   95% sorted inputs: n log n
  26.   sorted inputs: n             
  27.  
  28. Task 2: improving quicksort
  29. ---------------------------
  30.  
  31. Do the following changes affect the complexity of quicksort on any kind of
  32. input data? If so, what is it that changes?
  33.  
  34.   Shuffling the array first: [no] [yes+reason] 
  35.  
  36.  Yes, Reversed and Sorted performance is greatly improved. When pivot-element is the    first or last element (as it is for Sorted and reversed) the operation of quick sorting in regards to pivot element is increased. LOOK IT UP. Change time complexity to n log n on reversed and sorted arrays. Otherwise n² on sorted or reversed (double check)
  37.  
  38.   Median-of-three pivot selection: [no] [yes+reason]
  39.  
  40. Median performs very well on sorted arrays, pivot element is middle value of array and avoids worst case scenario where pivot element is smallest or largest. With median as pivot -> Complexity n lg n, if not worst case n² (n² / 2 ?)
  41.  
  42.   Insertion sort for small arrays: [no] [yes+reason]
  43.  
  44. No. Insertion made no significant difference in the tests. I tried insertion at n < 100. It does not change time complexity
  45.  
  46.  
  47.  
  48. Which combination of improvements gives the best result?
  49. If you use insertion sort for small arrays, say what cutoff you used.
  50.  
  51. [...answer here...]
  52.  
  53. Insertion didn't work for us. Median worked well with sorted arrays but when combined with shuffle it was useless. So in the end just the shuffle performed best which gives n log n complexity I think.
  54.  
  55.  
  56. -----
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