1
$\begingroup$

Can you help me with sorting algorithm implementation for objects of Student type by rating field. This field (rating) value can be any number from 0 to 100. Can I do the sort in-place?

$\endgroup$
  • $\begingroup$ Questions specific to C++ are off-topic here. Can you rephrase your question so that it is not specific to C++? $\endgroup$ – Yuval Filmus Nov 23 '20 at 10:13
  • 1
    $\begingroup$ A possible strategy: scan the input array once to count how many elements have key $k$ (for each $k = 0, \dots, 100$). Then, scan it a second time and place each element in the correct position (by swapping with the element already there). This works in $O(n)$ time with a small hidden constant (where $n$ is the number of elements to sort) and only requires $O(1)$ additional memory. $\endgroup$ – Steven Nov 23 '20 at 10:18
  • $\begingroup$ @YuvalFilmus I have edited my question. $\endgroup$ – Igor B Nov 23 '20 at 10:26
  • $\begingroup$ @Steven, want to write that as an answer so we can vote on it? $\endgroup$ – D.W. Nov 23 '20 at 10:28
2
$\begingroup$

Let $A[0 \dots, n-1]$ be the elements to be sorted. A possible strategy that requires $O(n)$ time and $O(1)$ additional memory is:

  • count, for each possible key $k$, the number of elements in $A$ with key $k$, in $O(n)$ time;
  • for each $k$ compute the intervals of indices of $A$ in which elements with key $k$ must lie (in $O(1)$ time);
  • Scan the input array a place each element in the correct interval. This can be done by swapping the considered element with any element that was already in that interval, taking care to not swap that element back.

A possible implementation is the following:

  • Initialize an array $C[0, \dots, 100]$. Initially all entries of $C$ are $0$.
  • For each $i=0, \dots, n-1$: increment $C[k]$ where $k$ is the key of $A[i]$.
  • For $k=0, \dots, 101$, let $P[k]=\sum_{j=0}^{k-1} C[j]$; At this point we know that an element with key $k$ needs to end up in some $A[i]$ with $P[k] \le i < P[k+1]$. Notice that, for $k>0$, $P[k] = P[k-1] + C[k-1]$.
  • Let $i=0$.
  • While $i<n$:
    • Let $k$ be the key of $A[i]$.
    • If $i \not\in [P[k], P[k+1])$
      • Decrement $C[k]$
      • Swap $A[i]$ with $A[P[k]+C[k]]$
    • Else
      • Increment $i$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.