Data Structure Notes

Chapter-1 Sorting Algorithm

• Selection Sorting:

/*
*   Selection Sort
*/
template<typename T>
void selectionSort(T arr[], int n) {
    for (int i = 0;i < n;i++) {
        int minIndex = i;
        for (int j = i + 1;j < n;j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }
}

// From both ends to exchange the elements in original array, it's a better solution optimize the previous Selection Sort.
template<typename T>
void OptimizedselectionSort(T arr[], int n) {

    int left = 0, right = n - 1;
    while (left < right) {
        int minIndex = left;
        int maxIndex = right;

        // In each rounds must assure arr[minIndex] <= arr[maxIndex]
        if (arr[minIndex] > arr[maxIndex])
            swap(arr[minIndex], arr[maxIndex]);

        //Traversing the array to choose the match positon.
        for (int i = left + 1; i < right; i++)
            if (arr[i] < arr[minIndex])
                minIndex = i;
            else if (arr[i] > arr[maxIndex])
                maxIndex = i;

        swap(arr[left], arr[minIndex]);
        swap(arr[right], arr[maxIndex]);

        left++;
        right--;
    }

    return;
}

• Bubble Sorting:

/*
*   BubbleSort
*/
template<typename T>
void BubbleSort(T arr[], int n) {

    bool swapped;

    do {
        swapped = false;
        for (int i = 1; i < n; i++)
            if (arr[i - 1] > arr[i]) {
                swap(arr[i - 1], arr[i]);
                swapped = true;

            }

        // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
        // 所以下一次排序, 最后的元素可以不再考虑
        n--;

    } while (swapped);
}


// 我们的第二版bubbleSort,使用newn进行优化
template<typename T>
void OptimizedBubbleSort(T arr[], int n) {

    int newn; // 使用newn进行优化

    do {
        newn = 0;
        for (int i = 1; i < n; i++)
            if (arr[i - 1] > arr[i]) {
                swap(arr[i - 1], arr[i]);

                // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                newn = i;
            }
        n = newn;
    } while (newn > 0);
}

• Shell Sorting:

template<typename T>
void shellSort(T arr[], int n) {

    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
    int h = 1;
    while (h < n / 3)
        h = 3 * h + 1;

    while (h >= 1) {

        // h-sort the array
        for (int i = h; i < n; i++) {

            // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            T e = arr[i];
            int j;
            for (j = i; j >= h && e < arr[j - h]; j -= h)
                arr[j] = arr[j - h];
            arr[j] = e;
        }

        h /= 3;
    }
}

• Insert Sorting: 对于近乎有序的数组可以降到$ O(n)$的时间复杂度。

template<typename T>
void BinaryInsertionSort(T arr[], int n) {
    int i, j, low, high, mid;
    for (i = 1;i < n;i++) {
        T e = arr[i];
        
        //Binary Searching in the ordered range of array.
        low = 0; high = i - 1;
        while (low<= high)
        {
            mid = (low + high) / 2;
            if (arr[mid] > e) high = mid - 1;
            else low = mid + 1;
        }
        //Moving elements.
        for (j = i - 1;j >= high + 1;--j) {
            arr[j + 1] = arr[j];
        }
        arr[high + 1] = e;
    }
}

template<typename T>
void OptimizedInsertionSort(T arr[], int n) {
    for (int i = 1;i < n;i++) {

        // Find right position without exchange frequently.
        T e = arr[i];
        int j;
        for (j = i;j > 0 && arr[j - 1] > e;j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
}

• Merge Sorting:
  • Tips1：Merge Sort Optimize in nearly ordered array

  void __mergeSort(T arr[], int l, int r) {
      if (l >= r) return;
  
      int mid = (l + r) / 2;      // variable 'mid' may overflow
      __mergeSort(arr, l, mid);
      __mergeSort(arr, mid+1, r);
      if(arr[mid] > arr[mid+1])   // optimize in nearly ordered array.
          __merge(arr, l, mid, r);
  }

  • Tips2：When the sorting range of array in a short length, using InsertSort replace MergeSort can be more faster.

   template<typename T>
  void __mergeSort(T arr[], int l, int r) {
      //if (l >= r) return;
      if (r - l <= 15) {           // The '15' is a constant represent the minmum jud