Sắp xếp Shell có giống với sắp xếp bong bóng không?

Question

Shellsort (còn được gọi là Shell sort hoặc Shell's method) là một thuật toán sắp xếp dựa trên so sánh tại chỗ

Nội dung chính Show

Giải trình
phức tạp
Triển khai
một tên khác cho sắp xếp bong bóng là gì?
Sự khác biệt giữa sắp xếp và sắp xếp bong bóng là gì?
Ý nghĩa của loại vỏ là gì?
Shell sắp xếp dựa trên thuật toán nào?

Shell Sort cải thiện độ phức tạp về thời gian của nó bằng cách tận dụng lợi thế của việc sử dụng Sắp xếp chèn trên một mảng được sắp xếp một phần dẫn đến số lần di chuyển ít hơn

Đó là sự khái quát hóa

sắp xếp theo trao đổi (sắp xếp bong bóng)
sắp xếp theo kiểu chèn (insertion sort)

Giải trình

Ý tưởng là sắp xếp danh sách các phần tử sao cho, bắt đầu từ bất kỳ đâu, xem xét mọi phần tử thứ h sẽ cho một danh sách được sắp xếp. Một danh sách như vậy được cho là được sắp xếp h
Lưu ý Mảng 1 sắp xếp là mảng đã sắp xếp
Xác định một chuỗi khoảng cách để làm việc trên

Nếu dãy khoảng cách là (5,3,1) và mảng bao gồm 14 phần tử (a1, a2,. , a14), khi đó, có ba đường chuyền

Trong lượt đầu tiên, các phần tử được nhóm thành (a1, a6, a11), (a2, a7, a12), (a3, a8, a13), (a4, a9, a14), (a5, a10). Mỗi nhóm được sắp xếp bằng Insertion Sort
Trong lượt thứ hai, việc sắp xếp 3 được thực hiện trên các nhóm (a1, a4, a7, a10, a13), (a2, a5, a8, a11, a14), (a3, a6, a9, a12)
Trong lượt thứ ba (cuối cùng), sắp xếp 1 được thực hiện trên (a1, a2,. , a14)

Mã giả của Sắp xếp vỏ sử dụng trình tự khoảng cách của Marcin Ciura, với sắp xếp chèn bên trong


# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]
# Start with the largest gap and work down to a gap of 1
foreach (gap in gaps)
{
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped order
    # keep adding one more element until the entire array is gap sorted
    for (i = gap; i < n; i += 1)
    {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
    }
}

phức tạp

Trường hợp xấu nhất thời gian phức tạp.


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

1 so sánh

Độ phức tạp thời gian trường hợp trung bình.


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

1 so sánh

Độ phức tạp thời gian trường hợp tốt nhất.


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

1

Độ phức tạp của không gian.


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

2

Triển khai

Triển khai thuật toán Shell Sort bằng 8 ngôn ngữ bao gồm


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

3,


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

4,


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

5,


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

6,


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

7,


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

8,


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

9 và


  #include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void shell_sort(int *a, int n)
{
  int i, j, gap, temp;
  /* Assess the array in gaps starting at half the array size - Each gap is a sublist of 2 values */
  for(gap = n/2 ; gap > 0 ; gap /= 2)
  {
    /* Index at the right value of each gap */
    for(i = gap ; i < n ; i++)
    {
      /* Take a copy of the value under inspection */
      temp = a[i];
      for(j = i ; j >= gap ; j-= gap)
      {
        /* Compare the values in the sub lists and swap where necessary */
        if(temp < a[j-gap])
          a[j] = a[j-gap];
        else
          break;
      }
      a[j] = temp;
    }
  }
}
int main(void)
{
  int i;
  int a[10] = { 5 , 211 , 66 , 7 , 12 , 2, 76 , 134 , 99 , 9 };
  printf("In: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  shell_sort(a, 10);
  printf("\nOut: ")
  for(i = 0 ; i < 10 ; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

00

một tên khác cho sắp xếp bong bóng là gì?

Thuật toán sắp xếp bong bóng, còn được gọi là sắp xếp chìm , là thuật toán sắp xếp đơn giản nhất chạy qua danh sách nhiều lần, so sánh các phần tử liền kề và .

Sự khác biệt giữa sắp xếp và sắp xếp bong bóng là gì?

Trong sắp xếp bong bóng, hai phần tử liền kề được so sánh. Nếu các phần tử liền kề không ở đúng vị trí, việc hoán đổi sẽ được thực hiện. Trong sắp xếp lựa chọn, phần tử tối thiểu được chọn từ mảng và hoán đổi với phần tử ở đầu mảng con chưa sắp xếp

Ý nghĩa của loại vỏ là gì?

Sắp xếp khung là thuật toán sắp xếp hiệu quả cao và dựa trên thuật toán sắp xếp chèn . Thuật toán này tránh những thay đổi lớn, như trong sắp xếp chèn, trong đó giá trị nhỏ hơn ở ngoài cùng bên phải và phải được di chuyển sang bên trái.

Shell sắp xếp dựa trên thuật toán nào?

Sắp xếp khung là phiên bản tổng quát của thuật toán sắp xếp chèn . Đầu tiên, nó sắp xếp các phần tử cách xa nhau và liên tục giảm khoảng cách giữa các phần tử được sắp xếp. Khoảng cách giữa các phần tử được giảm dựa trên trình tự được sử dụng.

programming