Biantian's Studio.

DS 05

DS
Word count: 647Reading time: 4 min
2020/04/14 Share

Sorting

Selection Sort

1. Algorithm:

  1. Split the array in two parts such that:
    • the first part of the array is sorted.
    • the second part contains elements than the elements in the first part.
  2. Pick the smallest element from the second part.
  3. Swap it with the element on the position right after the sorted part.
  4. The first part is initially empty.

Pseudocode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selection_sort(int[] arr){
    int n = arr.length;
    for(int i=0;i<n;i++){
        int min = i;
        // Find the smallest on positions i, i+1, ..., n-1
        for(int j=i;j<nj++){
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        // swap arr[min] and arr[i]
        final int temp = arr[min];
        arr[min] = arr[i];
        arr[i] = tmp;
    }
}

2. Time Complexity


Heap Sort

1. Algorithm:

  1. Build a (min) heap1 from the elements in the array.
  2. Then, do the following n-times:
    1. Pick the smallest element from the heap (root).
    2. Place it on the position right after the sorted part.

2. Time Complexity:

  • Building the heap is in .
  • Deleting the minimum from a heap is in - we do this n-times: .

The time complexity is .

Pseudocode:

1
2
3
4
5
6
7
void heap_sort(int[] arr){
    final MinHeap h = new MinHeap<Int>();
    h.heapify(arr);
    for(int i=0;i<arr.length;i++){
        arr[i] = h.deleteMin();
    }
}


Theoretically best

No comparison-based sorting algorithm has the Worst Case time complexity better than .


Merge Sort

1. Idea:

  1. Split the array into two halves.
  2. Sort each of them recursively.
  3. Merge the sorted parts.

2. Merging two sorted arrays a[-] and b[-] efficiently

Pseudocode:

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
30
31
32
33
34
35
36
37
38
39
40
void mergesort(int[] arr){
    mergesort_run(arr,0,arr.length);
}

void mergesort_run(int[] arr, int left, int right){
    if(right - left <= 1) return;
    int mid = (left + right) div 2;
    mergesort_run(arr, left, mid);
    mergesort_run(arr, mid, right);
    merge(arr, left, mid, right);
}

// Merging 
void merge(int[] arr, int left, int mid, int right){
    int[] tmp = new int[right-left];
    int i=0;
    int j=0;
    while(left+i < mid && mid+j < right){
        if(arr[left+i] <= arr[mid+j]){
            tmp[i+j] = arr[left+i];
            i++;
        }else{
            tmp[i+j] = arr[mid+j];
            j++;
        }
    }
    // Copy the rest
    while(left+i < mid){
        temp[i+j] = arr[left+i];
        i++;
    }
    while(mid+j < right){
        temp[i+j] = arr[mid+j];
        j++;
    }
    // Copy the sorted array in tmp back into arr
    for(i=0;i<right-left;i++){
        arr[left+i] = tmp[i];
    }
}

3. Time Complexity

.


Quick Sort

1. Idea

  1. Select an element of the array, which we call pivot.
  2. Partition the array so that the "small entries" (pivot) are on the left, then the pivot, then the "large entries" (pivot).
  3. Recursively (quick) sort the two partitions.

2. Pseudocode

1
2
3
4
5
6
7
8
9
10
void quicksort(int[] arr){
    quicksort_run(arr, 0, arr.length);
}

void quicksort_run(int[] arr, int left, int right){
    if(right = left) return;
    pivot_index = partition(arr, left, right);
    quicksort_run(arr, left, pivot_index);
    quicksort_run(arr, pivot_index+1, right);
}

3. Partitioning array arr

Idea

  1. Choose a pivot p from arr.
  2. Allocate two temporary arrays: tmpLE and tmpG.
  3. Store all elements less than or equal to p to tmpLE.
  4. Store all elements greater than p to tmpG.
  5. Copy the arrays tmpLE and tmpGback to arr and return the index of p in arr.

4. Time Complexity

Best Case:

Worst Case:

Average Case:

5. Pivot-selection strategies

You should consider the case that your array is already sorted, or that portions are.

It can be shown that if all permutations are equally likely, then regardless of pivot selection strategy, quicksort takes average case.

Choose pivot as:

  1. the middle entry (good for sorted sequences, unlike the leftmost-strategy).
  2. the median of the leftmost, rightmost and middle entries.
  3. use Quickselect to choose median in .
  4. a random entry (there is 50% chance for a good pivot).

  1. Min heap - The priority of every node is lower than that of its children.↩

Author：Biantian

原文链接：http://biantian.github.io/2020/04/14/ds5/

发表日期：April 14th 2020, 8:33:42 am

更新日期：April 15th 2020, 2:57:11 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Sorting
    1. 1.1. Selection Sort
      1. 1.1.1. 1. Algorithm:
      2. 1.1.2. 2. Time Complexity
    2. 1.2. Heap Sort
      1. 1.2.1. 1. Algorithm:
      2. 1.2.2. 2. Time Complexity:
    3. 1.3. Theoretically best
    4. 1.4. Merge Sort
      1. 1.4.1. 1. Idea:
      2. 1.4.2. 2. Merging two sorted arrays a[-] and b[-] efficiently
      3. 1.4.3. 3. Time Complexity
    5. 1.5. Quick Sort
      1. 1.5.1. 1. Idea
      2. 1.5.2. 2. Pseudocode
      3. 1.5.3. 3. Partitioning array arr
      4. 1.5.4. 4. Time Complexity
      5. 1.5.5. 5. Pivot-selection strategies
Total : 12
2020
AI DB DS hashtable OSN hexo web note
Revision