Skip to content

Instantly share code, notes, and snippets.

@AlexMost
Last active December 17, 2015 02:49
Show Gist options
  • Save AlexMost/5539182 to your computer and use it in GitHub Desktop.
Save AlexMost/5539182 to your computer and use it in GitHub Desktop.
qsort = ([f, o...]) ->
return [] unless f
less = o.filter (i) -> i < f
more = o.filter (i) -> i >= f
qsort(less).concat([f]).concat(qsort more)
template <typename T>
void qsort (T *result, T *list, int n)
{
if (n == 0) return;
T *smallerList, *largerList;
smallerList = new T[n];
largerList = new T[n];
T pivot = list[0];
int numSmaller=0, numLarger=0;
for (int i = 1; i < n; i++)
if (list[i] < pivot)
smallerList[numSmaller++] = list[i];
else
largerList[numLarger++] = list[i];
qsort(smallerList,smallerList,numSmaller);
qsort(largerList,largerList,numLarger);
int pos = 0;
for ( int i = 0; i < numSmaller; i++)
result[pos++] = smallerList[i];
result[pos++] = pivot;
for ( int i = 0; i < numLarger; i++)
result[pos++] = largerList[i];
delete [] smallerList;
delete [] largerList;
};
qsort [] = []
qsort (x:xs) = qsort less ++ [x] ++ qsort more
where less = filter (<x) xs
more = filter (>=x) xs
@pavlo-v-chernykh
Copy link

qsort.clj

(defn qsort [[x & xs]]
  (when x
    (let [less (filter #(< % x) xs)
          more (filter #(> % x) xs)]
      (lazy-cat (qsort less) [x] (qsort more)))))

Clojure solution is similar to Haskell one.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment