简单排序函数(C++/Processing/Java)
Simple sorting function (C++/Processing/Java)
void sort_records_by_id (int []indices, int []students_id )
{
for (int k = 0; k<indices.length; k++)
{
for (int j = k; j>0 && indices[j]<indices[j-1]; j--)
{
int place holder = indices[j];
indices[j] = indices [j-1];
indices[j-1] = place_holder;
}
}
}
void setup()
{
int [] students_id= {10001, 20001, 12334, 14332, 99999, 10111, 20101, 12034, 10332, 99991} ;
double [] midterm_marks = {99, 67, 88, 91, 56, 90, 70, 69, 79, 59};
double [] final_marks = {89, 76, 80, 67, 99, 98, 56, 96, 90, 60};
String [] students_name= {"Tim", "Joe", "Ali", "Kim", "Pam", "Rob", "Ben", "Ted", "Lee", "Jim"};
print_records(students_id, midterm_marks, final_marks, students_name);
// Using array of indices to use as an indicator of the order of teh records based on students id numbers
int[] indices = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// using insertion sort to reorder the indices based on students ids in an ascending order
sort_records_by_id(indices, students_id);
println();
println("The students records after sorting them by their id numbers are as follows:");
print_sorted_records(indices, students_id, midterm_marks, final_marks, students_name);
// Searching for the position of a student in the array of names and printing his/her records
// serarching for "Kim"
int position = search(students_name, "Kim");
if(position == -1) {
println("Search failed: " + "Kim" + " NOT FOUND");
}
else {
double average = calculate_student_average(midterm_marks[position], final_marks[position]);
println(students_name[position] + " was found: id: " + students_id[position]
+ " midterm mark: " + midterm_marks[position] + ", final mark: " + final_marks[position]
+ ", term average: " + average + ", and overal grade: " + letter_grade_calculation (average));
}
// Searching for "Sam"
position = search(students_name, "Sam");
if(position == -1) {
println("Search failed: " + "Sam" + " NOT FOUND");
}
else {
double average = calculate_student_average(midterm_marks[position], final_marks[position]);
println(students_name[position] + " was found: id is: " + students_id[position]
+ " midterm mark: " + midterm_marks[position] + ", final mark: " + final_marks[position]
+ ", term average: " + average + ", and overal grade: " + letter_grade_calculation (average));
}
}
/*
--------------------------------------------------------------------
The purpose of this function is to calculate the average of all the
numbers contained in an array and return that value to the calling
function.
The function REQUIRES
- An array of type double
The function PROMISES
-To return a value of type double to the user
representing the average of the array passed
by the user.
---------------------------------------------------------------------
*/
double calculate_class_average (double [] exam)
{
int i = 0;
double sum = 0;
//iterate through loop and add together the
//elements of the array into local variable
//"sum"
for (i = 0; i<exam.length; i++)
{
sum+=exam[i];
}
//Return the value of the average calculated
//by dividing sum, by the number of times the
//loop was executed, representing the # of elements
return (sum/i);
}
/*
-----------------------------------------------------------------------
The purpose of this function is to calculate the average between
two real numbers passed by the user and return that value to the
calling function
The function REQUIRES:
-Two real numbers of type double
The function PROMISES:
-To return the average between the
two values passed by the user as a
value of type double
-----------------------------------------------------------------------
*/
double calculate_student_average(double mid_mark, double final_mark)
{
//Calculate and retrun the average
//between the two numbers
return (mid_mark+final_mark)/2;
}
/*
--------------------------------------------------------------------------
The purpose of this function is to return a letter grade to the calling
function based on the value (grade) passed into the function.
The function REQUIRES:
-A real number of type double
The function PROMISES:
-To provide a letter grade based on the grade
provided to the function
--------------------------------------------------------------------------
*/
char letter_grade_calculation(double student_avg)
{
char ch = ' ';
//This decision structure compares the value (grade)
//that was passed into the function to a set of conditions
//which will assign a letter grade accordingly
if (student_avg>=90 && student_avg<=100)
ch = 'A';
else if (student_avg>=80 && student_avg<=89)
ch = 'B';
else if (student_avg>=70 && student_avg<=79)
ch = 'C';
else if (student_avg>=60 && student_avg<=69)
ch = 'D';
else if (student_avg>=59 && student_avg<=0)
ch = 'F';
return ch;
}
/*
--------------------------------------------------------------------------------------------------------------------------------------
The purpose of this function is to print out the contents of 4 parallel arrays, and other information related to the input, including
the average mark and letter grade. The same index in each array is printed out in one row in the console area. Then
the content in the following index is printed out for each array in the following row. This is repeated until all of the elements
in each array is printed out.
This function REQUIRES
- 4 arrays
- An integer array for the first argument
- A array of type double for the second and third argument
- An array of Strings for the fourth and final argument
The function PROMISES
-To print out the contents of each of these arrays in the console area, by printing out the elements in the same index
in each array for one row, and then printing out each element of the 4 arrays for the following index in the following row.
This is repeated until all of the elements of each array are printed in the console area in this fashion.
----------------------------------------------------------------------------------------------------------------------------------------
*/
void print_records(int [] students_id, double []midterm_marks, double []final_marks, String []students_name)
{
//Prints the Header for the table once.
print("Name \t id \t Mid \t Final\t Average \t Mark\n---------------------------------------------------------\n");
//loop keeps track
for ( int i = 0; i<midterm_marks.length; i++)
{
double avg = calculate_student_average(midterm_marks[i], final_marks[i]);
char letter = letter_grade_calculation(avg);
print(students_name[i],"\t",students_id[i],"\t",midterm_marks[i],"\t",final_marks[i],"\t",avg
,"\t",letter, "\n");
}
}
/*
*/
void sort_records_by_id (int []indices, int []students_id )
{
for (int k = 0; k<indices.length; k++)
{
for (int j = k; j>0 && indices[j]<indices[j-1]; j--)
{
int place holder = indices[j];
indices[j] = indices [j-1];
indices[j-1] = place_holder;
}
}
}
void print_sorted_records(int []index, int [] studnts_id, double []midterm_marks, double []final_marks, String []students_name)
{
for(i=0; i<index; i++)
{
int k = index[i];
print(students_name[i],"\t",students_id[i],"\t",midterm_marks[i],"\t",final_marks[i],"\t",avg
,"\t",letter, "\n");
}
}
/*
-----------------------------------------------------------------------------------------------------------------------
The purpose of this function is to search a given array of strings for a particular name or sequence of letters,
and if it finds the name or sequence of letters, then it returns its index number to the user. If an equivalent entry
in the array is not found, then the function returns a -1 to the calling function.
The function REQUIRES:
-An array of Strings to search through
-A String which is searched for in the array
The function PROMISES:
-To return the index position of the Target word (Word we are searching for)in the
array of strings passed into the function.
-If an equivalent name or sequence of words is not found in the array as the name or sequence
of letters provided by the user, than the function returns -1.
------------------------------------------------------------------------------------------------------------------------
*/
int search (String [] students_name, String target)
{
//local variable containing the value or index value
//to be returned to the calling function
int index =-1 ;
//This loop iterates through the contents of the array
//passed into the function, and compares each of its elements
//to the target/key word the user desires to search for. If a match
//is successfully found, we overwrite the -1 in the local variable with
//the index number of the word, and return it to the calling function. Otherwise,
//if a match is not found, -1 is not overwritten, and that will be the value returned
//to the user at the end of the loop.
for (int k = 0; k<students_name.length; k++)
{
//if the String at k in the array matches the target word
//then we assign k, the counter value, representing index, to
//the local variable.
if(students_name[k].equals(target) == true)
index = k;
}
return index;
}
void sort_records_by_id (int []indices, int []students_id )
{
for (int k = 0; k<indices.length; k++)
{
for (int j = k; j>0 && indices[j]<indices[j-1]; j--)
{
int place holder = indices[j];
indices[j] = indices [j-1];
indices[j-1] = place_holder;
}
}
}
我必须创建一个能够对整数数组进行排序的函数，不是通过更改和重新排列其内容，而是通过更改另一个整数数组（称为索引）中的整数顺序。
所以，我会有一个包含一系列 id 的数组，例如：
让我们称这个 id"
[#]代表索引
[0]10001
12001
[2]12334
[3]14332
[4]999999
[5]10111
有对应数组，整数值
[#] 是索引
让我们称之为 arr
[0]0
11
[2}2
[3]3
[4]4
[5]5
这样它们就对应于我们在另一个数组中的索引。
现在，我们必须改变"arr"的顺序，使元素的顺序与数组id中索引的顺序相对应。
请注意，数组 ID 不会以任何方式更改。
因此，我们可以通过使用 for 循环、arr 的值和数组 id，按升序将 ids 打印到控制台。
我希望我能够充分解释它。我还附上了一张图片以帮助澄清。
基本上，我的排序功能（如上所示）无法正常工作。
这个函数：
void sort_records_by_id (int []indices, int []students_id )
{
for (int k = 0; k<indices.length; k++)
{
for (int j = k; j>0 && indices[j]<indices[j-1]; j--)
{
int place holder = indices[j];
indices[j] = indices [j-1];
indices[j-1] = place_holder;
}
}
}
我想应该实现 BubbleSort-Algorithm。它没有。我的个人建议：通读提供的 link 上的算法细节，并确保您 理解 是。之后为普通 int-array 实现它并根据您的需要更改代码。将索引映射到实际值应该不会太难。错误范围包括排序需要对值进行实际比较，您的代码不会超过不正确的循环等。老实说，如果我修复了这段代码，您将无法识别其中的大部分内容。
但是：
OOP 的重点是尽可能避免这种情况。好吧，实际上这也可以通过 C++ 中的 struct 来解决，尽管为了可扩展性我会使用对象。在实施适当的 class 之后，整个事情变成了一个没有任何陷阱的微不足道的冒泡排序。
template<class I, class C>
void sort_indexes( I begin, I end, C const& container ) {
using index_type = std::iterator_traits<I>::reference;
std::sort( begin, end, [&](index_type lhs, index_type rhs) {
return container[lhs]<container[rhs];
};
}
给定索引的迭代器范围（begin 到 end）和一个用于查找的容器，对索引进行排序。
这里我们写一个泛型函数。它需要两个迭代器 begin 和 end。这些构成了一个 half-open 范围。这就像 <algorithm> header.
中的函数一样工作
我们还带了一个集装箱。此容器必须支持使用 [] 索引范围内的索引进行查找。一个数组，一个std::vector，甚至一个std::map都可以在这里工作。
然后我们下注。我们得到 std::sort 来完成这项工作。 std::sort 有 3 个参数。
前两个是迭代器（我们有）。最后一个是比较函数object.
它必须回答问题 "given two elements, which is smaller?"。 returns 如果较小的在左边，则为真。
所以我们只需在 container 索引中进行查找！
其余代码 template 和 using 别名是为了保持代码的通用性。你可以写一个结构类似的，I 被替换为 int*，container 被替换为你可以在 [] 上做的事情，index_type int，很容易。
使用示例：
int indexes[100] = { /* blah */ };
int data[100] = { /* blah */ };
sort_indexes( indexes, indexes+100, data );
现在在实际代码中，我会编写和使用 order_by:
template<class F, class O=std::less<>>
auto order_by( F&& f, O&& o = {}) {
return
[f = std::forward<F>(f), o = std::forward<O>(o)]
(auto&& lhs, auto&& rhs)->bool
{
return o( f(decltype(lhs)(lhs)), f(decltype(rhs)(rhs)) );
};
}
这是晦涩的，但我们得到：
std::sort( indexes, indexes+100, order_by( [&](int i){ return data[i]; } ) );
即，sort_indexes 的工作减少为在调用站点调用 order_by。
order_by 所做的是从类型 T 到类型 U 的投影，然后根据 U 的 mapped-to 排序在 T 上生成排序。这正是您想要的此处要执行的操作——按 table.
中的值排序索引
以下是以上所有基本生成的内容：
void sort_indexes_to_ids( int* begin, int* end, int const* ids ) {
std::sort( begin, end, [&](int lhs, int rhs) {
return ids[lhs]<ids[rhs];
};
}
针对您的具体案例。
使用std::sort是解决这个问题的正确方法。 std::sort 将比您以您的技能水平编写的任何内容都更有效率。即使您的能力足以在狭窄的应用程序中击败它，测试和记录自定义排序代码的额外开销也需要理由。
void sort_records_by_id (int []indices, int []students_id )
{
for (int k = 0; k<indices.length; k++)
{
for (int j = k; j>0 && indices[j]<indices[j-1]; j--)
{
int place holder = indices[j];
indices[j] = indices [j-1];
indices[j-1] = place_holder;
}
}
}
void setup()
{
int [] students_id= {10001, 20001, 12334, 14332, 99999, 10111, 20101, 12034, 10332, 99991} ;
double [] midterm_marks = {99, 67, 88, 91, 56, 90, 70, 69, 79, 59};
double [] final_marks = {89, 76, 80, 67, 99, 98, 56, 96, 90, 60};
String [] students_name= {"Tim", "Joe", "Ali", "Kim", "Pam", "Rob", "Ben", "Ted", "Lee", "Jim"};
print_records(students_id, midterm_marks, final_marks, students_name);
// Using array of indices to use as an indicator of the order of teh records based on students id numbers
int[] indices = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// using insertion sort to reorder the indices based on students ids in an ascending order
sort_records_by_id(indices, students_id);
println();
println("The students records after sorting them by their id numbers are as follows:");
print_sorted_records(indices, students_id, midterm_marks, final_marks, students_name);
// Searching for the position of a student in the array of names and printing his/her records
// serarching for "Kim"
int position = search(students_name, "Kim");
if(position == -1) {
println("Search failed: " + "Kim" + " NOT FOUND");
}
else {
double average = calculate_student_average(midterm_marks[position], final_marks[position]);
println(students_name[position] + " was found: id: " + students_id[position]
+ " midterm mark: " + midterm_marks[position] + ", final mark: " + final_marks[position]
+ ", term average: " + average + ", and overal grade: " + letter_grade_calculation (average));
}
// Searching for "Sam"
position = search(students_name, "Sam");
if(position == -1) {
println("Search failed: " + "Sam" + " NOT FOUND");
}
else {
double average = calculate_student_average(midterm_marks[position], final_marks[position]);
println(students_name[position] + " was found: id is: " + students_id[position]
+ " midterm mark: " + midterm_marks[position] + ", final mark: " + final_marks[position]
+ ", term average: " + average + ", and overal grade: " + letter_grade_calculation (average));
}
}
/*
--------------------------------------------------------------------
The purpose of this function is to calculate the average of all the
numbers contained in an array and return that value to the calling
function.
The function REQUIRES
- An array of type double
The function PROMISES
-To return a value of type double to the user
representing the average of the array passed
by the user.
---------------------------------------------------------------------
*/
double calculate_class_average (double [] exam)
{
int i = 0;
double sum = 0;
//iterate through loop and add together the
//elements of the array into local variable
//"sum"
for (i = 0; i<exam.length; i++)
{
sum+=exam[i];
}
//Return the value of the average calculated
//by dividing sum, by the number of times the
//loop was executed, representing the # of elements
return (sum/i);
}
/*
-----------------------------------------------------------------------
The purpose of this function is to calculate the average between
two real numbers passed by the user and return that value to the
calling function
The function REQUIRES:
-Two real numbers of type double
The function PROMISES:
-To return the average between the
two values passed by the user as a
value of type double
-----------------------------------------------------------------------
*/
double calculate_student_average(double mid_mark, double final_mark)
{
//Calculate and retrun the average
//between the two numbers
return (mid_mark+final_mark)/2;
}
/*
--------------------------------------------------------------------------
The purpose of this function is to return a letter grade to the calling
function based on the value (grade) passed into the function.
The function REQUIRES:
-A real number of type double
The function PROMISES:
-To provide a letter grade based on the grade
provided to the function
--------------------------------------------------------------------------
*/
char letter_grade_calculation(double student_avg)
{
char ch = ' ';
//This decision structure compares the value (grade)
//that was passed into the function to a set of conditions
//which will assign a letter grade accordingly
if (student_avg>=90 && student_avg<=100)
ch = 'A';
else if (student_avg>=80 && student_avg<=89)
ch = 'B';
else if (student_avg>=70 && student_avg<=79)
ch = 'C';
else if (student_avg>=60 && student_avg<=69)
ch = 'D';
else if (student_avg>=59 && student_avg<=0)
ch = 'F';
return ch;
}
/*
--------------------------------------------------------------------------------------------------------------------------------------
The purpose of this function is to print out the contents of 4 parallel arrays, and other information related to the input, including
the average mark and letter grade. The same index in each array is printed out in one row in the console area. Then
the content in the following index is printed out for each array in the following row. This is repeated until all of the elements
in each array is printed out.
This function REQUIRES
- 4 arrays
- An integer array for the first argument
- A array of type double for the second and third argument
- An array of Strings for the fourth and final argument
The function PROMISES
-To print out the contents of each of these arrays in the console area, by printing out the elements in the same index
in each array for one row, and then printing out each element of the 4 arrays for the following index in the following row.
This is repeated until all of the elements of each array are printed in the console area in this fashion.
----------------------------------------------------------------------------------------------------------------------------------------
*/
void print_records(int [] students_id, double []midterm_marks, double []final_marks, String []students_name)
{
//Prints the Header for the table once.
print("Name \t id \t Mid \t Final\t Average \t Mark\n---------------------------------------------------------\n");
//loop keeps track
for ( int i = 0; i<midterm_marks.length; i++)
{
double avg = calculate_student_average(midterm_marks[i], final_marks[i]);
char letter = letter_grade_calculation(avg);
print(students_name[i],"\t",students_id[i],"\t",midterm_marks[i],"\t",final_marks[i],"\t",avg
,"\t",letter, "\n");
}
}
/*
*/
void sort_records_by_id (int []indices, int []students_id )
{
for (int k = 0; k<indices.length; k++)
{
for (int j = k; j>0 && indices[j]<indices[j-1]; j--)
{
int place holder = indices[j];
indices[j] = indices [j-1];
indices[j-1] = place_holder;
}
}
}
void print_sorted_records(int []index, int [] studnts_id, double []midterm_marks, double []final_marks, String []students_name)
{
for(i=0; i<index; i++)
{
int k = index[i];
print(students_name[i],"\t",students_id[i],"\t",midterm_marks[i],"\t",final_marks[i],"\t",avg
,"\t",letter, "\n");
}
}
/*
-----------------------------------------------------------------------------------------------------------------------
The purpose of this function is to search a given array of strings for a particular name or sequence of letters,
and if it finds the name or sequence of letters, then it returns its index number to the user. If an equivalent entry
in the array is not found, then the function returns a -1 to the calling function.
The function REQUIRES:
-An array of Strings to search through
-A String which is searched for in the array
The function PROMISES:
-To return the index position of the Target word (Word we are searching for)in the
array of strings passed into the function.
-If an equivalent name or sequence of words is not found in the array as the name or sequence
of letters provided by the user, than the function returns -1.
------------------------------------------------------------------------------------------------------------------------
*/
int search (String [] students_name, String target)
{
//local variable containing the value or index value
//to be returned to the calling function
int index =-1 ;
//This loop iterates through the contents of the array
//passed into the function, and compares each of its elements
//to the target/key word the user desires to search for. If a match
//is successfully found, we overwrite the -1 in the local variable with
//the index number of the word, and return it to the calling function. Otherwise,
//if a match is not found, -1 is not overwritten, and that will be the value returned
//to the user at the end of the loop.
for (int k = 0; k<students_name.length; k++)
{
//if the String at k in the array matches the target word
//then we assign k, the counter value, representing index, to
//the local variable.
if(students_name[k].equals(target) == true)
index = k;
}
return index;
}
void sort_records_by_id (int []indices, int []students_id )
{
for (int k = 0; k<indices.length; k++)
{
for (int j = k; j>0 && indices[j]<indices[j-1]; j--)
{
int place holder = indices[j];
indices[j] = indices [j-1];
indices[j-1] = place_holder;
}
}
}
我必须创建一个能够对整数数组进行排序的函数，不是通过更改和重新排列其内容，而是通过更改另一个整数数组（称为索引）中的整数顺序。 所以，我会有一个包含一系列 id 的数组，例如： 让我们称这个 id" [#]代表索引 [0]10001 12001 [2]12334 [3]14332 [4]999999 [5]10111
有对应数组，整数值 [#] 是索引 让我们称之为 arr [0]0 11 [2}2 [3]3 [4]4 [5]5 这样它们就对应于我们在另一个数组中的索引。
现在，我们必须改变"arr"的顺序，使元素的顺序与数组id中索引的顺序相对应。 请注意，数组 ID 不会以任何方式更改。
因此，我们可以通过使用 for 循环、arr 的值和数组 id，按升序将 ids 打印到控制台。
我希望我能够充分解释它。我还附上了一张图片以帮助澄清。
基本上，我的排序功能（如上所示）无法正常工作。
这个函数：
void sort_records_by_id (int []indices, int []students_id )
{
for (int k = 0; k<indices.length; k++)
{
for (int j = k; j>0 && indices[j]<indices[j-1]; j--)
{
int place holder = indices[j];
indices[j] = indices [j-1];
indices[j-1] = place_holder;
}
}
}
我想应该实现 BubbleSort-Algorithm。它没有。我的个人建议：通读提供的 link 上的算法细节，并确保您 理解 是。之后为普通 int-array 实现它并根据您的需要更改代码。将索引映射到实际值应该不会太难。错误范围包括排序需要对值进行实际比较，您的代码不会超过不正确的循环等。老实说，如果我修复了这段代码，您将无法识别其中的大部分内容。
但是：
OOP 的重点是尽可能避免这种情况。好吧，实际上这也可以通过 C++ 中的 struct 来解决，尽管为了可扩展性我会使用对象。在实施适当的 class 之后，整个事情变成了一个没有任何陷阱的微不足道的冒泡排序。
template<class I, class C>
void sort_indexes( I begin, I end, C const& container ) {
using index_type = std::iterator_traits<I>::reference;
std::sort( begin, end, [&](index_type lhs, index_type rhs) {
return container[lhs]<container[rhs];
};
}
给定索引的迭代器范围（begin 到 end）和一个用于查找的容器，对索引进行排序。
这里我们写一个泛型函数。它需要两个迭代器 begin 和 end。这些构成了一个 half-open 范围。这就像 <algorithm> header.
我们还带了一个集装箱。此容器必须支持使用 [] 索引范围内的索引进行查找。一个数组，一个std::vector，甚至一个std::map都可以在这里工作。
然后我们下注。我们得到 std::sort 来完成这项工作。 std::sort 有 3 个参数。
前两个是迭代器（我们有）。最后一个是比较函数object.
它必须回答问题 "given two elements, which is smaller?"。 returns 如果较小的在左边，则为真。
所以我们只需在 container 索引中进行查找！
其余代码 template 和 using 别名是为了保持代码的通用性。你可以写一个结构类似的，I 被替换为 int*，container 被替换为你可以在 [] 上做的事情，index_type int，很容易。
使用示例：
int indexes[100] = { /* blah */ };
int data[100] = { /* blah */ };
sort_indexes( indexes, indexes+100, data );
现在在实际代码中，我会编写和使用 order_by:
template<class F, class O=std::less<>>
auto order_by( F&& f, O&& o = {}) {
return
[f = std::forward<F>(f), o = std::forward<O>(o)]
(auto&& lhs, auto&& rhs)->bool
{
return o( f(decltype(lhs)(lhs)), f(decltype(rhs)(rhs)) );
};
}
这是晦涩的，但我们得到：
std::sort( indexes, indexes+100, order_by( [&](int i){ return data[i]; } ) );
即，sort_indexes 的工作减少为在调用站点调用 order_by。
order_by 所做的是从类型 T 到类型 U 的投影，然后根据 U 的 mapped-to 排序在 T 上生成排序。这正是您想要的此处要执行的操作——按 table.
以下是以上所有基本生成的内容：
void sort_indexes_to_ids( int* begin, int* end, int const* ids ) {
std::sort( begin, end, [&](int lhs, int rhs) {
return ids[lhs]<ids[rhs];
};
}
针对您的具体案例。
使用std::sort是解决这个问题的正确方法。 std::sort 将比您以您的技能水平编写的任何内容都更有效率。即使您的能力足以在狭窄的应用程序中击败它，测试和记录自定义排序代码的额外开销也需要理由。