Sort

Algorithms
array
Catalogue
  1. 1. Selection Sort
  2. 2. Bubble Sort
  3. 3. Insertion Sort
  4. 4. Merge sort
    1. 4.1. 88. Merge Sorted Array
    2. 4.2. Merge k sorted array
    3. 4.3. Counting Inversions
  5. 5. Quick Sort
    1. 5.1. 215. Kth Largest Element in an Array
    2. 5.2. LintCode 80. Median
    3. 5.3. 283. Move Zeroes
      1. 5.3.1. Follow up : order can be changed
  6. 6. Rainbow Sort
    1. 6.1. 75. Sort Colors
      1. 6.1.1. Sol1. Counting Sort
      2. 6.1.2. Sol2. Dutch Partitioning Problem
  7. 7. Wiggle Sort
    1. 7.1. 280. Wiggle Sort
      1. 7.1.1. Solution1. Sort
      2. 7.1.2. Solution2. One Pass
    2. 7.2. 324. Wiggle Sort II
  8. 8. Big data
    1. 8.1. Sort with small memory

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning.

  • Time : O(n^2), as there are two nested loops
  • Space : O(1) (In-place)
1
2
3
4
5
6
7
8
def selectionSort(nums):
    n = len(nums)
    for i in xrange(n):
        minIndex = i
        for j in xrange(i, n):
            if nums[j] < nums[minIndex]:
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

  • Time : O(n^2), Best Case : O(n)
  • Space : O(1)
    1
    2
    3
    4
    5
    6
    def bubbleSort(nums):
        for i in xrange(len(nums)):
            for j in xrange(len(nums)-i-1):
                if nums[j] > nums[j+1]:
                    nums[j+1], nums[j] = nums[j], nums[j+1]
        return nums

Insertion Sort

  • Time : O(n^2), Best Case : O(n) when the elements are already sorted!
  • Space : O(1)
1
2
3
4
5
6
7
8
def insertionSort(nums):
    for i, num in enumerate(nums):
        j = i
        while j > 0 and nums[j-1] > num:
            nums[j] = nums[j-1]
            j -= 1
        nums[j] = num
    return nums

Merge sort

It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

  • Time : O(nlogn)
  • Space : O(n)

88. Merge Sorted Array

Merge Two Sorted Array in Merge Sort Algorithms

  • Three Pointers: nums1, nums2 and results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        p1, p2 = m-1, n-1
        idx = m+n-1
        while p1 >= 0 and p2 >= 0:
            if nums2[p2] > nums1[p1]:
                nums1[idx] = nums2[p2]
                p2 -= 1
            else:
                nums1[idx] = nums1[p1]
                p1 -= 1
            idx -= 1

        while p2 >= 0:
            nums1[idx] = nums2[p2]
            p2 -= 1
            idx -= 1

Merge k sorted array

  • Time : O(nlogk)
  1. sol1: Iterative way (Brute Force)
  2. sol2: Binary Reduction (Divide and Conquer)
  • if very large,so data in disk : read and write logk times
  1. sol3: k pointers smallest element(Heap)
  • if very large,so data in disk : read and write only 1 time

Counting Inversions

  • based on merge sort, count all the inversion paris!

Quick Sort

It picks an element as pivot and partitions the given array around the picked pivot.

  • The key process in quickSort is partition().
    Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def partition(nums, l, r):
    pivot = nums[r] # pick last element as pivot
    low = l
    for i in xrange(l, r):
        if nums[i] < pivot:
            nums[i], nums[low] = nums[low], nums[i]
            low += 1
    nums[low], nums[r] = nums[r], nums[low]
    return low

def quickSort(nums, l, r):
    if l >= r:
        return

    pivot = partition(nums, l, r)
    quickSort(nums, l, pivot-1)
    quickSort(nums, pivot+1, r)

215. Kth Largest Element in an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def findKthLargest(self, nums, k):
        l, r = 0, len(nums)-1
        while l <= r:
            idx = self.partition(nums, l, r)
            if idx > k-1:
                r = idx - 1
            elif idx < k-1:
                l = idx + 1
            else:
                return nums[idx]

    # Similar to Move Zeros!
    def partition(self, nums, l, r):
        if l >= r: return l

        pivot = nums[r]
        low = l
        for i in xrange(l, r):
            if nums[i] > pivot:
                nums[i], nums[low] = nums[low], nums[i]
                low += 1
        nums[low], nums[r] = nums[r], nums[low]
        return low

