Generate Half-Sorted BubbleSort

Question

Я пытался создать частично отсортированный массив.

Есть много способов сделать & Я выбрал свой собственный метод, который должен использовать любой алгоритм сортировки, там помещен «перерыв» в середине сортировки.

В этом случае я выбираю Bubble sort.

То, что я сделал, я остановить сортировку значения при счетчик достиг половин значений п

Но я понятия не имею, как это не работает, основываясь на моей логике.

Код:

#include<iostream> 
#include<vector> 

using namespace std; 

int main() 
{ 
    vector<int> a; 
    int i, j, p,n,temp; 
    cout << "Enter No. of Elements : "; 
    cin >> n;//user desired of total integers 
    for (i = 1; i <= n; i++)//this will loop from 1 to n value 
    { 
     a.push_back(i);//push into a vector 
    } 


    for (p = 1; p <= n ; p++)    
    { 

     for (j = 1; j <= n; j++) 
     { 
      if (j<n/2)// this is where, the sorting will stop 
      { 
       if (a[j] > a[j + 1]) 
       { 
        temp = a[j];      // Interchange Values 
        a[j] = a[j + 1]; 
        a[j + 1] = temp; 
       } 
      } 
     } 

    } 

    cout << "\nAfter Sorting : \n"; 
    for (i = 0; i <= n-1; i++) 
    { 
     cout << a[i] << endl; 
    } 
    system("pause"); 
    return 0; 
} 

Answer 1

Вы массив сначала сортируют, по крайней мере, создать его в обратном порядке, чтобы сделать ваши тесты смысл (или вы могли бы использовать некоторые случайные генераторы, тоже):

for (i = n - 1; i >= 0; i--) 

Тогда ваша логика ошибочна: вы не можете остановить выбор пузыря на полпути (сортировка пузырьков не гарантирует, что ранее перемещенные элементы больше не будут перемещаться, поэтому для этого нужны N^2 итерации), вместо этого, вам нужно сделать так, чтобы оно повторялось более n/2 элементов вместо o f n.

Что-то вроде:

for (p = 0; p <= n/2; p++)    
{ 
    for (j = 0; j <= n/2; j++) 
    { 
     if (a[j] > a[j + 1]) 
     { 
      temp = a[j];      
      a[j] = a[j + 1]; 
      a[j + 1] = temp; 
     } 
    } 
}