Codility - Lesson 6 Sorting

Source Link:
https://codility.com/programmers/lessons/6-sorting/

Some Notes:

Sorting is the process of arranging data in a certain order.

There are many sorting algorithms, and they differ considerably in terms of their time complexity and use of memory.

6.1. Selection sort

The idea: Find the minimal element and swap it with the first element of an array. Next,
just sort the rest of the array, without the first element, in the same way.

6.1: Selection sort — O(n2).
1 def selectionSort(A):
2 n = len(A)
3 for k in xrange(n):
4 minimal = k
5 for j in xrange(k + 1, n):
6 if A[j] < A[minimal]:
7 minimal = j
8 A[k], A[minimal] = A[minimal], A[k] # swap A[k] and A[minimal]
9 return A

6.2. Counting sort

The idea: First, count the elements in the array of counters (see chapter 2). Next, just iterate
through the array of counters in increasing order.

6.2: Counting sort — O(n + k)
1 def countingSort(A, k):
2 n = len(A)
3 count = [0] * (k + 1)
4 for i in xrange(n):
5 count[A[i]] += 1
6 p = 0
7 for i in xrange(k + 1):
8 for j in xrange(count[i]):
9 A[p] = i
10 p += 1
11 return A

6.3. Merge sort

The idea: Divide the unsorted array into two halves, sort each half separately and then just
merge them. After the split, each part is halved again.

(read more at http://en.wikipedia.org/wiki/Merge_sort)

6.4. Sorting functions

If the range of sorted values is unknown then there are algorithms which sort all the values in O(n log n) time. A big advantage of many programming languages are their built-in sorting functions. 

6.5. Exercise

Problem: You are given a zero-indexed array A consisting of n > 0 integers; you must return
the number of unique values in array A.

Solution O(n log n): First, sort array A; similar values will then be next to each other.
Finally, just count the number of distinct pairs in adjacent cells.

6.4: The number of distinct values — O(n log n).
1 def distinct(A):
2 n = len(A)
3 A.sort()
4 result = 1
5 for k in xrange(1, n):
6 if A[k] != A[k - 1]:
7 result += 1
8 return result