Chương trình C ++ cho Cocktail Sort?

Loại cocktail là một biến thể khác của loại bong bóng. Trong kỹ thuật sắp xếp bong bóng, nó luôn tìm kiếm từ trái sang phải và tìm phần tử lớn nhất ở cuối, trong giai đoạn thứ hai, nó tìm phần tử lớn thứ hai ở vị trí cuối cùng thứ hai. Kỹ thuật sắp xếp này đi theo cả hai hướng khác nhau. Hãy để chúng tôi xem thuật toán để hiểu ý tưởng.

Thuật toán

cocktail (mảng, n)

Begin
   flag := true
   start := 0, end := n-1
   while flag is set, do
      flag := false
      for i in range start to end-1, do
         if arr[i] > arr[i+1], then
            exchange arr[i] and arr[i+1]
            flag := true
         end if
      done
      if flag is not set, then
         break
      end if
      flag := false
      end := end – 1
      for i in range end -1 down to start, do
         if arr[i] > arr[i+1], then
            exchange arr[i] and arr[i+1]
            flag := true
         end if
      done
      start := start + 1
   done
End

Ví dụ

#include<iostream>
using namespace std;
void cocktailSort(int arr[], int n){
   bool flag = true;
   int start = 0, end = n-1;
   while(flag){
      flag = false;
      for(int i = start; i<end; i++){ //scan from left to right as bubble sort
         if(arr[i] > arr[i+1]){
            swap(arr[i], arr[i+1]);
            flag = true;
         }
      }
      if(!flag){ //if nothing has changed simply break the loop
         break;
      }
      flag = false;
      end--; //decrease the end pointer
      for(int i = end - 1; i >= start; i--){ //scan from right to left
         if(arr[i] > arr[i+1]){
            swap(arr[i], arr[i+1]);
            flag = true;
         }
      }
      start++;
   }
}
main() {
   int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
   int n = sizeof(data)/sizeof(data[0]);
   cout << "Sorted Sequence ";
   cocktailSort(data, n);
   for(int i = 0; i <n;i++){
      cout << data[i] << " ";
   }
}

Đầu ra

Sorted Sequence 13 20 32 35 40 54 74 98 98 154