셰이커 정렬을 수행하는 C++ 프로그램

셰이커 정렬은 주어진 데이터를 정렬하는 데 사용됩니다. 셰이커 정렬은 버블 정렬과 달리 양방향으로 배열을 정렬합니다. 이 알고리즘의 최악의 복잡성은 O(n^2)입니다.

알고리즘

Begin
   ShakerSort() function has ‘arr’ the array of data and ‘n’ the number of values, in the argument list.
   // Implement Sorting algorithm using nested for loops.
   The parent loop will run on ‘i’ from 0 to n-1 and contains two loops inside.
   The first loop will run on ‘j’ from i+1 to n-1 and use swap() if a[j] < a[j-1].
   Decrement n.
   The second loop will run on 'k' from m-1 to i+1 and use swap() if a[k] < a[k-1].
   Increment i.
End

예시 코드

#include<iostream>
using namespace std;
void swap(int *a, int *b) {
   int temp;
   temp = *a;
   *a = *b;
   *b = temp;
}
void ShakerSort(int a[], int m) {
   int i, j, k;
   for(i = 0; i < m;) {
      for(j = i+1; j < m; j++) {
         if(a[j] < a[j-1])
            swap(&a[j], &a[j-1]);
      }
      m--;
      for(k = m-1; k > i; k--) {
         if(a[k] < a[k-1])
            swap(&a[k], &a[k-1]);
      }
      i++;
   }
}
int main() {
   int n, i;
   cout<<"\nEnter the number of data element to be sorted: ";
   cin>>n;
   int a[n];
   for(i = 0; i < n; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>a[i];
   }
   ShakerSort(a, n);
   cout<<"\nSorted Data ";
   for (i = 0; i < n; i++)
      cout<<"->"<<a[i];
   return 0;
}

출력

Enter the number of data element to be sorted: 4
Enter element 1: 3
Enter element 2: 1
Enter element 3: 7
Enter element 4: 6
Sorted Data ->1->3->6->7