LintCode 80. Median

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    """
    @param nums: A list of integers
    @return: An integer denotes the middle number of the array
    """
    def median(self, nums):
        n = len(nums)
        k = (n + 1) // 2 - 1 # index we want to find
        left, right = 0, len(nums)-1
        while left <= right:
            idx = self.partition(nums, left, right)
            if idx == k:
                break
            elif idx < k:
                left = idx + 1
            else:
                right = idx - 1

        return nums[k]

    def partition(self, nums, left, right):
        pivot = nums[right]
        low = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[i], nums[low] = nums[low], nums[i]
                low += 1
        nums[low], nums[right] = nums[right], nums[low]
        return low

283. Move Zeroes

Maintaining the relative order of the non-zero elements.

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def moveZeroes(self, nums):
        non0 = 0
        n = len(nums)
        for i in xrange(n):
            if nums[i] != 0:
                nums[non0] = nums[i]
                non0 += 1
        for i in xrange(non0, n):
            nums[i] = 0
1
2
3
4
5
6
7
8
class Solution(object):
    def moveZeroes(self, nums):
        non0 = 0
        n = len(nums)
        for i in xrange(n):
            if nums[i] != 0:
                nums[non0], nums[i] = nums[i], nums[non0]
                non0 += 1

Follow up : order can be changed

The order of all other elments can be changed.

  • left and right pointer swap each number, it could change the order, but it reduces the operation number!
  • this method actually is similar to the partition function in Quick Sort!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def moveZeroes(self, nums):
        left, right = 0, len(nums)-1
        while left < right:
            while left < right and nums[left] != 0:
                left += 1
            while left < right and nums[right] == 0:
                right -= 1
            nums[left], nums[right] = nums[right], nums[left]
            print("operation")
            left += 1
            right -= 1

# Simplified Version
class Solution(object):
    def moveZeroes(self, nums):
        left, right = 0, len(nums)-1
        while left < right:
            if nums[left] != 0:
                left += 1
            elif nums[right] == 0:
                right -= 1
            else:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

Rainbow Sort

75. Sort Colors

Sol1. Counting Sort

two-pass algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
# Time : O(n)
# Space : O(n)
class Solution(object):
    def sortColors(self, nums):
        cnt = collections.defaultdict(int)
        for num in nums:
            cnt[num] += 1

        p = 0
        for i in xrange(3):
            for _ in xrange(cnt[i]):
                nums[p] = i
                p += 1

Sol2. Dutch Partitioning Problem

one-pass algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def sortColors(self, nums):
        l, r = 0, len(nums)-1
        i = 0
        while i <= r:
            if nums[i] == 0:
                nums[l], nums[i] = nums[i], nums[l]
                l += 1
                i += 1 # missing part
            elif nums[i] == 1:
                i += 1
            else:
                nums[i], nums[r] = nums[r], nums[i]
                r -= 1

Wiggle Sort

280. Wiggle Sort

Solution1. Sort

  • Time : O(nlogn)
    1
    2
    3
    4
    5
    class Solution(object):
        def wiggleSort(self, nums):
            nums.sort()
            for i in range(2, len(nums), 2):
                nums[i], nums[i-1] = nums[i-1], nums[i]

Solution2. One Pass

  • Time : O(n)
    1
    2
    3
    4
    5
    class Solution(object):
        def wiggleSort(self, nums):
            for i in range(1, len(nums)):
                if (i % 2 == 0 and nums[i] > nums[i-1]) or (i % 2 == 1 and nums[i] < nums[i-1]):
                    nums[i], nums[i-1] = nums[i-1], nums[i]

324. Wiggle Sort II

1
2
3
4
5
6
7
8
class Solution(object):
    def wiggleSort(self, nums):
        temp = sorted(nums)
        n = len(nums)
        for i in range(1, n, 2):
            nums[i] = temp.pop()
        for i in range(0, n, 2):
            nums[i] = temp.pop()

Big data

Sort with small memory

Given a single computer with a single CPU and a single core, which has 2GB of memory and 1GB available for use, it also has two 100GB hard drives. How to sort 80GB integers of 64bits.?

  • External Sort
  1. 400 chunks. Use 1GB memory to sort each 0.2GB. => write to disk
  2. 400-way merge
    chunk1 xxxxxx xxxxxxxxxxxxxxx
    chunk2 yyyyyy yyyyyyyyyyyyyyy
    …
    chunk400 zzzzzz zzzzzzzzzzzzzzz
    read from each chunk, block by block, insert into a min Heap.
  3. result block
  • Why read one block by block instead of one by one? File IO!!!
Share