2

次のバブルソートの2番目のforループの正確な目的を誰かが説明できますか？最初のループが配列の'i'番目の整数を調べていることは理解していますが、2番目のforループは正確には何を調べていますか？

このトピックについての私の無知を許してください。私は今1週間未満コーディングしていて、このテーマについて少し混乱しています。

void sort(int array[], int size) {
  for(int i = 0, x = size - 1; i < x; i++) {
    for(int j = 0; j < x - 1; j++) {
      if(array[j] > array[j + 1]) {
        int tmp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = tmp;
      }
    }
  }
}
4

2 に答える 2

4

Bubble Sort最初のループはリストの並べ替えに必要なパスの数を示しているため、実装したいことを考えると、最初のループも間違っていると思います。バブルソートの場合Total Number of elements - 1、n個の要素のリストをソートするために必要なパス数と同じです（n-1）パスが必要です。したがって、i私が間違っていない限り、私の謙虚な意見では、の値は1から開始する必要があります。さらに、提供されたスニペットは、必要に応じて変数を宣言するという点で、C言語のコーディングスタイルに似ていません。

2番目のループは基本的に比較を減らすためにあります（要素の数-パス-1）。各反復の後、各パスで最大の要素を（論理的にソートされていないリストの）右側に配置するためです。したがって、その要素は正しい位置にあるので、他の要素と比較する必要はありません。

  4 3 2 1 Original List
  3 2 1 4 Pass 1
        -
        Now since this above 4 is in it's rightful place
        we don't need to compare it with other elements.
        Hence we will start from the zeroth element and 
        compare two adjacent values, till 1 (for Pass 2)
        Here comparison will take place between 3 and 2,
        and since 3 is greater than 2, hence swapping 
        between 3 and 2, takes place. Now 3 is comapred
        with 1, again since greater value is on left
        side, so swapping will occur. Now 3 is not compared
        with 4, since both these values are in their 
        rightful place.
  2 1 3 4 Pass 2
      - 
        Now since this above 3 is in it's rightful place
        we don't need to compare it with other elements.
        Hence we will start from the zeroth element and 
        compare two adjacent values, till 1 (for Pass 3)
        Here only one comparison will occur, between
        2 and 1. After swapping 2 will come to it's rightful
        position. So no further comparison is needed.
  1 2 3 4 Pass 3
  Here the list is sorted, so no more comparisons, after Pass 3.    


void bubbleSort(int *ptr, int size)
{
        int pass = 1, i = 0, temp = 0;
        for (pass = 1; pass < size - 1; pass++)
        {
                for (i = 0; i <= size - pass - 1; i++)
                {
                        if (*(ptr + i) > *(ptr + i + 1))
                        {
                                temp = *(ptr + i);
                                *(ptr + i) = *(ptr + i + 1);
                                *(ptr + i + 1) = temp;
                        }
                }
                printf("Pass : %d\n", pass);
                for (temp = 0; temp < size; temp++)
                        printf("%d\t", *(ptr + temp));
                puts("");
        }
}
于 2013-03-10T06:21:47.663 に答える
1

バブルソートループが間違っています。正しいものは次のとおりです。

void bubbleSort(int numbers[], int array_size) {
  int i, j, temp;

  for (i = (array_size - 1); i > 0; i--) {
    for (j = 1; j <= i; j++) {
      if (numbers[j-1] > numbers[j]) {
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
}

2番目のループは主な作業を行っています。各ペアを比較し、それらの位置を入れ替えて、大きい方の数値が右に行くようにします（右が配列の最後に近づく）。

于 2013-03-10T06:24:19.080 に答える