Why does insertion sort work only if we use while as an inner loop and doesn’t work for ” for loop”?

huangapple go评论111阅读模式
英文:

Why does insertion sort work only if we use while as an inner loop and doesn’t work for ” for loop”?

问题

我试图尝试一个插入排序算法的问题。然而,我有以下问题。

我想了解为什么大多数在线解决方案使用嵌套的while循环而不是嵌套的for循环?我认为这可能与时间复杂度有关,然而,两者的时间复杂度都是O(n^2)。

下面我附上了两种不同的解决方案。


public class InsertionSort { 
// 我的方法
    /*使用插入排序对数组进行排序的函数*/
    // void sort(int arr[]) 
    // { 
    //     int n = arr.length; 
    //     for (int i = 1; i < n; ++i) { 
    //         if(arr[i] < arr[i-1]){
    //             for(int j = 0; j < i; j++){
    //                 if(arr[i] < arr[j]){
    //                     int temp = arr[j];
    //                     arr[j] = arr[i];
    //                     arr[i] = temp;
    //                 }
    //             }
    //         }
    //     } 
    // } 

// 在线解决方案
  
    void sort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 1; i < n; ++i) { 
            int key = arr[i]; 
            int j = i - 1; 

            /* 将arr[0..i-1]中大于key的元素向前移动一个位置,直到其当前位置的前一个位置 */
            while (j >= 0 && arr[j] > key) { 
                arr[j + 1] = arr[j]; 
                j = j - 1; 
            } 
            arr[j + 1] = key; 
        } 
    } 
英文:

I was trying to attempt a insertion algorithm question. However, I had the following question.

I wanted to nderstand why most solutions online use a nested while loop instead of a nested for loop? I thought it might have to do something with time complexity, however, both have a O(n^2) complexity.

Below I have attached the two different solutions


public class InsertionSort { 
// MY method
    /*Function to sort array using insertion sort*/
    // void sort(int arr[]) 
    // { 
    //     int n = arr.length; 
    //     for (int i = 1; i &lt; n; ++i) { 
    //         if(arr[i] &lt; arr[i-1]){
    //             for(int j = 0; j &lt; i; j++){
    //                 if(arr[i] &lt; arr[j]){
    //                     int temp = arr[j];
    //                     arr[j] = arr[i];
    //                     arr[i] = temp;
    //                 }
    //             }
    //         }
    //     } 
    // } 

// Online Solution
  
    void sort(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 1; i &lt; n; ++i) { 
            int key = arr[i]; 
            int j = i - 1; 
  
            /* Move elements of arr[0..i-1], that are 
               greater than key, to one position ahead 
               of their current position */
            while (j &gt;= 0 &amp;&amp; arr[j] &gt; key) { 
                arr[j + 1] = arr[j]; 
                j = j - 1; 
            } 
            arr[j + 1] = key; 
        } 
    } 

答案1

得分: 2

通常在开发算法时,您会根据以下情况选择循环结构:

  • 如果迭代次数已知,请使用 for 循环。
  • 如果迭代次数已知,请使用 while 循环。

在 Java 和其他编程语言中,您可以使用这两种循环结构来实现相同的功能。无论迭代次数是否已知,都没有关系。然而,从逻辑/可读性的角度来看,以下方式更合理:

  • ... 对于已知起始值到已知限制的范围,执行 ...
  • ... 条件为真时,执行 ...

伪代码中,伪代码是一种在不涉及实现细节的情况下描述算法的方式,通常就是这样写的(或类似写法):

对于 i 从 0 到 n,执行
    ...
当条件成立时,执行
    ...

当您查看 sort 算法时,会看到两个循环:外部的 for 循环和内部的 while 循环。

  • 外部循环是一个 for 循环,因为 in 是已知的。值 n 是已知的,因为它由数组的大小给出,在这个算法中是一个常数。
  • 内部循环是一个 while 循环,因为不知道条件何时失败,这取决于数组访问。您不知道这些值;如果知道的话,就可以通过硬编码一些交换来对数组进行排序。
英文:

Usually, when developing algorithms, you choose a loop based on this:

  • If the number of iterations is known, use a for-loop.
  • If the number of iterations is not known, use a while-loop.

In Java, and other languages, you can implement the same thing using both loops. It doesn't matter if the number of iterations is known. However, it makes sense, it's more readable/logical:

  • ... for a known starting value to a known limit do ...
  • ... while a condition is true do ...

In pseudocode, which is a way to describe an algorithm independently of implementation-details, it's often done just like that (or similar):

for i = 0 to n do
    ...
while condition do
    ...

When you look at sort, you can see two loops: the outer for-loop and the inner while-loop.

  • The outer loop is a for-loop because i and n are known. Value n is known because it's given by the size of the array, which is a constant in this algorithm.
  • The inner loop is a while-loop because it's not known when the condition will fail, as it depends on an array-access. You don't know the values; if you would, then you could sort the array by hardcoding some swaps.

huangapple
  • 本文由 发表于 2020年8月29日 17:03:17
  • 转载请务必保留本文链接:https://go.coder-hub.com/63645255.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定