/* Starting from the left of the list, mona compares numbers by pairs. If the first pair is ordered [smaller number, larger number], she moves on. If the first pair is ordered [larger number, smaller number], she swaps the two integers before moving on to the next pair. She repeats this process until she reaches the end of the list. Then, she moves back to the beginning of the list and repeats this process until the entire list is sorted. If the unsorted list is: [3, 9, 7, 4], she will perform the following steps (note Swaps here refers to cumulative swaps): She starts with the first pair [3, 9] is in order, move on. List: [3, 9, 7, 4]. Swaps: 0. [9, 7] is not. Swap. List: [3, 7, 9, 4]. Swaps: 1 [9, 4] is not. Swap. List: [3, 7, 4, 9]. Swaps: 2 Check if list is sorted. It is not, so start over at first pair. [3, 7] is in order, move on. List: [3, 7, 4, 9]. Swaps: 2 [7, 4] is not. Swap. List: [3, 4, 7, 9]. Swaps: 3. [7, 9] is in order, move on. List: [3, 4, 7, 9]. Swaps: 3. Check if list is sorted. It is */ #include #include using namespace std; #if 0 void print(vector&& v) { cout << '[' << v[0]; for(size_t i{1}; i < v.size(); ++i) cout << ", " << v[i]; cout << "]\n"; } #endif void Draw_vector_element(int indx, int ele) { cout << "iv[" << indx << "] = " << ele << " |"; for (int i = (0); i < ele; ++i) { cout << "=="; } cout << "\n"; } void Draw_vector(vector const &iv) { size_t idx{0}; for (auto i:iv) { Draw_vector_element(idx++,i); } cout << "\n"; } static size_t nswaps{0}; static bool swapped{false}; size_t BSort(vector&& v, size_t N) { for(size_t i{0}; i < N - 1; ++i) { if(v[i] > v[i + 1]) { swap(v[i], v[i+1]); swapped = true; nswaps += 1; //print(move(v)); Draw_vector(v); } } if (!swapped) return nswaps; if (N > 2) BSort(move(v), N-1); return nswaps; }; int main() { vector> lseq{{2,3,4,0,6,1,8,7,5,9}, {5,4,3}, {1,3,4,5}, {5,4,3,2}, {8,4,7,5,3}, {1,4,3,5,2}}; for(auto&& vec : lseq){ cout << "Initial State:\n"; //print(move(vec)); cout << '\n'; Draw_vector(vec); nswaps = 0; swapped = false; size_t nswaps = BSort(move(vec), vec.size()); cout << "\nnumber of swaps required = " << nswaps << "\n\n"; } }

[Challenge] Mirielle_List_sort.cpp