英文:
How Do I Implement an Insertion Sort Method for A Generic ArrayList?
问题
@Override
public <T extends Comparable<T>> void insertionSort(ArrayList<T> data) {
int i, x = 0;
T key;
for (i = 1; i < data.size(); i++) {
key = data.get(i);
x = i - 1;
while (x >= 0 && data.get(x).compareTo(key) > 0) {
data.set(x + 1, data.get(x));
x--;
}
data.set(x + 1, key);
}
}
英文:
I am meant to create a simple insertion sort method which sorts a series of generic names into alphabetical order. This should be simple, and I have already reviewed many other examples of insertion sort online, including on this site, yet I still cannot seem to obtain the correct output despite comparing my code, line-by-line, with other versions and being unable to identify what I have done different than some supposedly successful insertion sort methods.
The following code is the main class which I am not meant to alter:
public static void main(String[] args) {
GenericTools t = new ToolBox();
ArrayList<String> data = new ArrayList<>();
data.add("Carlos");
data.add("Alice");
data.add("Bob");
data.add("Zebra");
data.add("Fred");
t.insertionSort(data);
data.forEach(x -> System.out.println(x));
}
And, this is the GenericTools interface referenced above, for the record:
public <T> void swap(ArrayList<T> data, int p1, int p2);
Finally, this is my code which should be correctly sorting this list:
@Override
public <T extends Comparable<T>> void insertionSort(ArrayList<T> data) {
int i, x =0;
T key;
for (i=1;i<data.size();i++){
key= data.get(i);
while (x>=0 && data.get(x).compareTo(key) > 0){
data.set(x+1,data.get(i));
x--;
}
data.set(x+1,key);
}
}
However, instead produces the following output:
Fred
Alice
Bob
Zebra
Fred
As opposed to correct output of:
Alice
Bob
Carlos
Fred
Zebra
答案1
得分: 1
所以你打算在 ArrayList 的已排序部分(索引从 0 到 i - 1)上进行迭代,以降序的方式,并且同时将相对大于 key
的元素向右移动一个位置,同时找到放置 key
(data.get(i))的正确位置。你的算法是正确的,但在那里你犯了两个简单的错误:
-
你忘记在内部的 while 循环之前将变量
x
初始化为i - 1
。 -
当当前元素在字母上大于
key
时,你应该将 当前元素(data.get(x))右移一步,而不是data.get(i)
。
@Override
public <T extends Comparable<T>> void insertionSort(ArrayList<T> data) {
int i, x = 0;
T key;
for (i = 1; i < data.size(); i++) {
key = data.get(i);
x = i - 1; // 将 x 设置为 i - 1
while (x >= 0 && data.get(x).compareTo(key) > 0) {
data.set(x + 1, data.get(x)); // 移动 data.get(x) 而不是 data.get(i)。
x--;
}
data.set(x + 1, key);
}
}
英文:
So you intended to iterate over the sorted part (indices between 0 and i - 1) of the ArrayList in descending order and shift elements relatively greater than key
in right direction by one position at the same time, and find the correct position where to put the key
(data.get(i)). Your algorithm is right, but there are two simple mistakes you've made there:
-
you forgot to initialize variable
x
toi - 1
before inner while-loop. -
when current element is alphabetically greater than the
key
, you should move current element (data.get(x)) one step right instead ofdata.get(i)
.
@Override
public <T extends Comparable<T>> void insertionSort(ArrayList<T> data) {
int i, x =0;
T key;
for (i=1; i<data.size(); i++){
key= data.get(i);
x = i - 1; // set x to i - 1
while (x >= 0 && data.get(x).compareTo(key) > 0){
data.set(x+1, data.get(x)); // move data.get(x) instead of data.get(i).
x--;
}
data.set(x+1,key);
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论