- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
这是家庭作业。我最终会将这段代码翻译成 MIPS 汇编,但这对我来说是容易的部分。我已经调试这段代码好几个小时了,也去过我教授的办公时间,但我仍然无法让我的快速排序算法发挥作用。以下是代码以及我认为问题所在的一些评论:
// This struct is in my .h file
typedef struct {
// v0 points to the first element in the array equal to the pivot
int *v0;
// v1 points to the first element in the array greater than the pivot (one past the end of the pivot sub-array)
int *v1;
} PartRet;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
PartRet partition(int *lo, int *hi) {
// Will later be translating this to MIPS where 2 values can be returned. I am using a PartRet struct to simulate this.
PartRet retval;
// We must use the last item as the pivot
int pivot = *hi;
int *left = lo;
// Take the last value before the pivot
int *right = hi - 1;
while (left < right) {
while((left < hi) && (*left <= pivot)) {
++left;
}
while((right > lo) && (*right > pivot)) {
--right;
}
if (left < right) {
swap(left++, right--);
}
}
// Is this correct? left will always be >= right after the while loop
if (*hi < *left) {
swap(left, hi);
}
// MADE CHANGE HERE
int *v0 = hi;
int *v1;
// Starting at the left pointer, find the beginning of the sub-array where the elements are equal to the pivot
// MADE CHANGE HERE
while (v0 > lo && *(v0 - 1) >= pivot) {
--v0;
}
v1 = v0;
// Starting at the beginning of the sub-array where the elements are equal to the pivot, find the element after the end of this array.
while (v1 < hi && *v1 == pivot) {
++v1;
}
if (v1 <= v0) {
v1 = hi + 1;
}
// Simulating returning two values
retval.v0 = v0;
retval.v1 = v1;
return retval;
}
void quicksort(int *array, int length) {
if (length < 2) {
return;
}
PartRet part = partition(array, array + length - 1);
// I *think* this first call is correct, but I'm not sure.
int firstHalfLength = (int)(part.v0 - array);
quicksort(array, firstHalfLength);
int *onePastEnd = array + length;
int secondHalfLength = (int)(onePastEnd - part.v1);
// I have a feeling that this isn't correct
quicksort(part.v1, secondHalfLength);
}
我什至尝试使用在线代码示例重写代码,但要求是使用 lo 和 hi 指针,但我发现没有任何代码示例使用它。当我调试代码时,我最终只使代码适用于某些数组,而不适用于其他数组,尤其是当基准是数组中的最小元素时。
最佳答案
分区代码有问题。下面是来自 SSCCE 代码的 4 个简单测试输出:
array1:
Array (Before):
[6]: 23 9 37 4 2 12
Array (First half partition):
[3]: 2 9 4
Array (First half partition):
[1]: 2
Array (Second half partition):
[1]: 9
Array (Second half partition):
[2]: 23 37
Array (First half partition):
[0]:
Array (Second half partition):
[1]: 23
Array (After):
[6]: 2 4 9 12 37 23
array2:
Array (Before):
[3]: 23 9 37
Array (First half partition):
[1]: 23
Array (Second half partition):
[1]: 9
Array (After):
[3]: 23 37 9
array3:
Array (Before):
[2]: 23 9
Array (First half partition):
[0]:
Array (Second half partition):
[1]: 23
Array (After):
[2]: 9 23
array4:
Array (Before):
[2]: 9 24
Array (First half partition):
[0]:
Array (Second half partition):
[1]: 9
Array (After):
[2]: 24 9
#include <stdio.h>
typedef struct
{
int *v0; // v0 points to the first element in the array equal to the pivot
int *v1; // v1 points to the first element in the array greater than the pivot (one past the end of the pivot sub-array)
} PartRet;
static void dump_array(FILE *fp, const char *tag, int *array, int size)
{
fprintf(fp, "Array (%s):\n", tag);
fprintf(fp, "[%d]:", size);
for (int i = 0; i < size; i++)
fprintf(fp, " %d", array[i]);
putchar('\n');
}
static void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
static PartRet partition(int *lo, int *hi)
{
// Will later be translating this to MIPS where 2 values can be
// returned. I am using a PartRet struct to simulate this.
PartRet retval;
// This code probably won't ever be hit as the base case in the QS
// function will return first
if ((hi - lo) < 1)
{
retval.v0 = lo;
retval.v1 = lo + (hi - lo) - 1;
return retval;
}
// We must use the last item as the pivot
int pivot = *hi;
int *left = lo;
// Take the last value before the pivot
int *right = hi - 1;
while (left < right)
{
if (*left <= pivot)
{
++left;
continue;
}
if (*right >= pivot)
{
--right;
continue;
}
swap(left, right);
}
// Is this correct? left will always be >= right after the while loop
swap(left, hi);
int *v0 = left;
int *v1;
// Starting at the left pointer, find the beginning of the sub-array
// where the elements are equal to the pivot
while (v0 > lo && *(v0 - 1) == pivot)
{
--v0;
}
v1 = v0;
// Starting at the beginning of the sub-array where the elements are
// equal to the pivot, find the element after the end of this array.
while (v1 < hi && *v1 == pivot)
{
++v1;
}
// Simulating returning two values
retval.v0 = v0;
retval.v1 = v1;
return retval;
}
static void quicksort(int *array, int length)
{
if (length < 2)
{
return;
}
PartRet part = partition(array, array + length - 1);
// I *think* this first call is correct, but I'm not sure.
int firstHalfLength = (int)(part.v0 - array);
dump_array(stdout, "First half partition", array, firstHalfLength);
quicksort(array, firstHalfLength);
int *onePastEnd = array + length;
int secondHalfLength = (int)(onePastEnd - part.v1);
// I have a feeling that this isn't correct
dump_array(stdout, "Second half partition", part.v1, secondHalfLength);
quicksort(part.v1, secondHalfLength);
}
static void mini_test(FILE *fp, const char *name, int *array, int size)
{
putc('\n', fp);
fprintf(fp, "%s:\n", name);
dump_array(fp, "Before", array, size);
quicksort(array, size);
dump_array(fp, "After", array, size);
putc('\n', fp);
}
int main(void)
{
int array1[] = { 23, 9, 37, 4, 2, 12 };
enum { NUM_ARRAY1 = sizeof(array1) / sizeof(array1[0]) };
mini_test(stdout, "array1", array1, NUM_ARRAY1);
int array2[] = { 23, 9, 37, };
enum { NUM_ARRAY2 = sizeof(array2) / sizeof(array2[0]) };
mini_test(stdout, "array2", array2, NUM_ARRAY2);
int array3[] = { 23, 9, };
enum { NUM_ARRAY3 = sizeof(array3) / sizeof(array3[0]) };
mini_test(stdout, "array3", array3, NUM_ARRAY3);
int array4[] = { 9, 24, };
enum { NUM_ARRAY4 = sizeof(array4) / sizeof(array4[0]) };
mini_test(stdout, "array4", array4, NUM_ARRAY4);
return(0);
}
我没有对排序代码进行任何算法更改。我只是添加了 dump_array()
函数,并对它进行了策略性调用,然后添加了 mini_test()
函数和 main()
。这些固定装置非常有用。请注意,当输入数组的大小为 2 且顺序错误时,分区是正确的,但当大小为 2 且顺序正确时,分区将数组元素的位置颠倒了。这是有问题的!解决它,您可能已经修复了其余大部分。在所有 6 个排列(3 个不同的值)中玩一些 3 个元素数组;考虑使用 3 个元素和 2 个不同的值,以及 3 个元素和 1 个值。
关于c - 快速排序算法不适用于所有数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15652181/
我在我的 Xcode 项目目录中输入了以下内容: keytool -genkey -v -keystore release.keystore -alias mykey -keyalg RSA \
假设我有一个像这样的 DataFrame(或 Series): Value 0 0.5 1 0.8 2 -0.2 3 None 4 None 5 None
我正在对一个 Pandas 系列进行相对繁重的应用。有什么方法可以返回一些打印反馈,说明每次调用函数时在函数内部进行打印还有多远? 最佳答案 您可以使用跟踪器包装您的函数。以下两个示例,一个基于完成的
我有一个 DataFrame,其中一列包含列表作为单元格内容,如下所示: import pandas as pd df = pd.DataFrame({ 'col_lists': [[1, 2
我想使用 Pandas df.apply 但仅限于某些行 作为一个例子,我想做这样的事情,但我的实际问题有点复杂: import pandas as pd import math z = pd.Dat
我有以下 Pandas 数据框 id dist ds 0 0 0 0 5 1 0 0 7 2 0 0
这发生在我尝试使用 Gradle 构建时。由于字符串是对象,因此似乎没有理由发生此错误: No signature of method: java.util.HashMap.getOrDefault(
您好,有人可以解释为什么在 remaining() 函数中的 Backbone 示例应用程序 ( http://backbonejs.org/examples/todos/index.html ) 中
我有两个域类:用户 class User { String username String password String email Date dateCreated
问题陈述: 一个 pandas dataframe 列系列,same_group 需要根据两个现有列 row 和 col 的值从 bool 值创建。如果两个值在字典 memberships 中具有相似
apporable 报告以下错误: error: unknown type name 'MKMapItem'; did you mean 'MKMapView'? MKMapItem* destina
我有一个带有地址列的大型 DataFrame: data addr 0 0.617964 IN,Krishnagiri,635115 1 0.635428 IN,Chennai
我有一个列表list,里面有这样的项目 ElementA: Number=1, Version=1 ElementB: Number=1, Version=2 ElementC: Number=1,
我正在编译我的源代码,它只是在没有运行应用程序的情况下终止。这是我得到的日志: Build/android-armeabi-debug/com.app4u.portaldorugby/PortalDo
我正在尝试根据另一个单元格的值更改单元格值(颜色“红色”或“绿色”)。我运行以下命令: df.loc[0, 'Colour'] = df.loc[0, 'Count'].apply(lambda x:
我想弄清楚如何使用 StateT结合两个 State基于对我的 Scalaz state monad examples 的评论的状态转换器回答。 看来我已经很接近了,但是在尝试申请 sequence
如果我已经为它绑定(bind)了集合,我该如何添加 RibbonLibrary 默认的快速访问项容器。当我从 UI 添加快速访问工具项时,它会抛出 Operation is not valid whi
在我学习期间Typoclassopedia我遇到了这个证明,但我不确定我的证明是否正确。问题是: One might imagine a variant of the interchange law
我是一名优秀的程序员,十分优秀!