Skip to content

Commit b624010

Browse files
liuyuboboboliuyubobobo
committed
Chapter 02 Optimized Selection Sort added.
1 parent 108d1aa commit b624010

File tree

34 files changed

+538
-3
lines changed

34 files changed

+538
-3
lines changed

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Optimized-Selection-Sort/CMakeLists.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
cmake_minimum_required(VERSION 3.5)
2+
project(Optional_01_Optimized_Selection_Sort)
3+
4+
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
5+
6+
set(SOURCE_FILES main.cpp)
7+
add_executable(Optional_01_Optimized_Selection_Sort ${SOURCE_FILES})

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Optimized-Selection-Sort/InsertionSort.h

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
//
2+
// Created by Yuan Zhang on 11/14/17.
3+
//
4+
5+
#ifndef OPTIONAL_01_OPTIMIZED_SELECTION_SORT_INSERTIONSORT_H
6+
#define OPTIONAL_01_OPTIMIZED_SELECTION_SORT_INSERTIONSORT_H
7+
8+
#endif //OPTIONAL_01_OPTIMIZED_SELECTION_SORT_INSERTIONSORT_H

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Optimized-Selection-Sort/SelectionSort.h

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2+
//
3+
// Created by liuyubobobo on 7/16/16.
4+
//
5+
6+
#ifndef INC_04_INSERTION_SORT_ADVANCE_SELECTIONSORT_H
7+
#define INC_04_INSERTION_SORT_ADVANCE_SELECTIONSORT_H
8+
9+
#include <iostream>
10+
#include <algorithm>
11+
12+
using namespace std;
13+
14+
15+
#include <iostream>
16+
#include <algorithm>
17+
18+
using namespace std;
19+
20+
21+
template<typename T>
22+
void insertionSort(T arr[], int n){
23+
24+
for( int i = 1 ; i < n ; i ++ ) {
25+
26+
T e = arr[i];
27+
int j;
28+
for (j = i; j > 0 && arr[j-1] > e; j--)
29+
arr[j] = arr[j-1];
30+
arr[j] = e;
31+
}
32+
33+
return;
34+
}
35+
36+
#endif //INC_04_INSERTION_SORT_ADVANCE_SELECTIONSORT_H

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Optimized-Selection-Sort/SortTestHelper.h

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
//
2+
// Created by liuyubobobo on 7/13/16.
3+
//
4+
5+
#ifndef INC_04_INSERTION_SORT_ADVANCE_SORTTESTHELPER_H
6+
#define INC_04_INSERTION_SORT_ADVANCE_SORTTESTHELPER_H
7+
8+
#include <iostream>
9+
#include <algorithm>
10+
#include <string>
11+
#include <ctime>
12+
#include <cassert>
13+
#include <string>
14+
15+
using namespace std;
16+
17+
18+
namespace SortTestHelper {
19+
20+
// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
21+
int *generateRandomArray(int n, int range_l, int range_r) {
22+
23+
int *arr = new int[n];
24+
25+
srand(time(NULL));
26+
for (int i = 0; i < n; i++)
27+
arr[i] = rand() % (range_r - range_l + 1) + range_l;
28+
return arr;
29+
}
30+
31+
// 生成一个近乎有序的数组
32+
// 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据
33+
// swapTimes定义了数组的无序程度:
34+
// swapTimes == 0 时, 数组完全有序
35+
// swapTimes 越大, 数组越趋向于无序
36+
int *generateNearlyOrderedArray(int n, int swapTimes){
37+
38+
int *arr = new int[n];
39+
for(int i = 0 ; i < n ; i ++ )
40+
arr[i] = i;
41+
42+
srand(time(NULL));
43+
for( int i = 0 ; i < swapTimes ; i ++ ){
44+
int posx = rand()%n;
45+
int posy = rand()%n;
46+
swap( arr[posx] , arr[posy] );
47+
}
48+
49+
return arr;
50+
}
51+
52+
// 拷贝整型数组a中的所有元素到一个新的数组, 并返回新的数组
53+
int *copyIntArray(int a[], int n){
54+
55+
int *arr = new int[n];
56+
//* 在VS中, copy函数被认为是不安全的, 请大家手动写一遍for循环:)
57+
copy(a, a+n, arr);
58+
return arr;
59+
}
60+
61+
// 打印arr数组的所有内容
62+
template<typename T>
63+
void printArray(T arr[], int n) {
64+
65+
for (int i = 0; i < n; i++)
66+
cout << arr[i] << " ";
67+
cout << endl;
68+
69+
return;
70+
}
71+
72+
// 判断arr数组是否有序
73+
template<typename T>
74+
bool isSorted(T arr[], int n) {
75+
76+
for (int i = 0; i < n - 1; i++)
77+
if (arr[i] > arr[i + 1])
78+
return false;
79+
80+
return true;
81+
}
82+
83+
// 测试sort排序算法排序arr数组所得到结果的正确性和算法运行时间
84+
template<typename T>
85+
void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {
86+
87+
clock_t startTime = clock();
88+
sort(arr, n);
89+
clock_t endTime = clock();
90+
cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
91+
92+
assert(isSorted(arr, n));
93+
94+
return;
95+
}
96+
97+
};
98+
99+
#endif //INC_04_INSERTION_SORT_ADVANCE_SORTTESTHELPER_H

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Optimized-Selection-Sort/main.cpp

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
#include <iostream>
2+
#include <algorithm>
3+
#include "SortTestHelper.h"
4+
#include "SelectionSort.h"
5+
#include "InsertionSort.h"
6+
7+
using namespace std;
8+
9+
// 感谢github @zhengquan45 提出, 可以对选择排序进行优化
10+
// 在每一轮中, 可以同时找到当前未处理元素的最大值和最小值
11+
template<typename T>
12+
void selectionSort(T arr[], int n){
13+
14+
int left = 0, right = n - 1;
15+
while(left < right){
16+
int minIndex = left;
17+
int maxIndex = right;
18+
19+
// 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]
20+
if(arr[minIndex] > arr[maxIndex])
21+
swap(arr[minIndex], arr[maxIndex]);
22+
23+
for(int i = left + 1 ; i < right; i ++)
24+
if(arr[i] < arr[minIndex])
25+
minIndex = i;
26+
else if(arr[i] > arr[maxIndex])
27+
maxIndex = i;
28+
29+
swap(arr[left], arr[minIndex]);
30+
swap(arr[right], arr[maxIndex]);
31+
32+
left ++;
33+
right --;
34+
}
35+
36+
return;
37+
}
38+
39+
int main() {
40+
41+
int n = 40000;
42+
43+
// 测试1 一般测试
44+
cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
45+
int *arr1 = SortTestHelper::generateRandomArray(n,0,n);
46+
int *arr2 = SortTestHelper::copyIntArray(arr1, n);
47+
int *arr3 = SortTestHelper::copyIntArray(arr1, n);
48+
49+
SortTestHelper::testSort("Insertion Sort", insertionSort,arr1,n);
50+
SortTestHelper::testSort("Selection Sort", selectionSort,arr2,n);
51+
SortTestHelper::testSort("Selection Sort 2", selectionSort,arr3,n);
52+
53+
delete[] arr1;
54+
delete[] arr2;
55+
delete[] arr3;
56+
57+
cout<<endl;
58+
59+
60+
// 测试2 有序性更强的测试
61+
cout<<"Test for more ordered random array, size = "<<n<<", random range [0, 3]"<<endl;
62+
arr1 = SortTestHelper::generateRandomArray(n,0,3);
63+
arr2 = SortTestHelper::copyIntArray(arr1, n);
64+
arr3 = SortTestHelper::copyIntArray(arr1, n);
65+
66+
SortTestHelper::testSort("Insertion Sort", insertionSort,arr1,n);
67+
SortTestHelper::testSort("Selection Sort", selectionSort,arr2,n);
68+
SortTestHelper::testSort("Selection Sort 2", selectionSort,arr3,n);
69+
70+
delete[] arr1;
71+
delete[] arr2;
72+
delete[] arr3;
73+
74+
cout<<endl;
75+
76+
77+
// 测试3 测试近乎有序的数组
78+
int swapTimes = 100;
79+
cout<<"Test for nearly ordered array, size = "<<n<<", swap time = "<<swapTimes<<endl;
80+
arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);
81+
arr2 = SortTestHelper::copyIntArray(arr1, n);
82+
arr3 = SortTestHelper::copyIntArray(arr1, n);
83+
84+
SortTestHelper::testSort("Insertion Sort", insertionSort,arr1,n);
85+
SortTestHelper::testSort("Selection Sort", selectionSort,arr2,n);
86+
SortTestHelper::testSort("Selection Sort 2", selectionSort,arr3,n);
87+
88+
delete[] arr1;
89+
delete[] arr2;
90+
delete[] arr3;
91+
92+
return 0;
93+
}

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Bubble-Sort/CMakeLists.txt renamed to ‎02-Sorting-Basic/Course Code (C++)/Optional-02-Bubble-Sort/CMakeLists.txt

File renamed without changes.

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Bubble-Sort/InsertionSort.h renamed to ‎02-Sorting-Basic/Course Code (C++)/Optional-02-Bubble-Sort/InsertionSort.h

File renamed without changes.

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Bubble-Sort/SelectionSort.h renamed to ‎02-Sorting-Basic/Course Code (C++)/Optional-02-Bubble-Sort/SelectionSort.h

File renamed without changes.

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Bubble-Sort/SortTestHelper.h renamed to ‎02-Sorting-Basic/Course Code (C++)/Optional-02-Bubble-Sort/SortTestHelper.h

File renamed without changes.

‎02-Sorting-Basic/Course Code (C++)/Optional-01-Bubble-Sort/main.cpp renamed to ‎02-Sorting-Basic/Course Code (C++)/Optional-02-Bubble-Sort/main.cpp

File renamed without changes.

0 commit comments

Comments
 (0)