@@ -52,9 +52,6 @@ class Solution {
5252
5353/*
5454* Quick sort
55- * This will fail testcase 17/19 (used to pass earlier, before adding new testcases), I still added it here for interest.
56- * It fails on test case where we have an array with many elements of which all are 2's. This will have quicksort to run as
57- * its worst case, which is O(n^2). But on average this will run O(nlogn)
5855*/
5956class Solution {
6057fun sortArray (nums : IntArray ):IntArray {
@@ -72,10 +69,12 @@ class Solution {
7269 }
7370
7471private fun partition (nums : IntArray ,low : Int ,high : Int ):Int {
72+ val r= (low.. high).random()
73+ nums.swap(r, high)
7574val pivot= nums[high]
7675var i= low
7776
78- for (jin low until high) {
77+ for in low until high) {
7978if (nums[j]<= pivot) {
8079 nums.swap(i, j)
8180 i++
@@ -87,7 +86,7 @@ class Solution {
8786 }
8887
8988fun IntArray.swap (i : Int ,j : Int ) {
90- this [i]= this [j].also {this [j]= this [i] }
89+ this [i]= this [j].also this [j]= this [i] }
9190 }
9291}
9392