Interchange Sort & Shaker Sort

Hai thuật toán vừa được trình bày là "............ và ............."

(Viết thường tất cả chữ cái)

Ý tưởng của thuật toán Interchange sort

• A. Đổi chỗ vị trí cho nhau. Lặp lại xử lý trên với phần tử kế tiếp trong danh sách.

• B. Đổi chỗ hai phần tử đầu cuối. Lặp lại xử lý trên với phần tử kế tiếp trong danh sách

• C. Đổi chỗ hai phần tử kề nha.Lặp lại xử lý trên với phần tử kế tiếp trong danh sách

• D. Đổi chỗ hai phần tử trong cặp nghịch thế. Lặp lại xử lý trên với phần tử kế tiếp trong danh sách

Đâu không phải là tên gọi của Shaker Sort

• A.Bi-Directional Sort

• B.Shuttle Sort

• C.Ripple Sort

• D.Interchange Sort

Shaker Sort được đánh giá như thế nào

• A. Thuật toán không nhận diện được mảng đã sắp xếp

• B.Thuật toán nhận diện được mảng đã sắp xếp

• C. Độ phức tạp cho trường hợp tốt nhất là O(n)

• d. Cả B và C đều đúng

Cho dãy số sau: 6 1 3 0 5 7. Áp dụng phương pháp Interchange Sort, sau bao nhiều lần thực thì dãy số đã cho được sắp xếp tuần tự tăng dần

• A.4

• B.5

• C.6

• D.7

Giả sử cần sắp xếp mảng M có N phần tử sau theo phương pháp Shaker Sort {6 1 3 0 5 7}

Vòng lặp được thực hiện _ lần  thì mảng M đã cho được sắp xếp tuần tự tăng dần

• A.1

• B.2

• C.3

• D.4

Chọn đáp án đúng về hàm Swap

• A. void Swap(int &X, int &Y) {

  int Temp = X;

  X = Y;

  Y = Temp;

  return; }

• B. void Swap(float X, float Y) {

  int Temp = X;

  X = Y;

  Y = Temp;

  return; }

• C. void Swap(int *X, int *Y) {

  int Temp = X;

  X = Y;

  Y = Temp;

  return; }

• D. void Swap(int X, int Y) {

  int Temp = X;

  X = Y;

  Y = Temp;

  return; }

void shakerSort(int a[], int n){

int Left = 0;

int Right = n – 1;

int k = 0;

Biến k có dùng để làm gì?

• Biến k được sử dụng để lưu lại số lần các phần tử trong mảng bị đổi chỗ trong quá trình sắp xếp

• Biến k là một biến tạm thời được sử dụng để lưu giá trị tạm của phần tử đang được so sánh

• Nếu ta sử dụng thuật toán Shaker Sort với biến k, giá trị của k sẽ bằng 0 sau khi hoàn thành việc sắp xếp mảng [5, 1, 4, 2, 8]

• Biến k được sử dụng để lưu lại vị trí cuối cùng của phần tử bị hoán đổi trong vòng lặp trước

Cho dãy số {6 1 3 0 5 7 }. Áp dụng phương pháp sắp xếp lựa chọn (Interchange Sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 6 3 1 5 7 }. Dãy số thu được sau lần lặp thứ ba là:

Đâu là cặp nghịch thế

• A. a[3]=1      a[4]=52

• B.  a[0]=25  

  a[1]=4

• C. a[0]=25     a[1]=26

• D. a[4]=20     a[5]=32