#include "quicksort.h"
/*
* You should implement this. It is the meat of the constructor
* and is also used by the reset() method.
*
* It will create the QuickSort object with an "unsorted" list.
*
* - how_many is the number of elements in the list.
* - workload_type is BEST_CASE, WORST_CASE, or AVG_CASE
*/
void quicksort::init (int how_many, int workload_type) {
/*
* Insert your code here
*
* IMPORTANT NOTE: You need to allocate the numbers array declared in
* the sort class so that it can hold "how_many" numbers, and you
* need to fill numbers (integers) into this array. The ordering
* should be determined by the workload.
*
* Since you may be using the same workload for many different sorts
* and configurations of the same sort, you might want to use
* helper methods. Helper methods that should be accessible to
* all of the sorts should be "protected (not public or private) and
* placed in the Sort class. Helper methods used by only this sort
* can stay in this file and be made "private".
*
* This method should NOT sort the array.
*/
srand(clock() / 1000);
/*
* Your code goes here
*/
switch (workload_type){
case BEST_CASE:
for (int i = 0; i < how_many; i++)
numbers[i] = i;
break;
case WORST_CASE:
for (int i = 0; i < how_many; i++)
numbers[i] = how_many - i;
break;
case AVG_CASE:
for (int i = 0; i < how_many; i++)
numbers[i] = rand();
break;
}
}
/*
* This is the constructor. It is nothing more than a shell to
* call init(). This allows init() to be used by both the constructor
* and also the parent class's reset() method
*/
quicksort::quicksort (int how_many, int workload_type) {
this->how_many = how_many;
this->workload_type = workload_type;
init (how_many, workload_type);
}
/*
* This is the implementation of the quick sort algorithm that
* extends the Sort class's abstract sortNumbers() method.
*
* It is really a wrapper for the private helper method, sortPartition(),
* which does the real "divide and conquer".
*/
void quicksort::sortNumbers() {
sortPartition (0, how_many - 1);
}
/*
* This is a helper method called by sortNumbers(). It sorts
* an individual partition about the pivot point.
*/
int quicksort::partition (int left, int right) {
int pivot = numbers[left];
int l = left + 1;
int r = right;
while (l <= r) {
while (l <= right && numbers[l] <= pivot) {
l++;
}
while (r >= left && numbers[r] > pivot) {
r--;
}
if (l < r) {
swapNumbers(l, r);
l++;
r--;
}
}
swapNumbers(left, r); // put pivot in middle
return r;
}
/*
* This is a helper method called by sortNumbers(). It recursively
* calls itself on subpartitions to sort the numbers. The actual
* sorting within the partition is done by sortPartition(), which
* is iterative.
*/
void quicksort::sortPartition (int left, int right) {
int placed = partition (left, right);
if ((placed - left) > 1) sortPartition (left, placed - 1);
if ((right - placed) > 1) sortPartition (placed + 1, right);
}
没有合适的资源?快使用搜索试试~ 我知道了~
Optional_Exe_5.rar_decide
共30个文件
tlog:6个
cpp:4个
obj:4个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 131 浏览量
2022-09-20
21:54:58
上传
评论
收藏 1.78MB RAR 举报
温馨提示
This is a decide of Recomended Exercise 4 SSD5. I hope, I helped you
资源推荐
资源详情
资源评论
收起资源包目录
Optional_Exe_5.rar (30个子文件)
Optional_Exe_5
Optional_Exe_5.sdf 6.94MB
Optional_Exe_5
Optional_Exe_5.vcxproj 4KB
Optional_Exe_5.vcxproj.user 165B
selectionsort.h 277B
sort.cpp 1KB
main.cpp 2KB
Optional_Exe_5.vcxproj.filters 2KB
quicksort.h 404B
selectionsort.cpp 2KB
sort.h 850B
Debug
vc120.pdb 340KB
quicksort.obj 139KB
Optional_Exe_5.tlog
CL.write.1.tlog 4KB
CL.read.1.tlog 49KB
Optional_Exe_5.lastbuildstate 208B
cl.command.1.tlog 3KB
link.write.1.tlog 1KB
link.command.1.tlog 2KB
link.read.1.tlog 4KB
sort.obj 151KB
main.obj 151KB
selectionsort.obj 138KB
Optional_Exe_5.log 1KB
vc120.idb 379KB
quicksort.cpp 3KB
Debug
Optional_Exe_5.exe 72KB
Optional_Exe_5.ilk 497KB
Optional_Exe_5.pdb 820KB
Optional_Exe_5.sln 988B
Optional_Exe_5.v12.suo 22KB
共 30 条
- 1
资源评论
御道御小黑
- 粉丝: 58
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于STM32F103C8T6单片机蓄电池在线监测系统主板硬件(原理图+PCB)工程文件.zip
- mysql大纲资料.txt
- c++大纲资料.txt
- 效率工具bat脚本实现日志提取
- MyBatis 中动态 SQL 的示例
- STM8L101F3P6单片机+CC1100模块433M遥控器设计硬件(原理图+PCB)工程文件.zip
- 上传下载铁人下载系统 Liuxing 1.0-liuxing1.0.rar
- 南京邮电大学数学实验实力雄厚,凭借其优秀的师资力量、丰富的实践教学资源和卓越的科研成果,成为国内一流的数学实验教学和科研基地
- 【火爆朋友圈的今天吃什么源码 v1.0】随机的为用户带来每一天的用餐选择和推荐.rar
- MPU6050中文版数据手册
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功